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 if (unavailability.getTime() != null) 097 iTimesToAvoid.add(new TimeToAvoid(unavailability.getTime(), 1, Integer.MAX_VALUE)); 098 } 099 } 100 101 protected OnlineSectioningModel getModel() { 102 return iModel; 103 } 104 105 protected Student getStudent() { 106 return iStudent; 107 } 108 109 protected Set<Section> getPreferredSections(Request request) { 110 return iPreferredSections.get(request); 111 } 112 113 protected List<TimeToAvoid> getTimesToAvoid() { 114 return iTimesToAvoid; 115 } 116 117 /** 118 * Distance conflicts of idx-th assignment of the current schedule 119 */ 120 public Set<DistanceConflict.Conflict> getDistanceConflicts(Enrollment[] assignment, int idx) { 121 if (getModel().getDistanceConflict() == null || assignment[idx] == null) 122 return null; 123 Set<DistanceConflict.Conflict> dist = getModel().getDistanceConflict().conflicts(assignment[idx]); 124 for (int x = 0; x < idx; x++) 125 if (assignment[x] != null) 126 dist.addAll(getModel().getDistanceConflict().conflicts(assignment[x], assignment[idx])); 127 return dist; 128 } 129 130 /** 131 * Time overlapping conflicts of idx-th assignment of the current schedule 132 */ 133 public Set<TimeOverlapsCounter.Conflict> getTimeOverlappingConflicts(Enrollment[] assignment, int idx) { 134 if (getModel().getTimeOverlaps() == null || assignment[idx] == null) 135 return null; 136 Set<TimeOverlapsCounter.Conflict> overlaps = new HashSet<TimeOverlapsCounter.Conflict>(); 137 for (int x = 0; x < idx; x++) 138 if (assignment[x] != null) { 139 overlaps.addAll(getModel().getTimeOverlaps().conflicts(assignment[x], assignment[idx])); 140 } else if (getStudent().getRequests().get(x) instanceof FreeTimeRequest) 141 overlaps.addAll(getModel().getTimeOverlaps().conflicts( 142 ((FreeTimeRequest) getStudent().getRequests().get(x)).createEnrollment(), assignment[idx])); 143 overlaps.addAll(getModel().getTimeOverlaps().notAvailableTimeConflicts(assignment[idx])); 144 return overlaps; 145 } 146 147 /** 148 * Weight of an assignment. Unlike 149 * {@link StudentWeights#getWeight(Assignment, Enrollment, Set, Set)}, only count this 150 * side of distance conflicts and time overlaps. 151 **/ 152 protected double getWeight(Assignment<Request, Enrollment> assignment, Enrollment enrollment, 153 Set<DistanceConflict.Conflict> distanceConflicts, Set<TimeOverlapsCounter.Conflict> timeOverlappingConflicts) { 154 double weight = -getModel().getStudentWeights().getWeight(assignment, enrollment); 155 if (distanceConflicts != null) 156 for (DistanceConflict.Conflict c : distanceConflicts) { 157 Enrollment other = (c.getE1().equals(enrollment) ? c.getE2() : c.getE1()); 158 if (other.getRequest().getPriority() <= enrollment.getRequest().getPriority()) 159 weight += getModel().getStudentWeights().getDistanceConflictWeight(assignment, c); 160 } 161 if (timeOverlappingConflicts != null) 162 for (TimeOverlapsCounter.Conflict c : timeOverlappingConflicts) { 163 weight += getModel().getStudentWeights().getTimeOverlapConflictWeight(assignment, enrollment, c); 164 } 165 return enrollment.getRequest().getWeight() * weight; 166 } 167 168 public Request getRequest(int index) { 169 return (index < 0 || index >= getStudent().getRequests().size() ? null : getStudent().getRequests().get(index)); 170 } 171 172 public boolean isFreeTime(int index) { 173 Request r = getRequest(index); 174 return r != null && r instanceof FreeTimeRequest; 175 } 176 177 @Override 178 public int compare(Assignment<Request, Enrollment> assignment, Enrollment[] current, Enrollment[] best) { 179 if (best == null) 180 return -1; 181 182 // 0. best priority & alternativity ignoring free time requests 183 boolean ft = false; 184 for (int idx = 0; idx < current.length; idx++) { 185 if (isFreeTime(idx)) { 186 ft = true; 187 continue; 188 } 189 if (best[idx] != null && best[idx].getAssignments() != null) { 190 if (current[idx] == null || current[idx].getSections() == null) 191 return 1; // higher priority request assigned 192 if (best[idx].getPriority() < current[idx].getPriority()) 193 return 1; // less alternative request assigned 194 } else { 195 if (current[idx] != null && current[idx].getAssignments() != null) 196 return -1; // higher priority request assigned 197 } 198 } 199 200 // 0.1. allowed, but not available sections 201 int bestNotAvailable = 0, currentNotAvailable = 0; 202 for (int idx = 0; idx < current.length; idx++) { 203 if (best[idx] != null && best[idx].getAssignments() != null && best[idx].getRequest() instanceof CourseRequest && best[idx].getReservation() != null && best[idx].getReservation().canAssignOverLimit()) { 204 for (Section section: best[idx].getSections()) { 205 if (section.getLimit() == 0) 206 bestNotAvailable ++; 207 } 208 } 209 if (current[idx] != null && current[idx].getAssignments() != null && current[idx].getRequest() instanceof CourseRequest && current[idx].getReservation() != null && current[idx].getReservation().canAssignOverLimit()) { 210 for (Section section: current[idx].getSections()) { 211 if (section.getLimit() == 0) 212 currentNotAvailable ++; 213 } 214 } 215 } 216 if (bestNotAvailable > currentNotAvailable) return -1; 217 if (bestNotAvailable < currentNotAvailable) return 1; 218 219 // 0.5. avoid course time overlaps & unavailabilities 220 if (getModel().getTimeOverlaps() != null) { 221 int bestTimeOverlaps = 0, currentTimeOverlaps = 0; 222 for (int idx = 0; idx < current.length; idx++) { 223 if (best[idx] != null && best[idx].getAssignments() != null 224 && best[idx].getRequest() instanceof CourseRequest) { 225 for (int x = 0; x < idx; x++) { 226 if (best[x] != null && best[x].getAssignments() != null 227 && best[x].getRequest() instanceof CourseRequest) 228 bestTimeOverlaps += getModel().getTimeOverlaps().nrConflicts(best[x], best[idx]); 229 } 230 for (int x = 0; x < idx; x++) { 231 if (current[x] != null && current[x].getAssignments() != null 232 && current[x].getRequest() instanceof CourseRequest) 233 currentTimeOverlaps += getModel().getTimeOverlaps().nrConflicts(current[x], current[idx]); 234 } 235 } 236 } 237 for (int idx = 0; idx < current.length; idx++) { 238 if (best[idx] != null && best[idx].getAssignments() != null && best[idx].isCourseRequest()) { 239 bestTimeOverlaps += getModel().getTimeOverlaps().nrNotAvailableTimeConflicts(best[idx]); 240 } 241 if (current[idx] != null && current[idx].getAssignments() != null && current[idx].isCourseRequest()) { 242 currentTimeOverlaps += getModel().getTimeOverlaps().nrNotAvailableTimeConflicts(current[idx]); 243 } 244 } 245 if (currentTimeOverlaps < bestTimeOverlaps) 246 return -1; 247 if (bestTimeOverlaps < currentTimeOverlaps) 248 return 1; 249 } 250 251 // 1. minimize number of penalties 252 double bestPenalties = 0, currentPenalties = 0; 253 for (int idx = 0; idx < current.length; idx++) { 254 if (best[idx] != null && best[idx].getAssignments() != null && best[idx].isCourseRequest()) { 255 for (Section section : best[idx].getSections()) 256 bestPenalties += getModel().getOverExpected(assignment, section, best[idx].getRequest()); 257 for (Section section : current[idx].getSections()) 258 currentPenalties += getModel().getOverExpected(assignment, section, current[idx].getRequest()); 259 } 260 } 261 if (currentPenalties < bestPenalties) 262 return -1; 263 if (bestPenalties < currentPenalties) 264 return 1; 265 266 // 2. best priority & alternativity including free time requests 267 if (ft) { 268 for (int idx = 0; idx < current.length; idx++) { 269 if (best[idx] != null && best[idx].getAssignments() != null) { 270 if (current[idx] == null || current[idx].getSections() == null) 271 return 1; // higher priority request assigned 272 if (best[idx].getPriority() < current[idx].getPriority()) 273 return 1; // less alternative request assigned 274 } else { 275 if (current[idx] != null && current[idx].getAssignments() != null) 276 return -1; // higher priority request assigned 277 } 278 } 279 } 280 281 // 3. maximize selection 282 int bestSelected = 0, currentSelected = 0; 283 for (int idx = 0; idx < current.length; idx++) { 284 if (best[idx] != null && best[idx].getAssignments() != null && best[idx].isCourseRequest()) { 285 Set<Section> preferred = getPreferredSections(best[idx].getRequest()); 286 if (preferred != null && !preferred.isEmpty()) { 287 for (Section section : best[idx].getSections()) 288 if (preferred.contains(section)) 289 bestSelected++; 290 for (Section section : current[idx].getSections()) 291 if (preferred.contains(section)) 292 currentSelected++; 293 } 294 } 295 } 296 if (currentSelected > bestSelected) 297 return -1; 298 if (bestSelected > currentSelected) 299 return 1; 300 301 // 3.5 maximize preferences 302 double bestSelectedConfigs = 0, currentSelectedConfigs = 0; 303 double bestSelectedSections = 0, currentSelectedSections = 0; 304 for (int idx = 0; idx < current.length; idx++) { 305 if (best[idx] != null && best[idx].getAssignments() != null && best[idx].isCourseRequest()) { 306 bestSelectedSections += best[idx].percentSelectedSameSection(); 307 bestSelectedConfigs += best[idx].percentSelectedSameConfig(); 308 } 309 if (current[idx] != null && current[idx].getAssignments() != null && current[idx].isCourseRequest()) { 310 currentSelectedSections += current[idx].percentSelectedSameSection(); 311 currentSelectedConfigs += current[idx].percentSelectedSameConfig(); 312 } 313 } 314 if (0.3 * currentSelectedConfigs + 0.7 * currentSelectedSections > 0.3 * bestSelectedConfigs + 0.7 * bestSelectedSections) return -1; 315 if (0.3 * bestSelectedConfigs + 0.7 * bestSelectedSections > 0.3 * currentSelectedConfigs + 0.7 * currentSelectedSections) return 1; 316 317 // 4. avoid time overlaps 318 if (getModel().getTimeOverlaps() != null) { 319 int bestTimeOverlaps = 0, currentTimeOverlaps = 0; 320 for (int idx = 0; idx < current.length; idx++) { 321 if (best[idx] != null && best[idx].getAssignments() != null) { 322 for (int x = 0; x < idx; x++) { 323 if (best[x] != null && best[x].getAssignments() != null) 324 bestTimeOverlaps += getModel().getTimeOverlaps().nrConflicts(best[x], best[idx]); 325 else if (getStudent().getRequests().get(x) instanceof FreeTimeRequest) 326 bestTimeOverlaps += getModel().getTimeOverlaps() 327 .nrConflicts( 328 ((FreeTimeRequest) getStudent().getRequests().get(x)).createEnrollment(), 329 best[idx]); 330 } 331 for (int x = 0; x < idx; x++) { 332 if (current[x] != null && current[x].getAssignments() != null) 333 currentTimeOverlaps += getModel().getTimeOverlaps().nrConflicts(current[x], current[idx]); 334 else if (getStudent().getRequests().get(x) instanceof FreeTimeRequest) 335 currentTimeOverlaps += getModel().getTimeOverlaps().nrConflicts( 336 ((FreeTimeRequest) getStudent().getRequests().get(x)).createEnrollment(), 337 current[idx]); 338 } 339 } 340 } 341 for (int idx = 0; idx < current.length; idx++) { 342 if (best[idx] != null && best[idx].getAssignments() != null && best[idx].isCourseRequest()) { 343 bestTimeOverlaps += getModel().getTimeOverlaps().nrNotAvailableTimeConflicts(best[idx]); 344 } 345 if (current[idx] != null && current[idx].getAssignments() != null && current[idx].isCourseRequest()) { 346 currentTimeOverlaps += getModel().getTimeOverlaps().nrNotAvailableTimeConflicts(current[idx]); 347 } 348 } 349 if (currentTimeOverlaps < bestTimeOverlaps) 350 return -1; 351 if (bestTimeOverlaps < currentTimeOverlaps) 352 return 1; 353 } 354 355 // 5. avoid distance conflicts 356 if (getModel().getDistanceConflict() != null) { 357 int bestDistanceConf = 0, currentDistanceConf = 0; 358 for (int idx = 0; idx < current.length; idx++) { 359 if (best[idx] != null && best[idx].getAssignments() != null) { 360 for (int x = 0; x < idx; x++) { 361 if (best[x] != null && best[x].getAssignments() != null) 362 bestDistanceConf += getModel().getDistanceConflict().nrConflicts(best[x], best[idx]); 363 } 364 for (int x = 0; x < idx; x++) { 365 if (current[x] != null && current[x].getAssignments() != null) 366 currentDistanceConf += getModel().getDistanceConflict().nrConflicts(current[x], 367 current[idx]); 368 } 369 } 370 } 371 if (currentDistanceConf < bestDistanceConf) 372 return -1; 373 if (bestDistanceConf < currentDistanceConf) 374 return 1; 375 } 376 377 // 6. avoid no-time sections 378 int bestNoTime = 0, currentNoTime = 0; 379 for (int idx = 0; idx < current.length; idx++) { 380 if (best[idx] != null && best[idx].getAssignments() != null) { 381 for (Section section : best[idx].getSections()) 382 if (section.getTime() == null) 383 bestNoTime++; 384 for (Section section : current[idx].getSections()) 385 if (section.getTime() == null) 386 currentNoTime++; 387 } 388 } 389 if (currentNoTime < bestNoTime) 390 return -1; 391 if (bestNoTime < currentNoTime) 392 return 1; 393 394 // 7. balance sections 395 double bestUnavailableSize = 0.0, currentUnavailableSize = 0.0; 396 int bestAltSectionsWithLimit = 0, currentAltSectionsWithLimit = 0; 397 for (int idx = 0; idx < current.length; idx++) { 398 if (best[idx] != null && best[idx].getAssignments() != null) { 399 for (Section section : best[idx].getSections()) { 400 Subpart subpart = section.getSubpart(); 401 // skip unlimited and single section subparts 402 if (subpart.getSections().size() <= 1 || subpart.getLimit() <= 0) 403 continue; 404 // average size 405 double averageSize = ((double) subpart.getLimit()) / subpart.getSections().size(); 406 // section is below average 407 if (section.getLimit() < averageSize) 408 bestUnavailableSize += (averageSize - section.getLimit()) / averageSize; 409 bestAltSectionsWithLimit++; 410 } 411 for (Section section : current[idx].getSections()) { 412 Subpart subpart = section.getSubpart(); 413 // skip unlimited and single section subparts 414 if (subpart.getSections().size() <= 1 || subpart.getLimit() <= 0) 415 continue; 416 // average size 417 double averageSize = ((double) subpart.getLimit()) / subpart.getSections().size(); 418 // section is below average 419 if (section.getLimit() < averageSize) 420 currentUnavailableSize += (averageSize - section.getLimit()) / averageSize; 421 currentAltSectionsWithLimit++; 422 } 423 } 424 } 425 double bestUnavailableSizeFraction = (bestUnavailableSize > 0 ? bestUnavailableSize / bestAltSectionsWithLimit 426 : 0.0); 427 double currentUnavailableSizeFraction = (currentUnavailableSize > 0 ? currentUnavailableSize 428 / currentAltSectionsWithLimit : 0.0); 429 if (currentUnavailableSizeFraction < bestUnavailableSizeFraction) 430 return -1; 431 if (bestUnavailableSizeFraction < currentUnavailableSizeFraction) 432 return 1; 433 434 // 8. average penalty sections 435 double bestPenalty = 0.0, currentPenalty = 0.0; 436 for (int idx = 0; idx < current.length; idx++) { 437 if (best[idx] != null && best[idx].getAssignments() != null) { 438 for (Section section : best[idx].getSections()) 439 bestPenalty += section.getPenalty() / best[idx].getSections().size(); 440 for (Section section : current[idx].getSections()) 441 currentPenalty += section.getPenalty() / current[idx].getSections().size(); 442 } 443 } 444 if (currentPenalty < bestPenalty) 445 return -1; 446 if (bestPenalty < currentPenalty) 447 return 1; 448 449 return 0; 450 } 451 452 @Override 453 public boolean canImprove(Assignment<Request, Enrollment> assignment, int maxIdx, Enrollment[] current, 454 Enrollment[] best) { 455 // 0. best priority & alternativity ignoring free time requests 456 int alt = 0; 457 boolean ft = false; 458 for (int idx = 0; idx < current.length; idx++) { 459 if (isFreeTime(idx)) { 460 ft = true; 461 continue; 462 } 463 Request request = getRequest(idx); 464 if (idx < maxIdx) { 465 if (best[idx] != null) { 466 if (current[idx] == null) 467 return false; // higher priority request assigned 468 if (best[idx].getPriority() < current[idx].getPriority()) 469 return false; // less alternative request assigned 470 if (request.isAlternative()) 471 alt--; 472 } else { 473 if (current[idx] != null) 474 return true; // higher priority request assigned 475 if (!request.isAlternative()) 476 alt++; 477 } 478 } else { 479 if (best[idx] != null) { 480 if (best[idx].getPriority() > 0) 481 return true; // alternativity can be improved 482 } else { 483 if (!request.isAlternative() || alt > 0) 484 return true; // priority can be improved 485 } 486 } 487 } 488 489 // 0.1. allowed, but not available sections 490 int notAvailable = 0; 491 for (int idx = 0; idx < current.length; idx++) { 492 if (best[idx] != null && best[idx].getAssignments() != null && best[idx].getRequest() instanceof CourseRequest && best[idx].getReservation() != null && best[idx].getReservation().canAssignOverLimit()) { 493 for (Section section: best[idx].getSections()) { 494 if (section.getLimit() == 0) 495 notAvailable ++; 496 } 497 } 498 if (idx < maxIdx && current[idx] != null && current[idx].getAssignments() != null && current[idx].getRequest() instanceof CourseRequest && current[idx].getReservation() != null && current[idx].getReservation().canAssignOverLimit()) { 499 for (Section section: current[idx].getSections()) { 500 if (section.getLimit() == 0) 501 notAvailable --; 502 } 503 } 504 } 505 if (notAvailable > 0) { 506 return true; 507 } 508 509 // 0.5. avoid course time overlaps & unavailability overlaps 510 if (getModel().getTimeOverlaps() != null) { 511 int bestTimeOverlaps = 0, currentTimeOverlaps = 0; 512 for (int idx = 0; idx < current.length; idx++) { 513 if (best[idx] != null && best[idx].getRequest() instanceof CourseRequest) { 514 for (int x = 0; x < idx; x++) { 515 if (best[x] != null && best[x].getRequest() instanceof CourseRequest) 516 bestTimeOverlaps += getModel().getTimeOverlaps().nrConflicts(best[x], best[idx]); 517 } 518 } 519 if (current[idx] != null && idx < maxIdx && current[idx].getRequest() instanceof CourseRequest) { 520 for (int x = 0; x < idx; x++) { 521 if (current[x] != null && current[x].getRequest() instanceof CourseRequest) 522 currentTimeOverlaps += getModel().getTimeOverlaps().nrConflicts(current[x], current[idx]); 523 } 524 } 525 } 526 for (int idx = 0; idx < current.length; idx++) { 527 if (best[idx] != null && best[idx].getAssignments() != null && best[idx].isCourseRequest()) { 528 bestTimeOverlaps += getModel().getTimeOverlaps().nrNotAvailableTimeConflicts(best[idx]); 529 } 530 if (current[idx] != null && idx < maxIdx && current[idx].getAssignments() != null && current[idx].isCourseRequest()) { 531 currentTimeOverlaps += getModel().getTimeOverlaps().nrNotAvailableTimeConflicts(current[idx]); 532 } 533 } 534 if (currentTimeOverlaps < bestTimeOverlaps) 535 return true; 536 if (bestTimeOverlaps < currentTimeOverlaps) 537 return false; 538 } 539 540 // 1. maximize number of penalties 541 double bestPenalties = 0, currentPenalties = 0; 542 for (int idx = 0; idx < current.length; idx++) { 543 if (best[idx] != null) { 544 for (Section section : best[idx].getSections()) 545 bestPenalties += getModel().getOverExpected(assignment, section, best[idx].getRequest()); 546 } 547 if (current[idx] != null && idx < maxIdx) { 548 for (Section section : current[idx].getSections()) 549 currentPenalties += getModel().getOverExpected(assignment, section, current[idx].getRequest()); 550 } 551 } 552 if (currentPenalties < bestPenalties) 553 return true; 554 if (bestPenalties < currentPenalties) 555 return false; 556 557 // 2. best priority & alternativity including free times 558 if (ft) { 559 alt = 0; 560 for (int idx = 0; idx < current.length; idx++) { 561 Request request = getStudent().getRequests().get(idx); 562 if (idx < maxIdx) { 563 if (best[idx] != null) { 564 if (current[idx] == null) 565 return false; // higher priority request assigned 566 if (best[idx].getPriority() < current[idx].getPriority()) 567 return false; // less alternative request assigned 568 if (request.isAlternative()) 569 alt--; 570 } else { 571 if (current[idx] != null) 572 return true; // higher priority request assigned 573 if (request instanceof CourseRequest && !request.isAlternative()) 574 alt++; 575 } 576 } else { 577 if (best[idx] != null) { 578 if (best[idx].getPriority() > 0) 579 return true; // alternativity can be improved 580 } else { 581 if (!request.isAlternative() || alt > 0) 582 return true; // priority can be improved 583 } 584 } 585 } 586 } 587 588 // 3. maximize selection 589 int bestSelected = 0, currentSelected = 0; 590 for (int idx = 0; idx < current.length; idx++) { 591 if (best[idx] != null && best[idx].isCourseRequest()) { 592 Set<Section> preferred = getPreferredSections(best[idx].getRequest()); 593 if (preferred != null && !preferred.isEmpty()) { 594 for (Section section : best[idx].getSections()) 595 if (preferred.contains(section)) { 596 if (idx < maxIdx) 597 bestSelected++; 598 } else if (idx >= maxIdx) 599 bestSelected--; 600 } 601 } 602 if (current[idx] != null && idx < maxIdx && current[idx].isCourseRequest()) { 603 Set<Section> preferred = getPreferredSections(current[idx].getRequest()); 604 if (preferred != null && !preferred.isEmpty()) { 605 for (Section section : current[idx].getSections()) 606 if (preferred.contains(section)) 607 currentSelected++; 608 } 609 } 610 } 611 if (currentSelected > bestSelected) 612 return true; 613 if (bestSelected > currentSelected) 614 return false; 615 616 // 3.5 maximize preferences 617 double bestSelectedConfigs = 0, currentSelectedConfigs = 0; 618 double bestSelectedSections = 0, currentSelectedSections = 0; 619 for (int idx = 0; idx < current.length; idx++) { 620 if (best[idx] != null && best[idx].getAssignments() != null && best[idx].isCourseRequest()) { 621 bestSelectedSections += best[idx].percentSelectedSameSection(); 622 bestSelectedConfigs += best[idx].percentSelectedSameConfig(); 623 if (idx >= maxIdx) { 624 bestSelectedSections -= 1.0; 625 bestSelectedConfigs -= 1.0; 626 } 627 } 628 if (current[idx] != null && idx < maxIdx && current[idx].getAssignments() != null && current[idx].isCourseRequest()) { 629 currentSelectedSections += current[idx].percentSelectedSameSection(); 630 currentSelectedConfigs += current[idx].percentSelectedSameConfig(); 631 } 632 } 633 if (0.3 * currentSelectedConfigs + 0.7 * currentSelectedSections > 0.3 * bestSelectedConfigs + 0.7 * bestSelectedSections) return true; 634 if (0.3 * bestSelectedConfigs + 0.7 * bestSelectedSections > 0.3 * currentSelectedConfigs + 0.7 * currentSelectedSections) return false; 635 636 // 4. avoid time overlaps 637 if (getModel().getTimeOverlaps() != null) { 638 int bestTimeOverlaps = 0, currentTimeOverlaps = 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 bestTimeOverlaps += getModel().getTimeOverlaps().nrConflicts(best[x], best[idx]); 644 else if (getStudent().getRequests().get(x) instanceof FreeTimeRequest) 645 bestTimeOverlaps += getModel().getTimeOverlaps() 646 .nrConflicts( 647 ((FreeTimeRequest) getStudent().getRequests().get(x)).createEnrollment(), 648 best[idx]); 649 } 650 } 651 if (current[idx] != null && idx < maxIdx) { 652 for (int x = 0; x < idx; x++) { 653 if (current[x] != null) 654 currentTimeOverlaps += getModel().getTimeOverlaps().nrConflicts(current[x], current[idx]); 655 else if (getStudent().getRequests().get(x) instanceof FreeTimeRequest) 656 currentTimeOverlaps += getModel().getTimeOverlaps().nrConflicts( 657 ((FreeTimeRequest) getStudent().getRequests().get(x)).createEnrollment(), 658 current[idx]); 659 } 660 } 661 } 662 for (int idx = 0; idx < current.length; idx++) { 663 if (best[idx] != null && best[idx].getAssignments() != null && best[idx].isCourseRequest()) { 664 bestTimeOverlaps += getModel().getTimeOverlaps().nrNotAvailableTimeConflicts(best[idx]); 665 } 666 if (current[idx] != null && idx < maxIdx && current[idx].getAssignments() != null && current[idx].isCourseRequest()) { 667 currentTimeOverlaps += getModel().getTimeOverlaps().nrNotAvailableTimeConflicts(current[idx]); 668 } 669 } 670 if (currentTimeOverlaps < bestTimeOverlaps) 671 return true; 672 if (bestTimeOverlaps < currentTimeOverlaps) 673 return false; 674 } 675 676 // 5. avoid distance conflicts 677 if (getModel().getDistanceConflict() != null) { 678 int bestDistanceConf = 0, currentDistanceConf = 0; 679 for (int idx = 0; idx < current.length; idx++) { 680 if (best[idx] != null) { 681 for (int x = 0; x < idx; x++) { 682 if (best[x] != null) 683 bestDistanceConf += getModel().getDistanceConflict().nrConflicts(best[x], best[idx]); 684 } 685 } 686 if (current[idx] != null && idx < maxIdx) { 687 for (int x = 0; x < idx; x++) { 688 if (current[x] != null) 689 currentDistanceConf += getModel().getDistanceConflict().nrConflicts(current[x], 690 current[idx]); 691 } 692 } 693 } 694 if (currentDistanceConf < bestDistanceConf) 695 return true; 696 if (bestDistanceConf < currentDistanceConf) 697 return false; 698 } 699 700 // 6. avoid no-time sections 701 int bestNoTime = 0, currentNoTime = 0; 702 for (int idx = 0; idx < current.length; idx++) { 703 if (best[idx] != null) { 704 for (Section section : best[idx].getSections()) 705 if (section.getTime() == null) 706 bestNoTime++; 707 } 708 if (current[idx] != null && idx < maxIdx) { 709 for (Section section : current[idx].getSections()) 710 if (section.getTime() == null) 711 currentNoTime++; 712 } 713 } 714 if (currentNoTime < bestNoTime) 715 return true; 716 if (bestNoTime < currentNoTime) 717 return false; 718 719 // 7. balance sections 720 double bestUnavailableSize = 0.0, currentUnavailableSize = 0.0; 721 int bestAltSectionsWithLimit = 0, currentAltSectionsWithLimit = 0; 722 for (int idx = 0; idx < current.length; idx++) { 723 if (best[idx] != null) { 724 for (Section section : best[idx].getSections()) { 725 Subpart subpart = section.getSubpart(); 726 // skip unlimited and single section subparts 727 if (subpart.getSections().size() <= 1 || subpart.getLimit() <= 0) 728 continue; 729 // average size 730 double averageSize = ((double) subpart.getLimit()) / subpart.getSections().size(); 731 // section is below average 732 if (section.getLimit() < averageSize) 733 bestUnavailableSize += (averageSize - section.getLimit()) / averageSize; 734 bestAltSectionsWithLimit++; 735 } 736 } 737 if (current[idx] != null && idx < maxIdx) { 738 for (Section section : current[idx].getSections()) { 739 Subpart subpart = section.getSubpart(); 740 // skip unlimited and single section subparts 741 if (subpart.getSections().size() <= 1 || subpart.getLimit() <= 0) 742 continue; 743 // average size 744 double averageSize = ((double) subpart.getLimit()) / subpart.getSections().size(); 745 // section is below average 746 if (section.getLimit() < averageSize) 747 currentUnavailableSize += (averageSize - section.getLimit()) / averageSize; 748 currentAltSectionsWithLimit++; 749 } 750 } 751 } 752 double bestUnavailableSizeFraction = (bestUnavailableSize > 0 ? bestUnavailableSize / bestAltSectionsWithLimit 753 : 0.0); 754 double currentUnavailableSizeFraction = (currentUnavailableSize > 0 ? currentUnavailableSize 755 / currentAltSectionsWithLimit : 0.0); 756 if (currentUnavailableSizeFraction < bestUnavailableSizeFraction) 757 return true; 758 if (bestUnavailableSizeFraction < currentUnavailableSizeFraction) 759 return false; 760 761 // 8. average penalty sections 762 double bestPenalty = 0.0, currentPenalty = 0.0; 763 for (int idx = 0; idx < current.length; idx++) { 764 if (best[idx] != null) { 765 for (Section section : best[idx].getSections()) 766 bestPenalty += section.getPenalty() / best[idx].getSections().size(); 767 if (idx >= maxIdx && best[idx].isCourseRequest()) 768 bestPenalty -= ((CourseRequest) best[idx].getRequest()).getMinPenalty(); 769 } 770 if (current[idx] != null && idx < maxIdx) { 771 for (Section section : current[idx].getSections()) 772 currentPenalty += section.getPenalty() / current[idx].getSections().size(); 773 } 774 } 775 if (currentPenalty < bestPenalty) 776 return true; 777 if (bestPenalty < currentPenalty) 778 return false; 779 780 return true; 781 } 782 783 @Override 784 public double getTotalWeight(Assignment<Request, Enrollment> assignment, Enrollment[] enrollemnts) { 785 if (enrollemnts == null) 786 return 0.0; 787 double value = 0.0; 788 for (int idx = 0; idx < enrollemnts.length; idx++) { 789 if (enrollemnts[idx] != null) 790 value += getWeight(assignment, enrollemnts[idx], getDistanceConflicts(enrollemnts, idx), 791 getTimeOverlappingConflicts(enrollemnts, idx)); 792 } 793 return value; 794 } 795 796 @Override 797 public int compare(Assignment<Request, Enrollment> assignment, Enrollment e1, Enrollment e2) { 798 // 1. alternativity 799 if (e1.getPriority() < e2.getPriority()) 800 return -1; 801 if (e1.getPriority() > e2.getPriority()) 802 return 1; 803 804 // 1.5 not available sections 805 int na1 = 0, na2 = 0; 806 for (Section section: e1.getSections()) 807 if (section.getLimit() == 0) na1++; 808 for (Section section: e2.getSections()) 809 if (section.getLimit() == 0) na2++; 810 if (na1 < na2) return -1; 811 if (na2 > na1) return -1; 812 813 // 2. maximize number of penalties 814 double p1 = 0, p2 = 0; 815 for (Section section : e1.getSections()) 816 p1 += getModel().getOverExpected(assignment, section, e1.getRequest()); 817 for (Section section : e2.getSections()) 818 p2 += getModel().getOverExpected(assignment, section, e2.getRequest()); 819 if (p1 < p2) 820 return -1; 821 if (p2 < p1) 822 return 1; 823 824 // 3. maximize selection 825 if (e1.isCourseRequest()) { 826 Set<Section> preferred = getPreferredSections(e1.getRequest()); 827 if (preferred != null && !preferred.isEmpty()) { 828 int s1 = 0, s2 = 0; 829 for (Section section : e1.getSections()) 830 if (preferred.contains(section)) 831 s1++; 832 for (Section section : e2.getSections()) 833 if (preferred.contains(section)) 834 s2++; 835 if (s2 > s1) 836 return -1; 837 if (s1 > s2) 838 return 1; 839 } 840 } 841 842 // 3.5 maximize preferences 843 if (e1.isCourseRequest()) { 844 double s1 = 0.3 * e1.percentSelectedSameConfig() + 0.7 * e1.percentSelectedSameSection(); 845 double s2 = 0.3 * e2.percentSelectedSameConfig() + 0.7 * e2.percentSelectedSameSection(); 846 if (s1 > s2) return -1; 847 if (s2 > s1) return 1; 848 } 849 850 // 4. avoid time overlaps 851 if (getTimesToAvoid() == null) { 852 if (getModel().getTimeOverlaps() != null) { 853 int o1 = getModel().getTimeOverlaps().nrFreeTimeConflicts(e1) + getModel().getTimeOverlaps().nrNotAvailableTimeConflicts(e1); 854 int o2 = getModel().getTimeOverlaps().nrFreeTimeConflicts(e2) + getModel().getTimeOverlaps().nrNotAvailableTimeConflicts(e2); 855 if (o1 < o2) 856 return -1; 857 if (o2 < o1) 858 return 1; 859 } 860 } else { 861 if (e1.getRequest().equals(e2.getRequest()) && e1.isCourseRequest()) { 862 double o1 = 0.0, o2 = 0.0; 863 for (Section s : e1.getSections()) { 864 if (s.getTime() != null) 865 for (TimeToAvoid avoid : getTimesToAvoid()) { 866 if (avoid.priority() > e1.getPriority()) 867 o1 += avoid.overlap(s.getTime()); 868 } 869 } 870 for (Section s : e2.getSections()) { 871 if (s.getTime() != null) 872 for (TimeToAvoid avoid : getTimesToAvoid()) { 873 if (avoid.priority() > e2.getPriority()) 874 o2 += avoid.overlap(s.getTime()); 875 } 876 } 877 if (o1 < o2) 878 return -1; 879 if (o2 < o1) 880 return 1; 881 } 882 } 883 884 // 5. avoid distance conflicts 885 if (getModel().getDistanceConflict() != null) { 886 int c1 = getModel().getDistanceConflict().nrConflicts(e1); 887 int c2 = getModel().getDistanceConflict().nrConflicts(e2); 888 if (c1 < c2) 889 return -1; 890 if (c2 < c1) 891 return 1; 892 } 893 894 // 6. avoid no-time sections 895 int n1 = 0, n2 = 0; 896 for (Section section : e1.getSections()) 897 if (section.getTime() == null) 898 n1++; 899 for (Section section : e2.getSections()) 900 if (section.getTime() == null) 901 n2++; 902 if (n1 < n2) 903 return -1; 904 if (n2 < n1) 905 return 1; 906 907 // 7. balance sections 908 double u1 = 0.0, u2 = 0.0; 909 int a1 = 0, a2 = 0; 910 for (Section section : e1.getSections()) { 911 Subpart subpart = section.getSubpart(); 912 // skip unlimited and single section subparts 913 if (subpart.getSections().size() <= 1 || subpart.getLimit() <= 0) 914 continue; 915 // average size 916 double averageSize = ((double) subpart.getLimit()) / subpart.getSections().size(); 917 // section is below average 918 if (section.getLimit() < averageSize) 919 u1 += (averageSize - section.getLimit()) / averageSize; 920 a1++; 921 } 922 for (Section section : e2.getSections()) { 923 Subpart subpart = section.getSubpart(); 924 // skip unlimited and single section subparts 925 if (subpart.getSections().size() <= 1 || subpart.getLimit() <= 0) 926 continue; 927 // average size 928 double averageSize = ((double) subpart.getLimit()) / subpart.getSections().size(); 929 // section is below average 930 if (section.getLimit() < averageSize) 931 u2 += (averageSize - section.getLimit()) / averageSize; 932 a2++; 933 } 934 double f1 = (u1 > 0 ? u1 / a1 : 0.0); 935 double f2 = (u2 > 0 ? u2 / a2 : 0.0); 936 if (f1 < f2) 937 return -1; 938 if (f2 < f1) 939 return 1; 940 941 // 8. average penalty sections 942 double x1 = 0.0, x2 = 0.0; 943 for (Section section : e1.getSections()) 944 x1 += section.getPenalty() / e1.getSections().size(); 945 for (Section section : e2.getSections()) 946 x2 += section.getPenalty() / e2.getSections().size(); 947 if (x1 < x2) 948 return -1; 949 if (x2 < x1) 950 return 1; 951 952 return 0; 953 } 954 955 /** 956 * Time to be avoided. 957 */ 958 protected static class TimeToAvoid { 959 private TimeLocation iTime; 960 private double iPenalty; 961 private int iPriority; 962 963 public TimeToAvoid(TimeLocation time, int penalty, int priority) { 964 iTime = time; 965 iPenalty = penalty; 966 iPriority = priority; 967 } 968 969 public int priority() { 970 return iPriority; 971 } 972 973 public double overlap(TimeLocation time) { 974 if (time.hasIntersection(iTime)) { 975 return iPenalty * (time.nrSharedDays(iTime) * time.nrSharedDays(iTime)) 976 / (iTime.getNrMeetings() * iTime.getLength()); 977 } else { 978 return 0.0; 979 } 980 } 981 982 @Override 983 public String toString() { 984 return iTime.getLongName(true) + " (" + iPriority + "/" + iPenalty + ")"; 985 } 986 } 987}