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