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 // 3.5 maximize preferences 270 double bestSelectedConfigs = 0, currentSelectedConfigs = 0; 271 double bestSelectedSections = 0, currentSelectedSections = 0; 272 for (int idx = 0; idx < current.length; idx++) { 273 if (best[idx] != null && best[idx].getAssignments() != null && best[idx].isCourseRequest()) { 274 bestSelectedSections += best[idx].percentSelectedSameSection(); 275 bestSelectedConfigs += best[idx].percentSelectedSameConfig(); 276 } 277 if (current[idx] != null && current[idx].getAssignments() != null && current[idx].isCourseRequest()) { 278 currentSelectedSections += current[idx].percentSelectedSameSection(); 279 currentSelectedConfigs += current[idx].percentSelectedSameConfig(); 280 } 281 } 282 if (0.3 * currentSelectedConfigs + 0.7 * currentSelectedSections > 0.3 * bestSelectedConfigs + 0.7 * bestSelectedSections) return -1; 283 if (0.3 * bestSelectedConfigs + 0.7 * bestSelectedSections > 0.3 * currentSelectedConfigs + 0.7 * currentSelectedSections) return 1; 284 285 // 4. avoid time overlaps 286 if (getModel().getTimeOverlaps() != null) { 287 int bestTimeOverlaps = 0, currentTimeOverlaps = 0; 288 for (int idx = 0; idx < current.length; idx++) { 289 if (best[idx] != null && best[idx].getAssignments() != null) { 290 for (int x = 0; x < idx; x++) { 291 if (best[x] != null && best[x].getAssignments() != null) 292 bestTimeOverlaps += getModel().getTimeOverlaps().nrConflicts(best[x], best[idx]); 293 else if (getStudent().getRequests().get(x) instanceof FreeTimeRequest) 294 bestTimeOverlaps += getModel().getTimeOverlaps() 295 .nrConflicts( 296 ((FreeTimeRequest) getStudent().getRequests().get(x)).createEnrollment(), 297 best[idx]); 298 } 299 for (int x = 0; x < idx; x++) { 300 if (current[x] != null && current[x].getAssignments() != null) 301 currentTimeOverlaps += getModel().getTimeOverlaps().nrConflicts(current[x], current[idx]); 302 else if (getStudent().getRequests().get(x) instanceof FreeTimeRequest) 303 currentTimeOverlaps += getModel().getTimeOverlaps().nrConflicts( 304 ((FreeTimeRequest) getStudent().getRequests().get(x)).createEnrollment(), 305 current[idx]); 306 } 307 } 308 } 309 if (currentTimeOverlaps < bestTimeOverlaps) 310 return -1; 311 if (bestTimeOverlaps < currentTimeOverlaps) 312 return 1; 313 } 314 315 // 5. avoid distance conflicts 316 if (getModel().getDistanceConflict() != null) { 317 int bestDistanceConf = 0, currentDistanceConf = 0; 318 for (int idx = 0; idx < current.length; idx++) { 319 if (best[idx] != null && best[idx].getAssignments() != null) { 320 for (int x = 0; x < idx; x++) { 321 if (best[x] != null && best[x].getAssignments() != null) 322 bestDistanceConf += getModel().getDistanceConflict().nrConflicts(best[x], best[idx]); 323 } 324 for (int x = 0; x < idx; x++) { 325 if (current[x] != null && current[x].getAssignments() != null) 326 currentDistanceConf += getModel().getDistanceConflict().nrConflicts(current[x], 327 current[idx]); 328 } 329 } 330 } 331 if (currentDistanceConf < bestDistanceConf) 332 return -1; 333 if (bestDistanceConf < currentDistanceConf) 334 return 1; 335 } 336 337 // 6. avoid no-time sections 338 int bestNoTime = 0, currentNoTime = 0; 339 for (int idx = 0; idx < current.length; idx++) { 340 if (best[idx] != null && best[idx].getAssignments() != null) { 341 for (Section section : best[idx].getSections()) 342 if (section.getTime() == null) 343 bestNoTime++; 344 for (Section section : current[idx].getSections()) 345 if (section.getTime() == null) 346 currentNoTime++; 347 } 348 } 349 if (currentNoTime < bestNoTime) 350 return -1; 351 if (bestNoTime < currentNoTime) 352 return 1; 353 354 // 7. balance sections 355 double bestUnavailableSize = 0.0, currentUnavailableSize = 0.0; 356 int bestAltSectionsWithLimit = 0, currentAltSectionsWithLimit = 0; 357 for (int idx = 0; idx < current.length; idx++) { 358 if (best[idx] != null && best[idx].getAssignments() != null) { 359 for (Section section : best[idx].getSections()) { 360 Subpart subpart = section.getSubpart(); 361 // skip unlimited and single section subparts 362 if (subpart.getSections().size() <= 1 || subpart.getLimit() <= 0) 363 continue; 364 // average size 365 double averageSize = ((double) subpart.getLimit()) / subpart.getSections().size(); 366 // section is below average 367 if (section.getLimit() < averageSize) 368 bestUnavailableSize += (averageSize - section.getLimit()) / averageSize; 369 bestAltSectionsWithLimit++; 370 } 371 for (Section section : current[idx].getSections()) { 372 Subpart subpart = section.getSubpart(); 373 // skip unlimited and single section subparts 374 if (subpart.getSections().size() <= 1 || subpart.getLimit() <= 0) 375 continue; 376 // average size 377 double averageSize = ((double) subpart.getLimit()) / subpart.getSections().size(); 378 // section is below average 379 if (section.getLimit() < averageSize) 380 currentUnavailableSize += (averageSize - section.getLimit()) / averageSize; 381 currentAltSectionsWithLimit++; 382 } 383 } 384 } 385 double bestUnavailableSizeFraction = (bestUnavailableSize > 0 ? bestUnavailableSize / bestAltSectionsWithLimit 386 : 0.0); 387 double currentUnavailableSizeFraction = (currentUnavailableSize > 0 ? currentUnavailableSize 388 / currentAltSectionsWithLimit : 0.0); 389 if (currentUnavailableSizeFraction < bestUnavailableSizeFraction) 390 return -1; 391 if (bestUnavailableSizeFraction < currentUnavailableSizeFraction) 392 return 1; 393 394 // 8. average penalty sections 395 double bestPenalty = 0.0, currentPenalty = 0.0; 396 for (int idx = 0; idx < current.length; idx++) { 397 if (best[idx] != null && best[idx].getAssignments() != null) { 398 for (Section section : best[idx].getSections()) 399 bestPenalty += section.getPenalty(); 400 for (Section section : current[idx].getSections()) 401 currentPenalty += section.getPenalty(); 402 } 403 } 404 if (currentPenalty < bestPenalty) 405 return -1; 406 if (bestPenalty < currentPenalty) 407 return 1; 408 409 return 0; 410 } 411 412 @Override 413 public boolean canImprove(Assignment<Request, Enrollment> assignment, int maxIdx, Enrollment[] current, 414 Enrollment[] best) { 415 // 0. best priority & alternativity ignoring free time requests 416 int alt = 0; 417 boolean ft = false; 418 for (int idx = 0; idx < current.length; idx++) { 419 if (isFreeTime(idx)) { 420 ft = true; 421 continue; 422 } 423 Request request = getRequest(idx); 424 if (idx < maxIdx) { 425 if (best[idx] != null) { 426 if (current[idx] == null) 427 return false; // higher priority request assigned 428 if (best[idx].getPriority() < current[idx].getPriority()) 429 return false; // less alternative request assigned 430 if (request.isAlternative()) 431 alt--; 432 } else { 433 if (current[idx] != null) 434 return true; // higher priority request assigned 435 if (!request.isAlternative()) 436 alt++; 437 } 438 } else { 439 if (best[idx] != null) { 440 if (best[idx].getPriority() > 0) 441 return true; // alternativity can be improved 442 } else { 443 if (!request.isAlternative() || alt > 0) 444 return true; // priority can be improved 445 } 446 } 447 } 448 449 // 0.5. avoid course time overlaps 450 if (getModel().getTimeOverlaps() != null) { 451 int bestTimeOverlaps = 0, currentTimeOverlaps = 0; 452 for (int idx = 0; idx < current.length; idx++) { 453 if (best[idx] != null && best[idx].getRequest() instanceof CourseRequest) { 454 for (int x = 0; x < idx; x++) { 455 if (best[x] != null && best[x].getRequest() instanceof CourseRequest) 456 bestTimeOverlaps += getModel().getTimeOverlaps().nrConflicts(best[x], best[idx]); 457 } 458 } 459 if (current[idx] != null && idx < maxIdx && current[idx].getRequest() instanceof CourseRequest) { 460 for (int x = 0; x < idx; x++) { 461 if (current[x] != null && current[x].getRequest() instanceof CourseRequest) 462 currentTimeOverlaps += getModel().getTimeOverlaps().nrConflicts(current[x], current[idx]); 463 } 464 } 465 } 466 if (currentTimeOverlaps < bestTimeOverlaps) 467 return true; 468 if (bestTimeOverlaps < currentTimeOverlaps) 469 return false; 470 } 471 472 // 1. maximize number of penalties 473 double bestPenalties = 0, currentPenalties = 0; 474 for (int idx = 0; idx < current.length; idx++) { 475 if (best[idx] != null) { 476 for (Section section : best[idx].getSections()) 477 bestPenalties += getModel().getOverExpected(assignment, section, best[idx].getRequest()); 478 } 479 if (current[idx] != null && idx < maxIdx) { 480 for (Section section : current[idx].getSections()) 481 currentPenalties += getModel().getOverExpected(assignment, section, current[idx].getRequest()); 482 } 483 } 484 if (currentPenalties < bestPenalties) 485 return true; 486 if (bestPenalties < currentPenalties) 487 return false; 488 489 // 2. best priority & alternativity including free times 490 if (ft) { 491 alt = 0; 492 for (int idx = 0; idx < current.length; idx++) { 493 Request request = getStudent().getRequests().get(idx); 494 if (idx < maxIdx) { 495 if (best[idx] != null) { 496 if (current[idx] == null) 497 return false; // higher priority request assigned 498 if (best[idx].getPriority() < current[idx].getPriority()) 499 return false; // less alternative request assigned 500 if (request.isAlternative()) 501 alt--; 502 } else { 503 if (current[idx] != null) 504 return true; // higher priority request assigned 505 if (request instanceof CourseRequest && !request.isAlternative()) 506 alt++; 507 } 508 } else { 509 if (best[idx] != null) { 510 if (best[idx].getPriority() > 0) 511 return true; // alternativity can be improved 512 } else { 513 if (!request.isAlternative() || alt > 0) 514 return true; // priority can be improved 515 } 516 } 517 } 518 } 519 520 // 3. maximize selection 521 int bestSelected = 0, currentSelected = 0; 522 for (int idx = 0; idx < current.length; idx++) { 523 if (best[idx] != null && best[idx].isCourseRequest()) { 524 Set<Section> preferred = getPreferredSections(best[idx].getRequest()); 525 if (preferred != null && !preferred.isEmpty()) { 526 for (Section section : best[idx].getSections()) 527 if (preferred.contains(section)) { 528 if (idx < maxIdx) 529 bestSelected++; 530 } else if (idx >= maxIdx) 531 bestSelected--; 532 } 533 } 534 if (current[idx] != null && idx < maxIdx && current[idx].isCourseRequest()) { 535 Set<Section> preferred = getPreferredSections(current[idx].getRequest()); 536 if (preferred != null && !preferred.isEmpty()) { 537 for (Section section : current[idx].getSections()) 538 if (preferred.contains(section)) 539 currentSelected++; 540 } 541 } 542 } 543 if (currentSelected > bestSelected) 544 return true; 545 if (bestSelected > currentSelected) 546 return false; 547 548 // 3.5 maximize preferences 549 double bestSelectedConfigs = 0, currentSelectedConfigs = 0; 550 double bestSelectedSections = 0, currentSelectedSections = 0; 551 for (int idx = 0; idx < current.length; idx++) { 552 if (best[idx] != null && best[idx].getAssignments() != null && best[idx].isCourseRequest()) { 553 bestSelectedSections += best[idx].percentSelectedSameSection(); 554 bestSelectedConfigs += best[idx].percentSelectedSameConfig(); 555 if (idx >= maxIdx) { 556 bestSelectedSections -= 1.0; 557 bestSelectedConfigs -= 1.0; 558 } 559 } 560 if (current[idx] != null && idx < maxIdx && current[idx].getAssignments() != null && current[idx].isCourseRequest()) { 561 currentSelectedSections += current[idx].percentSelectedSameSection(); 562 currentSelectedConfigs += current[idx].percentSelectedSameConfig(); 563 } 564 } 565 if (0.3 * currentSelectedConfigs + 0.7 * currentSelectedSections > 0.3 * bestSelectedConfigs + 0.7 * bestSelectedSections) return true; 566 if (0.3 * bestSelectedConfigs + 0.7 * bestSelectedSections > 0.3 * currentSelectedConfigs + 0.7 * currentSelectedSections) return false; 567 568 // 4. avoid time overlaps 569 if (getModel().getTimeOverlaps() != null) { 570 int bestTimeOverlaps = 0, currentTimeOverlaps = 0; 571 for (int idx = 0; idx < current.length; idx++) { 572 if (best[idx] != null) { 573 for (int x = 0; x < idx; x++) { 574 if (best[x] != null) 575 bestTimeOverlaps += getModel().getTimeOverlaps().nrConflicts(best[x], best[idx]); 576 else if (getStudent().getRequests().get(x) instanceof FreeTimeRequest) 577 bestTimeOverlaps += getModel().getTimeOverlaps() 578 .nrConflicts( 579 ((FreeTimeRequest) getStudent().getRequests().get(x)).createEnrollment(), 580 best[idx]); 581 } 582 } 583 if (current[idx] != null && idx < maxIdx) { 584 for (int x = 0; x < idx; x++) { 585 if (current[x] != null) 586 currentTimeOverlaps += getModel().getTimeOverlaps().nrConflicts(current[x], current[idx]); 587 else if (getStudent().getRequests().get(x) instanceof FreeTimeRequest) 588 currentTimeOverlaps += getModel().getTimeOverlaps().nrConflicts( 589 ((FreeTimeRequest) getStudent().getRequests().get(x)).createEnrollment(), 590 current[idx]); 591 } 592 } 593 } 594 if (currentTimeOverlaps < bestTimeOverlaps) 595 return true; 596 if (bestTimeOverlaps < currentTimeOverlaps) 597 return false; 598 } 599 600 // 5. avoid distance conflicts 601 if (getModel().getDistanceConflict() != null) { 602 int bestDistanceConf = 0, currentDistanceConf = 0; 603 for (int idx = 0; idx < current.length; idx++) { 604 if (best[idx] != null) { 605 for (int x = 0; x < idx; x++) { 606 if (best[x] != null) 607 bestDistanceConf += getModel().getDistanceConflict().nrConflicts(best[x], best[idx]); 608 } 609 } 610 if (current[idx] != null && idx < maxIdx) { 611 for (int x = 0; x < idx; x++) { 612 if (current[x] != null) 613 currentDistanceConf += getModel().getDistanceConflict().nrConflicts(current[x], 614 current[idx]); 615 } 616 } 617 } 618 if (currentDistanceConf < bestDistanceConf) 619 return true; 620 if (bestDistanceConf < currentDistanceConf) 621 return false; 622 } 623 624 // 6. avoid no-time sections 625 int bestNoTime = 0, currentNoTime = 0; 626 for (int idx = 0; idx < current.length; idx++) { 627 if (best[idx] != null) { 628 for (Section section : best[idx].getSections()) 629 if (section.getTime() == null) 630 bestNoTime++; 631 } 632 if (current[idx] != null && idx < maxIdx) { 633 for (Section section : current[idx].getSections()) 634 if (section.getTime() == null) 635 currentNoTime++; 636 } 637 } 638 if (currentNoTime < bestNoTime) 639 return true; 640 if (bestNoTime < currentNoTime) 641 return false; 642 643 // 7. balance sections 644 double bestUnavailableSize = 0.0, currentUnavailableSize = 0.0; 645 int bestAltSectionsWithLimit = 0, currentAltSectionsWithLimit = 0; 646 for (int idx = 0; idx < current.length; idx++) { 647 if (best[idx] != null) { 648 for (Section section : best[idx].getSections()) { 649 Subpart subpart = section.getSubpart(); 650 // skip unlimited and single section subparts 651 if (subpart.getSections().size() <= 1 || subpart.getLimit() <= 0) 652 continue; 653 // average size 654 double averageSize = ((double) subpart.getLimit()) / subpart.getSections().size(); 655 // section is below average 656 if (section.getLimit() < averageSize) 657 bestUnavailableSize += (averageSize - section.getLimit()) / averageSize; 658 bestAltSectionsWithLimit++; 659 } 660 } 661 if (current[idx] != null && idx < maxIdx) { 662 for (Section section : current[idx].getSections()) { 663 Subpart subpart = section.getSubpart(); 664 // skip unlimited and single section subparts 665 if (subpart.getSections().size() <= 1 || subpart.getLimit() <= 0) 666 continue; 667 // average size 668 double averageSize = ((double) subpart.getLimit()) / subpart.getSections().size(); 669 // section is below average 670 if (section.getLimit() < averageSize) 671 currentUnavailableSize += (averageSize - section.getLimit()) / averageSize; 672 currentAltSectionsWithLimit++; 673 } 674 } 675 } 676 double bestUnavailableSizeFraction = (bestUnavailableSize > 0 ? bestUnavailableSize / bestAltSectionsWithLimit 677 : 0.0); 678 double currentUnavailableSizeFraction = (currentUnavailableSize > 0 ? currentUnavailableSize 679 / currentAltSectionsWithLimit : 0.0); 680 if (currentUnavailableSizeFraction < bestUnavailableSizeFraction) 681 return true; 682 if (bestUnavailableSizeFraction < currentUnavailableSizeFraction) 683 return false; 684 685 // 8. average penalty sections 686 double bestPenalty = 0.0, currentPenalty = 0.0; 687 for (int idx = 0; idx < current.length; idx++) { 688 if (best[idx] != null) { 689 for (Section section : best[idx].getSections()) 690 bestPenalty += section.getPenalty(); 691 if (idx >= maxIdx && best[idx].isCourseRequest()) 692 bestPenalty -= ((CourseRequest) best[idx].getRequest()).getMinPenalty(); 693 } 694 if (current[idx] != null && idx < maxIdx) { 695 for (Section section : current[idx].getSections()) 696 currentPenalty += section.getPenalty(); 697 } 698 } 699 if (currentPenalty < bestPenalty) 700 return true; 701 if (bestPenalty < currentPenalty) 702 return false; 703 704 return true; 705 } 706 707 @Override 708 public double getTotalWeight(Assignment<Request, Enrollment> assignment, Enrollment[] enrollemnts) { 709 if (enrollemnts == null) 710 return 0.0; 711 double value = 0.0; 712 for (int idx = 0; idx < enrollemnts.length; idx++) { 713 if (enrollemnts[idx] != null) 714 value += getWeight(assignment, enrollemnts[idx], getDistanceConflicts(enrollemnts, idx), 715 getTimeOverlappingConflicts(enrollemnts, idx)); 716 } 717 return value; 718 } 719 720 @Override 721 public int compare(Assignment<Request, Enrollment> assignment, Enrollment e1, Enrollment e2) { 722 // 1. alternativity 723 if (e1.getPriority() < e2.getPriority()) 724 return -1; 725 if (e1.getPriority() > e2.getPriority()) 726 return 1; 727 728 // 2. maximize number of penalties 729 double p1 = 0, p2 = 0; 730 for (Section section : e1.getSections()) 731 p1 += getModel().getOverExpected(assignment, section, e1.getRequest()); 732 for (Section section : e2.getSections()) 733 p2 += getModel().getOverExpected(assignment, section, e2.getRequest()); 734 if (p1 < p2) 735 return -1; 736 if (p2 < p1) 737 return 1; 738 739 // 3. maximize selection 740 if (e1.isCourseRequest()) { 741 Set<Section> preferred = getPreferredSections(e1.getRequest()); 742 if (preferred != null && !preferred.isEmpty()) { 743 int s1 = 0, s2 = 0; 744 for (Section section : e1.getSections()) 745 if (preferred.contains(section)) 746 s1++; 747 for (Section section : e2.getSections()) 748 if (preferred.contains(section)) 749 s2++; 750 if (s2 > s1) 751 return -1; 752 if (s1 > s2) 753 return 1; 754 } 755 } 756 757 // 3.5 maximize preferences 758 if (e1.isCourseRequest()) { 759 double s1 = 0.3 * e1.percentSelectedSameConfig() + 0.7 * e1.percentSelectedSameSection(); 760 double s2 = 0.3 * e2.percentSelectedSameConfig() + 0.7 * e2.percentSelectedSameSection(); 761 if (s1 > s2) return -1; 762 if (s2 < s1) return 1; 763 } 764 765 // 4. avoid time overlaps 766 if (getTimesToAvoid() == null) { 767 if (getModel().getTimeOverlaps() != null) { 768 int o1 = getModel().getTimeOverlaps().nrFreeTimeConflicts(e1); 769 int o2 = getModel().getTimeOverlaps().nrFreeTimeConflicts(e2); 770 if (o1 < o2) 771 return -1; 772 if (o2 < o1) 773 return 1; 774 } 775 } else { 776 if (e1.getRequest().equals(e2.getRequest()) && e1.isCourseRequest()) { 777 double o1 = 0.0, o2 = 0.0; 778 for (Section s : e1.getSections()) { 779 if (s.getTime() != null) 780 for (TimeToAvoid avoid : getTimesToAvoid()) { 781 if (avoid.priority() > e1.getPriority()) 782 o1 += avoid.overlap(s.getTime()); 783 } 784 } 785 for (Section s : e2.getSections()) { 786 if (s.getTime() != null) 787 for (TimeToAvoid avoid : getTimesToAvoid()) { 788 if (avoid.priority() > e2.getPriority()) 789 o2 += avoid.overlap(s.getTime()); 790 } 791 } 792 if (o1 < o2) 793 return -1; 794 if (o2 < o1) 795 return 1; 796 } 797 } 798 799 // 5. avoid distance conflicts 800 if (getModel().getDistanceConflict() != null) { 801 int c1 = getModel().getDistanceConflict().nrConflicts(e1); 802 int c2 = getModel().getDistanceConflict().nrConflicts(e2); 803 if (c1 < c2) 804 return -1; 805 if (c2 < c1) 806 return 1; 807 } 808 809 // 6. avoid no-time sections 810 int n1 = 0, n2 = 0; 811 for (Section section : e1.getSections()) 812 if (section.getTime() == null) 813 n1++; 814 for (Section section : e2.getSections()) 815 if (section.getTime() == null) 816 n2++; 817 if (n1 < n2) 818 return -1; 819 if (n2 < n1) 820 return 1; 821 822 // 7. balance sections 823 double u1 = 0.0, u2 = 0.0; 824 int a1 = 0, a2 = 0; 825 for (Section section : e1.getSections()) { 826 Subpart subpart = section.getSubpart(); 827 // skip unlimited and single section subparts 828 if (subpart.getSections().size() <= 1 || subpart.getLimit() <= 0) 829 continue; 830 // average size 831 double averageSize = ((double) subpart.getLimit()) / subpart.getSections().size(); 832 // section is below average 833 if (section.getLimit() < averageSize) 834 u1 += (averageSize - section.getLimit()) / averageSize; 835 a1++; 836 } 837 for (Section section : e2.getSections()) { 838 Subpart subpart = section.getSubpart(); 839 // skip unlimited and single section subparts 840 if (subpart.getSections().size() <= 1 || subpart.getLimit() <= 0) 841 continue; 842 // average size 843 double averageSize = ((double) subpart.getLimit()) / subpart.getSections().size(); 844 // section is below average 845 if (section.getLimit() < averageSize) 846 u2 += (averageSize - section.getLimit()) / averageSize; 847 a2++; 848 } 849 double f1 = (u1 > 0 ? u1 / a1 : 0.0); 850 double f2 = (u2 > 0 ? u2 / a2 : 0.0); 851 if (f1 < f2) 852 return -1; 853 if (f2 < f1) 854 return 1; 855 856 // 8. average penalty sections 857 double x1 = 0.0, x2 = 0.0; 858 for (Section section : e1.getSections()) 859 x1 += section.getPenalty(); 860 for (Section section : e2.getSections()) 861 x2 += section.getPenalty(); 862 if (x1 < x2) 863 return -1; 864 if (x2 < x1) 865 return 1; 866 867 return 0; 868 } 869 870 /** 871 * Time to be avoided. 872 */ 873 protected static class TimeToAvoid { 874 private TimeLocation iTime; 875 private double iPenalty; 876 private int iPriority; 877 878 public TimeToAvoid(TimeLocation time, int penalty, int priority) { 879 iTime = time; 880 iPenalty = penalty; 881 iPriority = priority; 882 } 883 884 public int priority() { 885 return iPriority; 886 } 887 888 public double overlap(TimeLocation time) { 889 if (time.hasIntersection(iTime)) { 890 return iPenalty * (time.nrSharedDays(iTime) * time.nrSharedDays(iTime)) 891 / (iTime.getNrMeetings() * iTime.getLength()); 892 } else { 893 return 0.0; 894 } 895 } 896 897 @Override 898 public String toString() { 899 return iTime.getLongName(true) + " (" + iPriority + "/" + iPenalty + ")"; 900 } 901 } 902}