001package org.cpsolver.studentsct.online.selection; 002 003import java.util.Hashtable; 004import java.util.Set; 005 006import org.cpsolver.ifs.assignment.Assignment; 007import org.cpsolver.studentsct.model.CourseRequest; 008import org.cpsolver.studentsct.model.Enrollment; 009import org.cpsolver.studentsct.model.FreeTimeRequest; 010import org.cpsolver.studentsct.model.Request; 011import org.cpsolver.studentsct.model.Section; 012import org.cpsolver.studentsct.model.Student; 013import org.cpsolver.studentsct.model.Subpart; 014import org.cpsolver.studentsct.online.OnlineSectioningModel; 015 016/** 017* Equal weighting multi-criteria selection criterion. Much like the {@link OnlineSectioningCriterion}, but 018* course request priorities are ignored. Most complete solution is preferred instead. 019* 020* @version StudentSct 1.3 (Student Sectioning)<br> 021* Copyright (C) 2014 Tomas Muller<br> 022* <a href="mailto:muller@unitime.org">muller@unitime.org</a><br> 023* <a href="http://muller.unitime.org">http://muller.unitime.org</a><br> 024* <br> 025* This library is free software; you can redistribute it and/or modify 026* it under the terms of the GNU Lesser General Public License as 027* published by the Free Software Foundation; either version 3 of the 028* License, or (at your option) any later version. <br> 029* <br> 030* This library is distributed in the hope that it will be useful, but 031* WITHOUT ANY WARRANTY; without even the implied warranty of 032* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 033* Lesser General Public License for more details. <br> 034* <br> 035* You should have received a copy of the GNU Lesser General Public 036* License along with this library; if not see <a 037* href='http://www.gnu.org/licenses'>http://www.gnu.org/licenses</a>. 038* 039*/ 040public class EqualWeightCriterion extends OnlineSectioningCriterion { 041 042 public EqualWeightCriterion(Student student, OnlineSectioningModel model, 043 Assignment<Request, Enrollment> assignment, Hashtable<CourseRequest, Set<Section>> preferredSections) { 044 super(student, model, assignment, preferredSections); 045 } 046 047 @Override 048 public int compare(Assignment<Request, Enrollment> assignment, Enrollment[] current, Enrollment[] best) { 049 if (best == null) 050 return -1; 051 052 // 0. best number of assigned course requests (including alternativity & 053 // priority) 054 int currentAssignedCourseReq = 0, bestAssignedCourseReq = 0; 055 int currentAssignedRequests = 0, bestAssignedRequests = 0; 056 int currentAssignedPriority = 0, bestAssignedPriority = 0; 057 int currentAssignedAlternativity = 0, bestAssignedAlternativity = 0; 058 for (int idx = 0; idx < current.length; idx++) { 059 if (current[idx] != null && current[idx].getAssignments() != null) { 060 currentAssignedRequests++; 061 if (current[idx].isCourseRequest()) 062 currentAssignedCourseReq++; 063 currentAssignedPriority += current[idx].getPriority() * current[idx].getPriority(); 064 currentAssignedAlternativity += (current[idx].getRequest().isAlternative() ? 1 : 0); 065 } 066 if (best[idx] != null && best[idx].getAssignments() != null) { 067 bestAssignedRequests++; 068 if (best[idx].isCourseRequest()) 069 bestAssignedCourseReq++; 070 bestAssignedPriority += best[idx].getPriority() * best[idx].getPriority(); 071 bestAssignedAlternativity += (best[idx].getRequest().isAlternative() ? 1 : 0); 072 } 073 } 074 if (currentAssignedCourseReq > bestAssignedCourseReq) 075 return -1; 076 if (bestAssignedCourseReq > currentAssignedCourseReq) 077 return 1; 078 if (currentAssignedPriority < bestAssignedPriority) 079 return -1; 080 if (bestAssignedPriority < currentAssignedPriority) 081 return 1; 082 if (currentAssignedAlternativity < bestAssignedAlternativity) 083 return -1; 084 if (bestAssignedAlternativity < currentAssignedAlternativity) 085 return 1; 086 087 // 0.5. avoid course overlaps 088 if (getModel().getTimeOverlaps() != null) { 089 int bestTimeOverlaps = 0, currentTimeOverlaps = 0; 090 for (int idx = 0; idx < current.length; idx++) { 091 if (best[idx] != null && best[idx].getAssignments() != null && best[idx].getRequest() instanceof CourseRequest) { 092 for (int x = 0; x < idx; x++) { 093 if (best[x] != null && best[x].getAssignments() != null 094 && best[x].getRequest() instanceof CourseRequest) 095 bestTimeOverlaps += getModel().getTimeOverlaps().nrConflicts(best[x], best[idx]); 096 } 097 } 098 if (current[idx] != null && current[idx].getAssignments() != null && current[idx].getRequest() instanceof CourseRequest) { 099 for (int x = 0; x < idx; x++) { 100 if (current[x] != null && current[x].getAssignments() != null 101 && current[x].getRequest() instanceof CourseRequest) 102 currentTimeOverlaps += getModel().getTimeOverlaps().nrConflicts(current[x], current[idx]); 103 } 104 } 105 } 106 if (currentTimeOverlaps < bestTimeOverlaps) 107 return -1; 108 if (bestTimeOverlaps < currentTimeOverlaps) 109 return 1; 110 } 111 112 // 1. minimize number of penalties 113 double bestPenalties = 0, currentPenalties = 0; 114 for (int idx = 0; idx < current.length; idx++) { 115 if (best[idx] != null && best[idx].getAssignments() != null && best[idx].isCourseRequest()) { 116 for (Section section : best[idx].getSections()) 117 bestPenalties += getModel().getOverExpected(assignment, section, best[idx].getRequest()); 118 } 119 if (current[idx] != null && current[idx].getAssignments() != null && current[idx].isCourseRequest()) { 120 for (Section section : current[idx].getSections()) 121 currentPenalties += getModel().getOverExpected(assignment, section, current[idx].getRequest()); 122 } 123 } 124 if (currentPenalties < bestPenalties) 125 return -1; 126 if (bestPenalties < currentPenalties) 127 return 1; 128 129 // 2. best number of assigned requests (including free time requests) 130 if (currentAssignedRequests > bestAssignedRequests) 131 return -1; 132 if (bestAssignedRequests > currentAssignedRequests) 133 return 1; 134 135 // 3. maximize selection 136 int bestSelected = 0, currentSelected = 0; 137 for (int idx = 0; idx < current.length; idx++) { 138 Set<Section> preferred = getPreferredSections(getRequest(idx)); 139 if (preferred != null && !preferred.isEmpty()) { 140 if (best[idx] != null && best[idx].getAssignments() != null && best[idx].isCourseRequest()) { 141 for (Section section : best[idx].getSections()) 142 if (preferred.contains(section)) 143 bestSelected++; 144 } 145 if (current[idx] != null && current[idx].getAssignments() != null && current[idx].isCourseRequest()) { 146 for (Section section : current[idx].getSections()) 147 if (preferred.contains(section)) 148 currentSelected++; 149 } 150 } 151 } 152 if (currentSelected > bestSelected) 153 return -1; 154 if (bestSelected > currentSelected) 155 return 1; 156 157 // 4. avoid time overlaps 158 if (getModel().getTimeOverlaps() != null) { 159 int bestTimeOverlaps = 0, currentTimeOverlaps = 0; 160 for (int idx = 0; idx < current.length; idx++) { 161 if (best[idx] != null && best[idx].getAssignments() != null) { 162 for (int x = 0; x < idx; x++) { 163 if (best[x] != null && best[x].getAssignments() != null) 164 bestTimeOverlaps += getModel().getTimeOverlaps().nrConflicts(best[x], best[idx]); 165 else if (getStudent().getRequests().get(x) instanceof FreeTimeRequest) 166 bestTimeOverlaps += getModel().getTimeOverlaps() 167 .nrConflicts( 168 ((FreeTimeRequest) getStudent().getRequests().get(x)).createEnrollment(), 169 best[idx]); 170 } 171 } 172 if (current[idx] != null && current[idx].getAssignments() != null) { 173 for (int x = 0; x < idx; x++) { 174 if (current[x] != null && current[x].getAssignments() != null) 175 currentTimeOverlaps += getModel().getTimeOverlaps().nrConflicts(current[x], current[idx]); 176 else if (getStudent().getRequests().get(x) instanceof FreeTimeRequest) 177 currentTimeOverlaps += getModel().getTimeOverlaps().nrConflicts( 178 ((FreeTimeRequest) getStudent().getRequests().get(x)).createEnrollment(), 179 current[idx]); 180 } 181 } 182 } 183 if (currentTimeOverlaps < bestTimeOverlaps) 184 return -1; 185 if (bestTimeOverlaps < currentTimeOverlaps) 186 return 1; 187 } 188 189 // 5. avoid distance conflicts 190 if (getModel().getDistanceConflict() != null) { 191 int bestDistanceConf = 0, currentDistanceConf = 0; 192 for (int idx = 0; idx < current.length; idx++) { 193 if (best[idx] != null && best[idx].getAssignments() != null) { 194 for (int x = 0; x < idx; x++) { 195 if (best[x] != null && best[x].getAssignments() != null) 196 bestDistanceConf += getModel().getDistanceConflict().nrConflicts(best[x], best[idx]); 197 } 198 } 199 if (current[idx] != null && current[idx].getAssignments() != null) { 200 for (int x = 0; x < idx; x++) { 201 if (current[x] != null && current[x].getAssignments() != null) 202 currentDistanceConf += getModel().getDistanceConflict().nrConflicts(current[x], 203 current[idx]); 204 } 205 } 206 } 207 if (currentDistanceConf < bestDistanceConf) 208 return -1; 209 if (bestDistanceConf < currentDistanceConf) 210 return 1; 211 } 212 213 // 6. avoid no-time sections 214 int bestNoTime = 0, currentNoTime = 0; 215 for (int idx = 0; idx < current.length; idx++) { 216 if (best[idx] != null && best[idx].getAssignments() != null) { 217 for (Section section : best[idx].getSections()) 218 if (section.getTime() == null) 219 bestNoTime++; 220 } 221 if (current[idx] != null && current[idx].getAssignments() != null) { 222 for (Section section : current[idx].getSections()) 223 if (section.getTime() == null) 224 currentNoTime++; 225 } 226 } 227 if (currentNoTime < bestNoTime) 228 return -1; 229 if (bestNoTime < currentNoTime) 230 return 1; 231 232 // 7. balance sections 233 double bestUnavailableSize = 0.0, currentUnavailableSize = 0.0; 234 int bestAltSectionsWithLimit = 0, currentAltSectionsWithLimit = 0; 235 for (int idx = 0; idx < current.length; idx++) { 236 if (best[idx] != null && best[idx].getAssignments() != null) { 237 for (Section section : best[idx].getSections()) { 238 Subpart subpart = section.getSubpart(); 239 // skip unlimited and single section subparts 240 if (subpart.getSections().size() <= 1 || subpart.getLimit() <= 0) 241 continue; 242 // average size 243 double averageSize = ((double) subpart.getLimit()) / subpart.getSections().size(); 244 // section is below average 245 if (section.getLimit() < averageSize) 246 bestUnavailableSize += (averageSize - section.getLimit()) / averageSize; 247 bestAltSectionsWithLimit++; 248 } 249 } 250 if (current[idx] != null && current[idx].getAssignments() != null) { 251 for (Section section : current[idx].getSections()) { 252 Subpart subpart = section.getSubpart(); 253 // skip unlimited and single section subparts 254 if (subpart.getSections().size() <= 1 || subpart.getLimit() <= 0) 255 continue; 256 // average size 257 double averageSize = ((double) subpart.getLimit()) / subpart.getSections().size(); 258 // section is below average 259 if (section.getLimit() < averageSize) 260 currentUnavailableSize += (averageSize - section.getLimit()) / averageSize; 261 currentAltSectionsWithLimit++; 262 } 263 } 264 } 265 double bestUnavailableSizeFraction = (bestUnavailableSize > 0 ? bestUnavailableSize / bestAltSectionsWithLimit 266 : 0.0); 267 double currentUnavailableSizeFraction = (currentUnavailableSize > 0 ? currentUnavailableSize 268 / currentAltSectionsWithLimit : 0.0); 269 if (currentUnavailableSizeFraction < bestUnavailableSizeFraction) 270 return -1; 271 if (bestUnavailableSizeFraction < currentUnavailableSizeFraction) 272 return 1; 273 274 // 8. average penalty sections 275 double bestPenalty = 0.0, currentPenalty = 0.0; 276 for (int idx = 0; idx < current.length; idx++) { 277 if (best[idx] != null && best[idx].getAssignments() != null) { 278 for (Section section : best[idx].getSections()) 279 bestPenalty += section.getPenalty(); 280 } 281 if (current[idx] != null && current[idx].getAssignments() != null) { 282 for (Section section : current[idx].getSections()) 283 currentPenalty += section.getPenalty(); 284 } 285 } 286 if (currentPenalty < bestPenalty) 287 return -1; 288 if (bestPenalty < currentPenalty) 289 return 1; 290 291 return 0; 292 } 293 294 @Override 295 public boolean canImprove(Assignment<Request, Enrollment> assignment, int maxIdx, Enrollment[] current, 296 Enrollment[] best) { 297 // 0. best number of assigned course requests (including alternativity & 298 // priority) 299 int currentAssignedCourseReq = 0, bestAssignedCourseReq = 0; 300 int currentAssignedRequests = 0, bestAssignedRequests = 0; 301 int currentAssignedPriority = 0, bestAssignedPriority = 0; 302 int currentAssignedAlternativity = 0, bestAssignedAlternativity = 0; 303 int alt = 0; 304 for (int idx = 0; idx < current.length; idx++) { 305 if (idx < maxIdx) { 306 if (current[idx] != null && current[idx].getAssignments() != null) { 307 currentAssignedRequests++; 308 if (current[idx].isCourseRequest()) 309 currentAssignedCourseReq++; 310 currentAssignedPriority += current[idx].getPriority() * current[idx].getPriority(); 311 currentAssignedAlternativity += (current[idx].getRequest().isAlternative() ? 1 : 0); 312 } else if (!isFreeTime(idx) && !getRequest(idx).isAlternative()) { 313 alt++; 314 } 315 } else { 316 if (!getRequest(idx).isAlternative()) { 317 currentAssignedRequests++; 318 if (!isFreeTime(idx)) 319 currentAssignedCourseReq++; 320 } else if (alt > 0) { 321 currentAssignedRequests++; 322 currentAssignedCourseReq++; 323 alt--; 324 currentAssignedAlternativity++; 325 } 326 } 327 if (best[idx] != null && best[idx].getAssignments() != null) { 328 bestAssignedRequests++; 329 if (best[idx].isCourseRequest()) 330 bestAssignedCourseReq++; 331 bestAssignedPriority += best[idx].getPriority() * best[idx].getPriority(); 332 bestAssignedAlternativity += (best[idx].getRequest().isAlternative() ? 1 : 0); 333 } 334 } 335 if (currentAssignedCourseReq > bestAssignedCourseReq) 336 return true; 337 if (bestAssignedCourseReq > currentAssignedCourseReq) 338 return false; 339 if (currentAssignedPriority < bestAssignedPriority) 340 return true; 341 if (bestAssignedPriority < currentAssignedPriority) 342 return false; 343 if (currentAssignedAlternativity < bestAssignedAlternativity) 344 return true; 345 if (bestAssignedAlternativity < currentAssignedAlternativity) 346 return false; 347 348 // 0.5. avoid course time overlaps 349 if (getModel().getTimeOverlaps() != null) { 350 int bestTimeOverlaps = 0, currentTimeOverlaps = 0; 351 for (int idx = 0; idx < current.length; idx++) { 352 if (best[idx] != null && best[idx].getRequest() instanceof CourseRequest) { 353 for (int x = 0; x < idx; x++) { 354 if (best[x] != null && best[x].getRequest() instanceof CourseRequest) 355 bestTimeOverlaps += getModel().getTimeOverlaps().nrConflicts(best[x], best[idx]); 356 } 357 } 358 if (current[idx] != null && idx < maxIdx && current[idx].getRequest() instanceof CourseRequest) { 359 for (int x = 0; x < idx; x++) { 360 if (current[x] != null && current[x].getRequest() instanceof CourseRequest) 361 currentTimeOverlaps += getModel().getTimeOverlaps().nrConflicts(current[x], current[idx]); 362 } 363 } 364 } 365 if (currentTimeOverlaps < bestTimeOverlaps) 366 return true; 367 if (bestTimeOverlaps < currentTimeOverlaps) 368 return false; 369 } 370 371 // 1. maximize number of penalties 372 double bestPenalties = 0, currentPenalties = 0; 373 for (int idx = 0; idx < current.length; idx++) { 374 if (best[idx] != null) { 375 for (Section section : best[idx].getSections()) 376 bestPenalties += getModel().getOverExpected(assignment, section, best[idx].getRequest()); 377 } 378 if (current[idx] != null && idx < maxIdx) { 379 for (Section section : current[idx].getSections()) 380 currentPenalties += getModel().getOverExpected(assignment, section, current[idx].getRequest()); 381 } 382 } 383 if (currentPenalties < bestPenalties) 384 return true; 385 if (bestPenalties < currentPenalties) 386 return false; 387 388 // 2. best number of assigned requests (including free time requests) 389 if (currentAssignedRequests > bestAssignedRequests) 390 return true; 391 if (bestAssignedRequests > currentAssignedRequests) 392 return false; 393 394 // 3. maximize selection 395 int bestSelected = 0, currentSelected = 0; 396 for (int idx = 0; idx < current.length; idx++) { 397 if (best[idx] != null && best[idx].isCourseRequest()) { 398 Set<Section> preferred = getPreferredSections(best[idx].getRequest()); 399 if (preferred != null && !preferred.isEmpty()) { 400 for (Section section : best[idx].getSections()) 401 if (preferred.contains(section)) { 402 if (idx < maxIdx) 403 bestSelected++; 404 } else if (idx >= maxIdx) 405 bestSelected--; 406 } 407 } 408 if (current[idx] != null && idx < maxIdx && current[idx].isCourseRequest()) { 409 Set<Section> preferred = getPreferredSections(current[idx].getRequest()); 410 if (preferred != null && !preferred.isEmpty()) { 411 for (Section section : current[idx].getSections()) 412 if (preferred.contains(section)) 413 currentSelected++; 414 } 415 } 416 } 417 if (currentSelected > bestSelected) 418 return true; 419 if (bestSelected > currentSelected) 420 return false; 421 422 // 4. avoid time overlaps 423 if (getModel().getTimeOverlaps() != null) { 424 int bestTimeOverlaps = 0, currentTimeOverlaps = 0; 425 for (int idx = 0; idx < current.length; idx++) { 426 if (best[idx] != null) { 427 for (int x = 0; x < idx; x++) { 428 if (best[x] != null) 429 bestTimeOverlaps += getModel().getTimeOverlaps().nrConflicts(best[x], best[idx]); 430 else if (getStudent().getRequests().get(x) instanceof FreeTimeRequest) 431 bestTimeOverlaps += getModel().getTimeOverlaps() 432 .nrConflicts( 433 ((FreeTimeRequest) getStudent().getRequests().get(x)).createEnrollment(), 434 best[idx]); 435 } 436 } 437 if (current[idx] != null && idx < maxIdx) { 438 for (int x = 0; x < idx; x++) { 439 if (current[x] != null) 440 currentTimeOverlaps += getModel().getTimeOverlaps().nrConflicts(current[x], current[idx]); 441 else if (getStudent().getRequests().get(x) instanceof FreeTimeRequest) 442 currentTimeOverlaps += getModel().getTimeOverlaps().nrConflicts( 443 ((FreeTimeRequest) getStudent().getRequests().get(x)).createEnrollment(), 444 current[idx]); 445 } 446 } 447 } 448 if (currentTimeOverlaps < bestTimeOverlaps) 449 return true; 450 if (bestTimeOverlaps < currentTimeOverlaps) 451 return false; 452 } 453 454 // 5. avoid distance conflicts 455 if (getModel().getDistanceConflict() != null) { 456 int bestDistanceConf = 0, currentDistanceConf = 0; 457 for (int idx = 0; idx < current.length; idx++) { 458 if (best[idx] != null) { 459 for (int x = 0; x < idx; x++) { 460 if (best[x] != null) 461 bestDistanceConf += getModel().getDistanceConflict().nrConflicts(best[x], best[idx]); 462 } 463 } 464 if (current[idx] != null && idx < maxIdx) { 465 for (int x = 0; x < idx; x++) { 466 if (current[x] != null) 467 currentDistanceConf += getModel().getDistanceConflict().nrConflicts(current[x], 468 current[idx]); 469 } 470 } 471 } 472 if (currentDistanceConf < bestDistanceConf) 473 return true; 474 if (bestDistanceConf < currentDistanceConf) 475 return false; 476 } 477 478 // 6. avoid no-time sections 479 int bestNoTime = 0, currentNoTime = 0; 480 for (int idx = 0; idx < current.length; idx++) { 481 if (best[idx] != null) { 482 for (Section section : best[idx].getSections()) 483 if (section.getTime() == null) 484 bestNoTime++; 485 } 486 if (current[idx] != null && idx < maxIdx) { 487 for (Section section : current[idx].getSections()) 488 if (section.getTime() == null) 489 currentNoTime++; 490 } 491 } 492 if (currentNoTime < bestNoTime) 493 return true; 494 if (bestNoTime < currentNoTime) 495 return false; 496 497 // 7. balance sections 498 double bestUnavailableSize = 0.0, currentUnavailableSize = 0.0; 499 int bestAltSectionsWithLimit = 0, currentAltSectionsWithLimit = 0; 500 for (int idx = 0; idx < current.length; idx++) { 501 if (best[idx] != null) { 502 for (Section section : best[idx].getSections()) { 503 Subpart subpart = section.getSubpart(); 504 // skip unlimited and single section subparts 505 if (subpart.getSections().size() <= 1 || subpart.getLimit() <= 0) 506 continue; 507 // average size 508 double averageSize = ((double) subpart.getLimit()) / subpart.getSections().size(); 509 // section is below average 510 if (section.getLimit() < averageSize) 511 bestUnavailableSize += (averageSize - section.getLimit()) / averageSize; 512 bestAltSectionsWithLimit++; 513 } 514 } 515 if (current[idx] != null && idx < maxIdx) { 516 for (Section section : current[idx].getSections()) { 517 Subpart subpart = section.getSubpart(); 518 // skip unlimited and single section subparts 519 if (subpart.getSections().size() <= 1 || subpart.getLimit() <= 0) 520 continue; 521 // average size 522 double averageSize = ((double) subpart.getLimit()) / subpart.getSections().size(); 523 // section is below average 524 if (section.getLimit() < averageSize) 525 currentUnavailableSize += (averageSize - section.getLimit()) / averageSize; 526 currentAltSectionsWithLimit++; 527 } 528 } 529 } 530 double bestUnavailableSizeFraction = (bestUnavailableSize > 0 ? bestUnavailableSize / bestAltSectionsWithLimit 531 : 0.0); 532 double currentUnavailableSizeFraction = (currentUnavailableSize > 0 ? currentUnavailableSize 533 / currentAltSectionsWithLimit : 0.0); 534 if (currentUnavailableSizeFraction < bestUnavailableSizeFraction) 535 return true; 536 if (bestUnavailableSizeFraction < currentUnavailableSizeFraction) 537 return false; 538 539 // 8. average penalty sections 540 double bestPenalty = 0.0, currentPenalty = 0.0; 541 for (int idx = 0; idx < current.length; idx++) { 542 if (best[idx] != null) { 543 for (Section section : best[idx].getSections()) 544 bestPenalty += section.getPenalty(); 545 if (idx >= maxIdx && best[idx].isCourseRequest()) 546 bestPenalty -= ((CourseRequest) best[idx].getRequest()).getMinPenalty(); 547 } 548 if (current[idx] != null && idx < maxIdx) { 549 for (Section section : current[idx].getSections()) 550 currentPenalty += section.getPenalty(); 551 } 552 } 553 if (currentPenalty < bestPenalty) 554 return true; 555 if (bestPenalty < currentPenalty) 556 return false; 557 558 return true; 559 } 560}