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