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