001package org.cpsolver.studentsct.online.selection; 002 003import java.util.ArrayList; 004import java.util.HashSet; 005import java.util.Hashtable; 006import java.util.List; 007import java.util.Set; 008 009import org.cpsolver.coursett.model.TimeLocation; 010import org.cpsolver.ifs.assignment.Assignment; 011import org.cpsolver.studentsct.extension.DistanceConflict; 012import org.cpsolver.studentsct.extension.TimeOverlapsCounter; 013import org.cpsolver.studentsct.model.CourseRequest; 014import org.cpsolver.studentsct.model.Enrollment; 015import org.cpsolver.studentsct.model.FreeTimeRequest; 016import org.cpsolver.studentsct.model.Request; 017import org.cpsolver.studentsct.model.Section; 018import org.cpsolver.studentsct.model.Student; 019import org.cpsolver.studentsct.model.Subpart; 020import org.cpsolver.studentsct.online.OnlineSectioningModel; 021import org.cpsolver.studentsct.online.selection.MultiCriteriaBranchAndBoundSelection.SelectionCriterion; 022import org.cpsolver.studentsct.weights.StudentWeights; 023 024/** 025* Multi-criteria selection criterion. This provides a lexicographical order of solutions using the 026* following criteria: 027* <ul> 028* <li>best priority & alternativity ignoring free time requests (a better solution has a higher priority course assigned or does not use alternative request if possible) 029* <li>avoid or minimize course time overlaps 030* <li>minimise use of over-expected classes (this prevents students of getting into classes that we know will be needed later in the process) 031* <li>best priority & alternativity including free time requests (this is to prevent students of gaming the system by adding free time requests) 032* <li>maximise selection (preferred sections) 033* <li>avoid or minimise time overlaps (for classes that are allowed to overlap and for free time requests) 034* <li>avoid or minimise distance conflicts 035* <li>avoid classes that have no time assignment (arranged hours) 036* <li>balance sections 037* <li>minimise class penalties (expressing how much a class is over-expected) 038* </ul> 039* 040* @version StudentSct 1.3 (Student Sectioning)<br> 041* Copyright (C) 2014 Tomas Muller<br> 042* <a href="mailto:muller@unitime.org">muller@unitime.org</a><br> 043* <a href="http://muller.unitime.org">http://muller.unitime.org</a><br> 044* <br> 045* This library is free software; you can redistribute it and/or modify 046* it under the terms of the GNU Lesser General Public License as 047* published by the Free Software Foundation; either version 3 of the 048* License, or (at your option) any later version. <br> 049* <br> 050* This library is distributed in the hope that it will be useful, but 051* WITHOUT ANY WARRANTY; without even the implied warranty of 052* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 053* Lesser General Public License for more details. <br> 054* <br> 055* You should have received a copy of the GNU Lesser General Public 056* License along with this library; if not see <a 057* href='http://www.gnu.org/licenses'>http://www.gnu.org/licenses</a>. 058* 059*/ 060public class OnlineSectioningCriterion implements SelectionCriterion { 061 private Hashtable<CourseRequest, Set<Section>> iPreferredSections = null; 062 private List<TimeToAvoid> iTimesToAvoid = null; 063 private OnlineSectioningModel iModel; 064 private Student iStudent; 065 066 /** 067 * Constructor 068 * @param student current student 069 * @param model online student sectioning model 070 * @param assignment current assignment 071 * @param preferredSections preferred sections 072 */ 073 public OnlineSectioningCriterion(Student student, OnlineSectioningModel model, 074 Assignment<Request, Enrollment> assignment, Hashtable<CourseRequest, Set<Section>> preferredSections) { 075 iStudent = student; 076 iModel = model; 077 iPreferredSections = preferredSections; 078 if (model.getProperties().getPropertyBoolean("OnlineStudentSectioning.TimesToAvoidHeuristics", true)) { 079 iTimesToAvoid = new ArrayList<TimeToAvoid>(); 080 for (Request r : iStudent.getRequests()) { 081 if (r instanceof CourseRequest) { 082 List<Enrollment> enrollments = ((CourseRequest) r).getAvaiableEnrollmentsSkipSameTime(assignment); 083 if (enrollments.size() <= 5) { 084 int penalty = (7 - enrollments.size()) * (r.isAlternative() ? 1 : 7 - enrollments.size()); 085 for (Enrollment enrollment : enrollments) 086 for (Section section : enrollment.getSections()) 087 if (section.getTime() != null) 088 iTimesToAvoid.add(new TimeToAvoid(section.getTime(), penalty, r.getPriority())); 089 } 090 } else if (r instanceof FreeTimeRequest) { 091 iTimesToAvoid.add(new TimeToAvoid(((FreeTimeRequest) r).getTime(), 1, r.getPriority())); 092 } 093 } 094 } 095 } 096 097 protected OnlineSectioningModel getModel() { 098 return iModel; 099 } 100 101 protected Student getStudent() { 102 return iStudent; 103 } 104 105 protected Set<Section> getPreferredSections(Request request) { 106 return iPreferredSections.get(request); 107 } 108 109 protected List<TimeToAvoid> getTimesToAvoid() { 110 return iTimesToAvoid; 111 } 112 113 /** 114 * Distance conflicts of idx-th assignment of the current schedule 115 */ 116 public Set<DistanceConflict.Conflict> getDistanceConflicts(Enrollment[] assignment, int idx) { 117 if (getModel().getDistanceConflict() == null || assignment[idx] == null) 118 return null; 119 Set<DistanceConflict.Conflict> dist = getModel().getDistanceConflict().conflicts(assignment[idx]); 120 for (int x = 0; x < idx; x++) 121 if (assignment[x] != null) 122 dist.addAll(getModel().getDistanceConflict().conflicts(assignment[x], assignment[idx])); 123 return dist; 124 } 125 126 /** 127 * Time overlapping conflicts of idx-th assignment of the current schedule 128 */ 129 public Set<TimeOverlapsCounter.Conflict> getTimeOverlappingConflicts(Enrollment[] assignment, int idx) { 130 if (getModel().getTimeOverlaps() == null || assignment[idx] == null) 131 return null; 132 Set<TimeOverlapsCounter.Conflict> overlaps = new HashSet<TimeOverlapsCounter.Conflict>(); 133 for (int x = 0; x < idx; x++) 134 if (assignment[x] != null) 135 overlaps.addAll(getModel().getTimeOverlaps().conflicts(assignment[x], assignment[idx])); 136 else if (getStudent().getRequests().get(x) instanceof FreeTimeRequest) 137 overlaps.addAll(getModel().getTimeOverlaps().conflicts( 138 ((FreeTimeRequest) getStudent().getRequests().get(x)).createEnrollment(), assignment[idx])); 139 return overlaps; 140 } 141 142 /** 143 * Weight of an assignment. Unlike 144 * {@link StudentWeights#getWeight(Assignment, Enrollment, Set, Set)}, only count this 145 * side of distance conflicts and time overlaps. 146 **/ 147 protected double getWeight(Assignment<Request, Enrollment> assignment, Enrollment enrollment, 148 Set<DistanceConflict.Conflict> distanceConflicts, Set<TimeOverlapsCounter.Conflict> timeOverlappingConflicts) { 149 double weight = -getModel().getStudentWeights().getWeight(assignment, enrollment); 150 if (distanceConflicts != null) 151 for (DistanceConflict.Conflict c : distanceConflicts) { 152 Enrollment other = (c.getE1().equals(enrollment) ? c.getE2() : c.getE1()); 153 if (other.getRequest().getPriority() <= enrollment.getRequest().getPriority()) 154 weight += getModel().getStudentWeights().getDistanceConflictWeight(assignment, c); 155 } 156 if (timeOverlappingConflicts != null) 157 for (TimeOverlapsCounter.Conflict c : timeOverlappingConflicts) { 158 weight += getModel().getStudentWeights().getTimeOverlapConflictWeight(assignment, enrollment, c); 159 } 160 return enrollment.getRequest().getWeight() * weight; 161 } 162 163 public Request getRequest(int index) { 164 return (index < 0 || index >= getStudent().getRequests().size() ? null : getStudent().getRequests().get(index)); 165 } 166 167 public boolean isFreeTime(int index) { 168 Request r = getRequest(index); 169 return r != null && r instanceof FreeTimeRequest; 170 } 171 172 @Override 173 public int compare(Assignment<Request, Enrollment> assignment, Enrollment[] current, Enrollment[] best) { 174 if (best == null) 175 return -1; 176 177 // 0. best priority & alternativity ignoring free time requests 178 boolean ft = false; 179 for (int idx = 0; idx < current.length; idx++) { 180 if (isFreeTime(idx)) { 181 ft = true; 182 continue; 183 } 184 if (best[idx] != null && best[idx].getAssignments() != null) { 185 if (current[idx] == null || current[idx].getSections() == null) 186 return 1; // higher priority request assigned 187 if (best[idx].getPriority() < current[idx].getPriority()) 188 return 1; // less alternative request assigned 189 } else { 190 if (current[idx] != null && current[idx].getAssignments() != null) 191 return -1; // higher priority request assigned 192 } 193 } 194 195 // 0.5. avoid course time overlaps 196 if (getModel().getTimeOverlaps() != null) { 197 int bestTimeOverlaps = 0, currentTimeOverlaps = 0; 198 for (int idx = 0; idx < current.length; idx++) { 199 if (best[idx] != null && best[idx].getAssignments() != null 200 && best[idx].getRequest() instanceof CourseRequest) { 201 for (int x = 0; x < idx; x++) { 202 if (best[x] != null && best[x].getAssignments() != null 203 && best[x].getRequest() instanceof CourseRequest) 204 bestTimeOverlaps += getModel().getTimeOverlaps().nrConflicts(best[x], best[idx]); 205 } 206 for (int x = 0; x < idx; x++) { 207 if (current[x] != null && current[x].getAssignments() != null 208 && current[x].getRequest() instanceof CourseRequest) 209 currentTimeOverlaps += getModel().getTimeOverlaps().nrConflicts(current[x], current[idx]); 210 } 211 } 212 } 213 if (currentTimeOverlaps < bestTimeOverlaps) 214 return -1; 215 if (bestTimeOverlaps < currentTimeOverlaps) 216 return 1; 217 } 218 219 // 1. minimize number of penalties 220 double bestPenalties = 0, currentPenalties = 0; 221 for (int idx = 0; idx < current.length; idx++) { 222 if (best[idx] != null && best[idx].getAssignments() != null && best[idx].isCourseRequest()) { 223 for (Section section : best[idx].getSections()) 224 bestPenalties += getModel().getOverExpected(assignment, section, best[idx].getRequest()); 225 for (Section section : current[idx].getSections()) 226 currentPenalties += getModel().getOverExpected(assignment, section, current[idx].getRequest()); 227 } 228 } 229 if (currentPenalties < bestPenalties) 230 return -1; 231 if (bestPenalties < currentPenalties) 232 return 1; 233 234 // 2. best priority & alternativity including free time requests 235 if (ft) { 236 for (int idx = 0; idx < current.length; idx++) { 237 if (best[idx] != null && best[idx].getAssignments() != null) { 238 if (current[idx] == null || current[idx].getSections() == null) 239 return 1; // higher priority request assigned 240 if (best[idx].getPriority() < current[idx].getPriority()) 241 return 1; // less alternative request assigned 242 } else { 243 if (current[idx] != null && current[idx].getAssignments() != null) 244 return -1; // higher priority request assigned 245 } 246 } 247 } 248 249 // 3. maximize selection 250 int bestSelected = 0, currentSelected = 0; 251 for (int idx = 0; idx < current.length; idx++) { 252 if (best[idx] != null && best[idx].getAssignments() != null && best[idx].isCourseRequest()) { 253 Set<Section> preferred = getPreferredSections(best[idx].getRequest()); 254 if (preferred != null && !preferred.isEmpty()) { 255 for (Section section : best[idx].getSections()) 256 if (preferred.contains(section)) 257 bestSelected++; 258 for (Section section : current[idx].getSections()) 259 if (preferred.contains(section)) 260 currentSelected++; 261 } 262 } 263 } 264 if (currentSelected > bestSelected) 265 return -1; 266 if (bestSelected > currentSelected) 267 return 1; 268 269 // 4. avoid time overlaps 270 if (getModel().getTimeOverlaps() != null) { 271 int bestTimeOverlaps = 0, currentTimeOverlaps = 0; 272 for (int idx = 0; idx < current.length; idx++) { 273 if (best[idx] != null && best[idx].getAssignments() != null) { 274 for (int x = 0; x < idx; x++) { 275 if (best[x] != null && best[x].getAssignments() != null) 276 bestTimeOverlaps += getModel().getTimeOverlaps().nrConflicts(best[x], best[idx]); 277 else if (getStudent().getRequests().get(x) instanceof FreeTimeRequest) 278 bestTimeOverlaps += getModel().getTimeOverlaps() 279 .nrConflicts( 280 ((FreeTimeRequest) getStudent().getRequests().get(x)).createEnrollment(), 281 best[idx]); 282 } 283 for (int x = 0; x < idx; x++) { 284 if (current[x] != null && current[x].getAssignments() != null) 285 currentTimeOverlaps += getModel().getTimeOverlaps().nrConflicts(current[x], current[idx]); 286 else if (getStudent().getRequests().get(x) instanceof FreeTimeRequest) 287 currentTimeOverlaps += getModel().getTimeOverlaps().nrConflicts( 288 ((FreeTimeRequest) getStudent().getRequests().get(x)).createEnrollment(), 289 current[idx]); 290 } 291 } 292 } 293 if (currentTimeOverlaps < bestTimeOverlaps) 294 return -1; 295 if (bestTimeOverlaps < currentTimeOverlaps) 296 return 1; 297 } 298 299 // 5. avoid distance conflicts 300 if (getModel().getDistanceConflict() != null) { 301 int bestDistanceConf = 0, currentDistanceConf = 0; 302 for (int idx = 0; idx < current.length; idx++) { 303 if (best[idx] != null && best[idx].getAssignments() != null) { 304 for (int x = 0; x < idx; x++) { 305 if (best[x] != null && best[x].getAssignments() != null) 306 bestDistanceConf += getModel().getDistanceConflict().nrConflicts(best[x], best[idx]); 307 } 308 for (int x = 0; x < idx; x++) { 309 if (current[x] != null && current[x].getAssignments() != null) 310 currentDistanceConf += getModel().getDistanceConflict().nrConflicts(current[x], 311 current[idx]); 312 } 313 } 314 } 315 if (currentDistanceConf < bestDistanceConf) 316 return -1; 317 if (bestDistanceConf < currentDistanceConf) 318 return 1; 319 } 320 321 // 6. avoid no-time sections 322 int bestNoTime = 0, currentNoTime = 0; 323 for (int idx = 0; idx < current.length; idx++) { 324 if (best[idx] != null && best[idx].getAssignments() != null) { 325 for (Section section : best[idx].getSections()) 326 if (section.getTime() == null) 327 bestNoTime++; 328 for (Section section : current[idx].getSections()) 329 if (section.getTime() == null) 330 currentNoTime++; 331 } 332 } 333 if (currentNoTime < bestNoTime) 334 return -1; 335 if (bestNoTime < currentNoTime) 336 return 1; 337 338 // 7. balance sections 339 double bestUnavailableSize = 0.0, currentUnavailableSize = 0.0; 340 int bestAltSectionsWithLimit = 0, currentAltSectionsWithLimit = 0; 341 for (int idx = 0; idx < current.length; idx++) { 342 if (best[idx] != null && best[idx].getAssignments() != null) { 343 for (Section section : best[idx].getSections()) { 344 Subpart subpart = section.getSubpart(); 345 // skip unlimited and single section subparts 346 if (subpart.getSections().size() <= 1 || subpart.getLimit() <= 0) 347 continue; 348 // average size 349 double averageSize = ((double) subpart.getLimit()) / subpart.getSections().size(); 350 // section is below average 351 if (section.getLimit() < averageSize) 352 bestUnavailableSize += (averageSize - section.getLimit()) / averageSize; 353 bestAltSectionsWithLimit++; 354 } 355 for (Section section : current[idx].getSections()) { 356 Subpart subpart = section.getSubpart(); 357 // skip unlimited and single section subparts 358 if (subpart.getSections().size() <= 1 || subpart.getLimit() <= 0) 359 continue; 360 // average size 361 double averageSize = ((double) subpart.getLimit()) / subpart.getSections().size(); 362 // section is below average 363 if (section.getLimit() < averageSize) 364 currentUnavailableSize += (averageSize - section.getLimit()) / averageSize; 365 currentAltSectionsWithLimit++; 366 } 367 } 368 } 369 double bestUnavailableSizeFraction = (bestUnavailableSize > 0 ? bestUnavailableSize / bestAltSectionsWithLimit 370 : 0.0); 371 double currentUnavailableSizeFraction = (currentUnavailableSize > 0 ? currentUnavailableSize 372 / currentAltSectionsWithLimit : 0.0); 373 if (currentUnavailableSizeFraction < bestUnavailableSizeFraction) 374 return -1; 375 if (bestUnavailableSizeFraction < currentUnavailableSizeFraction) 376 return 1; 377 378 // 8. average penalty sections 379 double bestPenalty = 0.0, currentPenalty = 0.0; 380 for (int idx = 0; idx < current.length; idx++) { 381 if (best[idx] != null && best[idx].getAssignments() != null) { 382 for (Section section : best[idx].getSections()) 383 bestPenalty += section.getPenalty(); 384 for (Section section : current[idx].getSections()) 385 currentPenalty += section.getPenalty(); 386 } 387 } 388 if (currentPenalty < bestPenalty) 389 return -1; 390 if (bestPenalty < currentPenalty) 391 return 1; 392 393 return 0; 394 } 395 396 @Override 397 public boolean canImprove(Assignment<Request, Enrollment> assignment, int maxIdx, Enrollment[] current, 398 Enrollment[] best) { 399 // 0. best priority & alternativity ignoring free time requests 400 int alt = 0; 401 boolean ft = false; 402 for (int idx = 0; idx < current.length; idx++) { 403 if (isFreeTime(idx)) { 404 ft = true; 405 continue; 406 } 407 Request request = getRequest(idx); 408 if (idx < maxIdx) { 409 if (best[idx] != null) { 410 if (current[idx] == null) 411 return false; // higher priority request assigned 412 if (best[idx].getPriority() < current[idx].getPriority()) 413 return false; // less alternative request assigned 414 if (request.isAlternative()) 415 alt--; 416 } else { 417 if (current[idx] != null) 418 return true; // higher priority request assigned 419 if (!request.isAlternative()) 420 alt++; 421 } 422 } else { 423 if (best[idx] != null) { 424 if (best[idx].getPriority() > 0) 425 return true; // alternativity can be improved 426 } else { 427 if (!request.isAlternative() || alt > 0) 428 return true; // priority can be improved 429 } 430 } 431 } 432 433 // 0.5. avoid course time overlaps 434 if (getModel().getTimeOverlaps() != null) { 435 int bestTimeOverlaps = 0, currentTimeOverlaps = 0; 436 for (int idx = 0; idx < current.length; idx++) { 437 if (best[idx] != null && best[idx].getRequest() instanceof CourseRequest) { 438 for (int x = 0; x < idx; x++) { 439 if (best[x] != null && best[x].getRequest() instanceof CourseRequest) 440 bestTimeOverlaps += getModel().getTimeOverlaps().nrConflicts(best[x], best[idx]); 441 } 442 } 443 if (current[idx] != null && idx < maxIdx && current[idx].getRequest() instanceof CourseRequest) { 444 for (int x = 0; x < idx; x++) { 445 if (current[x] != null && current[x].getRequest() instanceof CourseRequest) 446 currentTimeOverlaps += getModel().getTimeOverlaps().nrConflicts(current[x], current[idx]); 447 } 448 } 449 } 450 if (currentTimeOverlaps < bestTimeOverlaps) 451 return true; 452 if (bestTimeOverlaps < currentTimeOverlaps) 453 return false; 454 } 455 456 // 1. maximize number of penalties 457 double bestPenalties = 0, currentPenalties = 0; 458 for (int idx = 0; idx < current.length; idx++) { 459 if (best[idx] != null) { 460 for (Section section : best[idx].getSections()) 461 bestPenalties += getModel().getOverExpected(assignment, section, best[idx].getRequest()); 462 } 463 if (current[idx] != null && idx < maxIdx) { 464 for (Section section : current[idx].getSections()) 465 currentPenalties += getModel().getOverExpected(assignment, section, current[idx].getRequest()); 466 } 467 } 468 if (currentPenalties < bestPenalties) 469 return true; 470 if (bestPenalties < currentPenalties) 471 return false; 472 473 // 2. best priority & alternativity including free times 474 if (ft) { 475 alt = 0; 476 for (int idx = 0; idx < current.length; idx++) { 477 Request request = getStudent().getRequests().get(idx); 478 if (idx < maxIdx) { 479 if (best[idx] != null) { 480 if (current[idx] == null) 481 return false; // higher priority request assigned 482 if (best[idx].getPriority() < current[idx].getPriority()) 483 return false; // less alternative request assigned 484 if (request.isAlternative()) 485 alt--; 486 } else { 487 if (current[idx] != null) 488 return true; // higher priority request assigned 489 if (request instanceof CourseRequest && !request.isAlternative()) 490 alt++; 491 } 492 } else { 493 if (best[idx] != null) { 494 if (best[idx].getPriority() > 0) 495 return true; // alternativity can be improved 496 } else { 497 if (!request.isAlternative() || alt > 0) 498 return true; // priority can be improved 499 } 500 } 501 } 502 } 503 504 // 3. maximize selection 505 int bestSelected = 0, currentSelected = 0; 506 for (int idx = 0; idx < current.length; idx++) { 507 if (best[idx] != null && best[idx].isCourseRequest()) { 508 Set<Section> preferred = getPreferredSections(best[idx].getRequest()); 509 if (preferred != null && !preferred.isEmpty()) { 510 for (Section section : best[idx].getSections()) 511 if (preferred.contains(section)) { 512 if (idx < maxIdx) 513 bestSelected++; 514 } else if (idx >= maxIdx) 515 bestSelected--; 516 } 517 } 518 if (current[idx] != null && idx < maxIdx && current[idx].isCourseRequest()) { 519 Set<Section> preferred = getPreferredSections(current[idx].getRequest()); 520 if (preferred != null && !preferred.isEmpty()) { 521 for (Section section : current[idx].getSections()) 522 if (preferred.contains(section)) 523 currentSelected++; 524 } 525 } 526 } 527 if (currentSelected > bestSelected) 528 return true; 529 if (bestSelected > currentSelected) 530 return false; 531 532 // 4. avoid time overlaps 533 if (getModel().getTimeOverlaps() != null) { 534 int bestTimeOverlaps = 0, currentTimeOverlaps = 0; 535 for (int idx = 0; idx < current.length; idx++) { 536 if (best[idx] != null) { 537 for (int x = 0; x < idx; x++) { 538 if (best[x] != null) 539 bestTimeOverlaps += getModel().getTimeOverlaps().nrConflicts(best[x], best[idx]); 540 else if (getStudent().getRequests().get(x) instanceof FreeTimeRequest) 541 bestTimeOverlaps += getModel().getTimeOverlaps() 542 .nrConflicts( 543 ((FreeTimeRequest) getStudent().getRequests().get(x)).createEnrollment(), 544 best[idx]); 545 } 546 } 547 if (current[idx] != null && idx < maxIdx) { 548 for (int x = 0; x < idx; x++) { 549 if (current[x] != null) 550 currentTimeOverlaps += getModel().getTimeOverlaps().nrConflicts(current[x], current[idx]); 551 else if (getStudent().getRequests().get(x) instanceof FreeTimeRequest) 552 currentTimeOverlaps += getModel().getTimeOverlaps().nrConflicts( 553 ((FreeTimeRequest) getStudent().getRequests().get(x)).createEnrollment(), 554 current[idx]); 555 } 556 } 557 } 558 if (currentTimeOverlaps < bestTimeOverlaps) 559 return true; 560 if (bestTimeOverlaps < currentTimeOverlaps) 561 return false; 562 } 563 564 // 5. avoid distance conflicts 565 if (getModel().getDistanceConflict() != null) { 566 int bestDistanceConf = 0, currentDistanceConf = 0; 567 for (int idx = 0; idx < current.length; idx++) { 568 if (best[idx] != null) { 569 for (int x = 0; x < idx; x++) { 570 if (best[x] != null) 571 bestDistanceConf += getModel().getDistanceConflict().nrConflicts(best[x], best[idx]); 572 } 573 } 574 if (current[idx] != null && idx < maxIdx) { 575 for (int x = 0; x < idx; x++) { 576 if (current[x] != null) 577 currentDistanceConf += getModel().getDistanceConflict().nrConflicts(current[x], 578 current[idx]); 579 } 580 } 581 } 582 if (currentDistanceConf < bestDistanceConf) 583 return true; 584 if (bestDistanceConf < currentDistanceConf) 585 return false; 586 } 587 588 // 6. avoid no-time sections 589 int bestNoTime = 0, currentNoTime = 0; 590 for (int idx = 0; idx < current.length; idx++) { 591 if (best[idx] != null) { 592 for (Section section : best[idx].getSections()) 593 if (section.getTime() == null) 594 bestNoTime++; 595 } 596 if (current[idx] != null && idx < maxIdx) { 597 for (Section section : current[idx].getSections()) 598 if (section.getTime() == null) 599 currentNoTime++; 600 } 601 } 602 if (currentNoTime < bestNoTime) 603 return true; 604 if (bestNoTime < currentNoTime) 605 return false; 606 607 // 7. balance sections 608 double bestUnavailableSize = 0.0, currentUnavailableSize = 0.0; 609 int bestAltSectionsWithLimit = 0, currentAltSectionsWithLimit = 0; 610 for (int idx = 0; idx < current.length; idx++) { 611 if (best[idx] != null) { 612 for (Section section : best[idx].getSections()) { 613 Subpart subpart = section.getSubpart(); 614 // skip unlimited and single section subparts 615 if (subpart.getSections().size() <= 1 || subpart.getLimit() <= 0) 616 continue; 617 // average size 618 double averageSize = ((double) subpart.getLimit()) / subpart.getSections().size(); 619 // section is below average 620 if (section.getLimit() < averageSize) 621 bestUnavailableSize += (averageSize - section.getLimit()) / averageSize; 622 bestAltSectionsWithLimit++; 623 } 624 } 625 if (current[idx] != null && idx < maxIdx) { 626 for (Section section : current[idx].getSections()) { 627 Subpart subpart = section.getSubpart(); 628 // skip unlimited and single section subparts 629 if (subpart.getSections().size() <= 1 || subpart.getLimit() <= 0) 630 continue; 631 // average size 632 double averageSize = ((double) subpart.getLimit()) / subpart.getSections().size(); 633 // section is below average 634 if (section.getLimit() < averageSize) 635 currentUnavailableSize += (averageSize - section.getLimit()) / averageSize; 636 currentAltSectionsWithLimit++; 637 } 638 } 639 } 640 double bestUnavailableSizeFraction = (bestUnavailableSize > 0 ? bestUnavailableSize / bestAltSectionsWithLimit 641 : 0.0); 642 double currentUnavailableSizeFraction = (currentUnavailableSize > 0 ? currentUnavailableSize 643 / currentAltSectionsWithLimit : 0.0); 644 if (currentUnavailableSizeFraction < bestUnavailableSizeFraction) 645 return true; 646 if (bestUnavailableSizeFraction < currentUnavailableSizeFraction) 647 return false; 648 649 // 8. average penalty sections 650 double bestPenalty = 0.0, currentPenalty = 0.0; 651 for (int idx = 0; idx < current.length; idx++) { 652 if (best[idx] != null) { 653 for (Section section : best[idx].getSections()) 654 bestPenalty += section.getPenalty(); 655 if (idx >= maxIdx && best[idx].isCourseRequest()) 656 bestPenalty -= ((CourseRequest) best[idx].getRequest()).getMinPenalty(); 657 } 658 if (current[idx] != null && idx < maxIdx) { 659 for (Section section : current[idx].getSections()) 660 currentPenalty += section.getPenalty(); 661 } 662 } 663 if (currentPenalty < bestPenalty) 664 return true; 665 if (bestPenalty < currentPenalty) 666 return false; 667 668 return true; 669 } 670 671 @Override 672 public double getTotalWeight(Assignment<Request, Enrollment> assignment, Enrollment[] enrollemnts) { 673 if (enrollemnts == null) 674 return 0.0; 675 double value = 0.0; 676 for (int idx = 0; idx < enrollemnts.length; idx++) { 677 if (enrollemnts[idx] != null) 678 value += getWeight(assignment, enrollemnts[idx], getDistanceConflicts(enrollemnts, idx), 679 getTimeOverlappingConflicts(enrollemnts, idx)); 680 } 681 return value; 682 } 683 684 @Override 685 public int compare(Assignment<Request, Enrollment> assignment, Enrollment e1, Enrollment e2) { 686 // 1. alternativity 687 if (e1.getPriority() < e2.getPriority()) 688 return -1; 689 if (e1.getPriority() > e2.getPriority()) 690 return 1; 691 692 // 2. maximize number of penalties 693 double p1 = 0, p2 = 0; 694 for (Section section : e1.getSections()) 695 p1 += getModel().getOverExpected(assignment, section, e1.getRequest()); 696 for (Section section : e2.getSections()) 697 p2 += getModel().getOverExpected(assignment, section, e2.getRequest()); 698 if (p1 < p2) 699 return -1; 700 if (p2 < p1) 701 return 1; 702 703 // 3. maximize selection 704 if (e1.isCourseRequest()) { 705 Set<Section> preferred = getPreferredSections(e1.getRequest()); 706 if (preferred != null && !preferred.isEmpty()) { 707 int s1 = 0, s2 = 0; 708 for (Section section : e1.getSections()) 709 if (preferred.contains(section)) 710 s1++; 711 for (Section section : e2.getSections()) 712 if (preferred.contains(section)) 713 s2++; 714 if (s2 > s1) 715 return -1; 716 if (s1 > s2) 717 return 1; 718 } 719 } 720 721 // 4. avoid time overlaps 722 if (getTimesToAvoid() == null) { 723 if (getModel().getTimeOverlaps() != null) { 724 int o1 = getModel().getTimeOverlaps().nrFreeTimeConflicts(e1); 725 int o2 = getModel().getTimeOverlaps().nrFreeTimeConflicts(e2); 726 if (o1 < o2) 727 return -1; 728 if (o2 < o1) 729 return 1; 730 } 731 } else { 732 if (e1.getRequest().equals(e2.getRequest()) && e1.isCourseRequest()) { 733 double o1 = 0.0, o2 = 0.0; 734 for (Section s : e1.getSections()) { 735 if (s.getTime() != null) 736 for (TimeToAvoid avoid : getTimesToAvoid()) { 737 if (avoid.priority() > e1.getPriority()) 738 o1 += avoid.overlap(s.getTime()); 739 } 740 } 741 for (Section s : e2.getSections()) { 742 if (s.getTime() != null) 743 for (TimeToAvoid avoid : getTimesToAvoid()) { 744 if (avoid.priority() > e2.getPriority()) 745 o2 += avoid.overlap(s.getTime()); 746 } 747 } 748 if (o1 < o2) 749 return -1; 750 if (o2 < o1) 751 return 1; 752 } 753 } 754 755 // 5. avoid distance conflicts 756 if (getModel().getDistanceConflict() != null) { 757 int c1 = getModel().getDistanceConflict().nrConflicts(e1); 758 int c2 = getModel().getDistanceConflict().nrConflicts(e2); 759 if (c1 < c2) 760 return -1; 761 if (c2 < c1) 762 return 1; 763 } 764 765 // 6. avoid no-time sections 766 int n1 = 0, n2 = 0; 767 for (Section section : e1.getSections()) 768 if (section.getTime() == null) 769 n1++; 770 for (Section section : e2.getSections()) 771 if (section.getTime() == null) 772 n2++; 773 if (n1 < n2) 774 return -1; 775 if (n2 < n1) 776 return 1; 777 778 // 7. balance sections 779 double u1 = 0.0, u2 = 0.0; 780 int a1 = 0, a2 = 0; 781 for (Section section : e1.getSections()) { 782 Subpart subpart = section.getSubpart(); 783 // skip unlimited and single section subparts 784 if (subpart.getSections().size() <= 1 || subpart.getLimit() <= 0) 785 continue; 786 // average size 787 double averageSize = ((double) subpart.getLimit()) / subpart.getSections().size(); 788 // section is below average 789 if (section.getLimit() < averageSize) 790 u1 += (averageSize - section.getLimit()) / averageSize; 791 a1++; 792 } 793 for (Section section : e2.getSections()) { 794 Subpart subpart = section.getSubpart(); 795 // skip unlimited and single section subparts 796 if (subpart.getSections().size() <= 1 || subpart.getLimit() <= 0) 797 continue; 798 // average size 799 double averageSize = ((double) subpart.getLimit()) / subpart.getSections().size(); 800 // section is below average 801 if (section.getLimit() < averageSize) 802 u2 += (averageSize - section.getLimit()) / averageSize; 803 a2++; 804 } 805 double f1 = (u1 > 0 ? u1 / a1 : 0.0); 806 double f2 = (u2 > 0 ? u2 / a2 : 0.0); 807 if (f1 < f2) 808 return -1; 809 if (f2 < f1) 810 return 1; 811 812 // 8. average penalty sections 813 double x1 = 0.0, x2 = 0.0; 814 for (Section section : e1.getSections()) 815 x1 += section.getPenalty(); 816 for (Section section : e2.getSections()) 817 x2 += section.getPenalty(); 818 if (x1 < x2) 819 return -1; 820 if (x2 < x1) 821 return 1; 822 823 return 0; 824 } 825 826 /** 827 * Time to be avoided. 828 */ 829 protected static class TimeToAvoid { 830 private TimeLocation iTime; 831 private double iPenalty; 832 private int iPriority; 833 834 public TimeToAvoid(TimeLocation time, int penalty, int priority) { 835 iTime = time; 836 iPenalty = penalty; 837 iPriority = priority; 838 } 839 840 public int priority() { 841 return iPriority; 842 } 843 844 public double overlap(TimeLocation time) { 845 if (time.hasIntersection(iTime)) { 846 return iPenalty * (time.nrSharedDays(iTime) * time.nrSharedDays(iTime)) 847 / (iTime.getNrMeetings() * iTime.getLength()); 848 } else { 849 return 0.0; 850 } 851 } 852 853 @Override 854 public String toString() { 855 return iTime.getLongName(true) + " (" + iPriority + "/" + iPenalty + ")"; 856 } 857 } 858}