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