001package org.cpsolver.coursett.model; 002 003import java.util.ArrayList; 004import java.util.Collection; 005import java.util.HashSet; 006import java.util.List; 007import java.util.Set; 008 009import org.cpsolver.coursett.constraint.JenrlConstraint; 010import org.cpsolver.coursett.criteria.StudentCommittedConflict; 011import org.cpsolver.coursett.criteria.StudentConflict; 012import org.cpsolver.ifs.assignment.Assignment; 013import org.cpsolver.ifs.solution.Solution; 014import org.cpsolver.ifs.termination.TerminationCondition; 015import org.cpsolver.ifs.util.Progress; 016import org.cpsolver.ifs.util.ToolBox; 017 018 019/** 020 * Student sectioning (after a solution is found). <br> 021 * <br> 022 * In the current implementation, students are not re-sectioned during the 023 * search, but a student re-sectioning algorithm is called after the solver is 024 * finished or upon the user's request. The re-sectioning is based on a local 025 * search algorithm where the neighboring assignment is obtained from the 026 * current assignment by applying one of the following moves: 027 * <ul> 028 * <li>Two students enrolled in the same course swap all of their class 029 * assignments. 030 * <li>A student is re-enrolled into classes associated with a course such that 031 * the number of conflicts involving that student is minimized. 032 * </ul> 033 * The solver maintains a queue, initially containing all courses with multiple 034 * classes. During each iteration, an improving move (i.e., a move decreasing 035 * the overall number of student conflicts) is applied once discovered. 036 * Re-sectioning is complete once no more improving moves are possible. Only 037 * consistent moves (i.e., moves that respect class limits and other 038 * constraints) are considered. Any additional courses having student conflicts 039 * after a move is accepted are added to the queue. <br> 040 * Since students are not re-sectioned during the timetabling search, the 041 * computed number of student conflicts is really an upper bound on the actual 042 * number that may exist afterward. To compensate for this during the search, 043 * student conflicts between subparts with multiple classes are weighted lower 044 * than conflicts between classes that meet at a single time (i.e., having 045 * student conflicts that cannot be avoided by re-sectioning). 046 * 047 * @version CourseTT 1.3 (University Course Timetabling)<br> 048 * Copyright (C) 2006 - 2014 Tomáš Müller<br> 049 * <a href="mailto:muller@unitime.org">muller@unitime.org</a><br> 050 * <a href="http://muller.unitime.org">http://muller.unitime.org</a><br> 051 * <br> 052 * This library is free software; you can redistribute it and/or modify 053 * it under the terms of the GNU Lesser General Public License as 054 * published by the Free Software Foundation; either version 3 of the 055 * License, or (at your option) any later version. <br> 056 * <br> 057 * This library is distributed in the hope that it will be useful, but 058 * WITHOUT ANY WARRANTY; without even the implied warranty of 059 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 060 * Lesser General Public License for more details. <br> 061 * <br> 062 * You should have received a copy of the GNU Lesser General Public 063 * License along with this library; if not see 064 * <a href='http://www.gnu.org/licenses/'>http://www.gnu.org/licenses/</a>. 065 */ 066 067public class FinalSectioning { 068 private TimetableModel iModel = null; 069 public static double sEps = 0.0001; 070 private boolean iWeighStudents = false; 071 072 public FinalSectioning(TimetableModel model) { 073 iModel = model; 074 iWeighStudents = model.getProperties().getPropertyBoolean("General.WeightStudents", iWeighStudents); 075 } 076 077 public void execute(Solution<Lecture, Placement> solution, TerminationCondition<Lecture, Placement> termination) { 078 Progress p = Progress.getInstance(iModel); 079 p.setStatus("Student Sectioning..."); 080 Collection<Lecture> variables = new ArrayList<Lecture>(iModel.variables()); 081 // include committed classes that have structure 082 if (iModel.hasConstantVariables()) 083 for (Lecture lecture: iModel.constantVariables()) { 084 // if (lecture.getParent() != null || (lecture.sameStudentsLectures()!= null && !lecture.sameStudentsLectures().isEmpty())) 085 variables.add(lecture); 086 } 087 while (!variables.isEmpty() && (termination == null || termination.canContinue(solution))) { 088 // sLogger.debug("Shifting students ..."); 089 p.setPhase("moving students ...", variables.size()); 090 HashSet<Lecture> lecturesToRecompute = new HashSet<Lecture>(variables.size()); 091 092 for (Lecture lecture : variables) { 093 if (lecture.getParent() == null) { 094 Configuration cfg = lecture.getConfiguration(); 095 if (cfg != null && cfg.getAltConfigurations().size() > 1) 096 findAndPerformMoves(solution.getAssignment(), cfg, lecturesToRecompute); 097 } 098 // sLogger.debug("Shifting students for "+lecture); 099 findAndPerformMoves(solution.getAssignment(), lecture, lecturesToRecompute); 100 // sLogger.debug("Lectures to recompute: "+lects); 101 p.incProgress(); 102 } 103 // sLogger.debug("Shifting done, "+getViolatedStudentConflictsCounter().get()+" conflicts."); 104 variables = lecturesToRecompute; 105 } 106 } 107 108 /** 109 * Perform sectioning on the given lecture 110 * 111 * @param assignment current assignment 112 * @param lecture 113 * given lecture 114 * @param recursive 115 * recursively resection lectures affected by a student swap 116 * @param configAsWell 117 * resection students between configurations as well 118 **/ 119 public void resection(Assignment<Lecture, Placement> assignment, Lecture lecture, boolean recursive, boolean configAsWell) { 120 HashSet<Lecture> variables = new HashSet<Lecture>(); 121 findAndPerformMoves(assignment, lecture, variables); 122 if (configAsWell) { 123 Configuration cfg = lecture.getConfiguration(); 124 if (cfg != null && cfg.getAltConfigurations().size() > 1) 125 findAndPerformMoves(assignment, cfg, variables); 126 } 127 if (recursive) { 128 while (!variables.isEmpty()) { 129 HashSet<Lecture> lecturesToRecompute = new HashSet<Lecture>(); 130 for (Lecture l : variables) { 131 if (configAsWell && l.getParent() == null) { 132 Configuration cfg = l.getConfiguration(); 133 if (cfg != null && cfg.getAltConfigurations().size() > 1) 134 findAndPerformMoves(assignment, cfg, lecturesToRecompute); 135 } 136 findAndPerformMoves(assignment, l, lecturesToRecompute); 137 } 138 variables = lecturesToRecompute; 139 } 140 } 141 } 142 143 /** 144 * Swap students between this and the same lectures (lectures which differ 145 * only in the section) 146 * @param assignment current assignment 147 * @param lecture a class that is being considered 148 * @param lecturesToRecompute set of classes that may need to be re-considered 149 */ 150 public void findAndPerformMoves(Assignment<Lecture, Placement> assignment, Lecture lecture, HashSet<Lecture> lecturesToRecompute) { 151 if (lecture.sameSubpartLectures() == null || assignment.getValue(lecture) == null) 152 return; 153 154 if (lecture.getClassLimitConstraint() != null) { 155 while (lecture.nrWeightedStudents() > sEps + lecture.minClassLimit()) { 156 Move m = findAwayMove(assignment, lecture); 157 if (m == null) 158 break; 159 if (m.perform(assignment)) 160 lecturesToRecompute.add(m.secondLecture()); 161 else 162 m.getUndoMove().perform(assignment); 163 } 164 } else if (!iWeighStudents) { 165 while (true) { 166 Move m = findAwayMove(assignment, lecture); 167 if (m == null) 168 break; 169 if (m.perform(assignment)) 170 lecturesToRecompute.add(m.secondLecture()); 171 else 172 m.getUndoMove().perform(assignment); 173 } 174 } 175 176 Set<Student> conflictStudents = lecture.conflictStudents(assignment); 177 if (conflictStudents == null || conflictStudents.isEmpty()) 178 return; 179 // sLogger.debug(" conflicts:"+conflictStudents.size()+"/"+conflictStudents); 180 // sLogger.debug("Solution before swap is "+iModel.getInfo()+"."); 181 if (lecture.sameSubpartLectures().size() > 1) { 182 for (Student student : conflictStudents) { 183 if (assignment.getValue(lecture) == null) 184 continue; 185 Move m = findMove(assignment, lecture, student); 186 if (m != null) { 187 if (m.perform(assignment)) 188 lecturesToRecompute.add(m.secondLecture()); 189 else 190 m.getUndoMove().perform(assignment); 191 } 192 } 193 } else { 194 for (Student student : conflictStudents) { 195 for (Lecture anotherLecture : lecture.conflictLectures(assignment, student)) { 196 if (anotherLecture.equals(lecture) || anotherLecture.sameSubpartLectures() == null 197 || assignment.getValue(anotherLecture) == null 198 || anotherLecture.sameSubpartLectures().size() <= 1) 199 continue; 200 lecturesToRecompute.add(anotherLecture); 201 } 202 } 203 } 204 } 205 206 public void findAndPerformMoves(Assignment<Lecture, Placement> assignment, Configuration configuration, HashSet<Lecture> lecturesToRecompute) { 207 for (Student student : configuration.students()) { 208 if (!configuration.hasConflict(assignment, student)) 209 continue; 210 211 MoveBetweenCfgs m = findMove(assignment, configuration, student); 212 213 if (m != null) { 214 if (m.perform(assignment)) 215 lecturesToRecompute.addAll(m.secondLectures()); 216 else 217 m.getUndoMove().perform(assignment); 218 } 219 } 220 } 221 222 public Move findAwayMove(Assignment<Lecture, Placement> assignment, Lecture lecture) { 223 List<Move> bestMoves = null; 224 double bestDelta = 0; 225 for (Student student : lecture.students()) { 226 if (!student.canUnenroll(lecture)) 227 continue; 228 for (Lecture sameLecture : lecture.sameSubpartLectures()) { 229 double studentWeight = student.getOfferingWeight(sameLecture.getConfiguration()); 230 if (!student.canEnroll(sameLecture)) 231 continue; 232 if (sameLecture.equals(lecture) || assignment.getValue(sameLecture) == null) 233 continue; 234 if (sameLecture.nrWeightedStudents() + studentWeight <= sEps + sameLecture.classLimit(assignment)) { 235 Move m = createMove(assignment, lecture, student, sameLecture, null); 236 if (m == null || m.isTabu()) 237 continue; 238 double delta = m.getDelta(assignment); 239 if (delta < bestDelta) { 240 if (bestMoves == null) 241 bestMoves = new ArrayList<Move>(); 242 else 243 bestMoves.clear(); 244 bestMoves.add(m); 245 bestDelta = delta; 246 } else if (delta == bestDelta) { 247 if (bestMoves == null) 248 bestMoves = new ArrayList<Move>(); 249 bestMoves.add(m); 250 } 251 } 252 } 253 } 254 if (bestDelta < -sEps && bestMoves != null) { 255 Move m = ToolBox.random(bestMoves); 256 return m; 257 } 258 return null; 259 } 260 261 public Move findMove(Assignment<Lecture, Placement> assignment, Lecture lecture, Student student) { 262 if (!student.canUnenroll(lecture)) return null; 263 double bestDelta = 0; 264 List<Move> bestMoves = null; 265 double studentWeight = student.getOfferingWeight(lecture.getConfiguration()); 266 for (Lecture sameLecture : lecture.sameSubpartLectures()) { // sameStudentLectures 267 if (!student.canEnroll(sameLecture)) 268 continue; 269 if (sameLecture.equals(lecture) || assignment.getValue(sameLecture) == null) 270 continue; 271 if (sameLecture.nrWeightedStudents() + studentWeight <= sEps + sameLecture.classLimit(assignment)) { 272 Move m = createMove(assignment, lecture, student, sameLecture, null); 273 if (m == null || m.isTabu()) 274 continue; 275 double delta = m.getDelta(assignment); 276 if (delta < bestDelta) { 277 if (bestMoves == null) 278 bestMoves = new ArrayList<Move>(); 279 else 280 bestMoves.clear(); 281 bestMoves.add(m); 282 bestDelta = delta; 283 } else if (delta == bestDelta) { 284 if (bestMoves == null) 285 bestMoves = new ArrayList<Move>(); 286 bestMoves.add(m); 287 } 288 } 289 for (Student anotherStudent : sameLecture.students()) { 290 if (!anotherStudent.canUnenroll(sameLecture) || !anotherStudent.canEnroll(lecture)) 291 continue; 292 double anotherStudentWeight = anotherStudent.getOfferingWeight(lecture.getConfiguration()); 293 if (anotherStudentWeight != studentWeight) { 294 if (sameLecture.nrWeightedStudents() - anotherStudentWeight + studentWeight > sEps 295 + sameLecture.classLimit(assignment)) 296 continue; 297 if (lecture.nrWeightedStudents() - studentWeight + anotherStudentWeight > sEps 298 + lecture.classLimit(assignment)) 299 continue; 300 } 301 if (bestDelta < -sEps && bestMoves != null && bestMoves.size() > 10) 302 break; 303 Move m = createMove(assignment, lecture, student, sameLecture, anotherStudent); 304 if (m == null || m.isTabu()) 305 continue; 306 double delta = m.getDelta(assignment); 307 if (delta < bestDelta) { 308 if (bestMoves == null) 309 bestMoves = new ArrayList<Move>(); 310 else 311 bestMoves.clear(); 312 bestMoves.add(m); 313 bestDelta = delta; 314 } else if (delta == bestDelta) { 315 if (bestMoves == null) 316 bestMoves = new ArrayList<Move>(); 317 bestMoves.add(m); 318 } 319 } 320 if (Math.abs(bestDelta) < sEps && bestMoves != null && bestMoves.size() > 10) 321 break; 322 } 323 if (bestDelta < -sEps && bestMoves != null) 324 return ToolBox.random(bestMoves); 325 return null; 326 } 327 328 public MoveBetweenCfgs findMove(Assignment<Lecture, Placement> assignment, Configuration config, Student student) { 329 double bestDelta = 0; 330 List<MoveBetweenCfgs> bestMoves = null; 331 for (Configuration altConfig : config.getAltConfigurations()) { 332 if (altConfig.equals(config)) 333 continue; 334 335 MoveBetweenCfgs m = createMove(assignment, config, student, altConfig, null); 336 if (m != null && !m.isTabu()) { 337 double delta = m.getDelta(assignment); 338 if (delta < bestDelta) { 339 if (bestMoves == null) 340 bestMoves = new ArrayList<MoveBetweenCfgs>(); 341 else 342 bestMoves.clear(); 343 bestMoves.add(m); 344 bestDelta = delta; 345 } else if (delta == bestDelta) { 346 if (bestMoves == null) 347 bestMoves = new ArrayList<MoveBetweenCfgs>(); 348 bestMoves.add(m); 349 } 350 } 351 352 for (Student anotherStudent : altConfig.students()) { 353 if (bestDelta < -sEps && bestMoves != null && bestMoves.size() > 10) 354 break; 355 356 m = createMove(assignment, config, student, altConfig, anotherStudent); 357 if (m != null && !m.isTabu()) { 358 double delta = m.getDelta(assignment); 359 if (delta < bestDelta) { 360 if (bestMoves == null) 361 bestMoves = new ArrayList<MoveBetweenCfgs>(); 362 else 363 bestMoves.clear(); 364 bestMoves.add(m); 365 bestDelta = delta; 366 } else if (delta == bestDelta) { 367 if (bestMoves == null) 368 bestMoves = new ArrayList<MoveBetweenCfgs>(); 369 bestMoves.add(m); 370 } 371 } 372 } 373 if (Math.abs(bestDelta) < sEps && bestMoves != null && bestMoves.size() > 10) 374 break; 375 } 376 if (bestDelta < -sEps && bestMoves != null) 377 return ToolBox.random(bestMoves); 378 return null; 379 } 380 381 public Move createMove(Assignment<Lecture, Placement> assignment, Lecture firstLecture, Student firstStudent, Lecture secondLecture, Student secondStudent) { 382 return createMove(assignment, firstLecture, firstStudent, secondLecture, secondStudent, null); 383 } 384 385 public Move createMove(Assignment<Lecture, Placement> assignment, Lecture firstLecture, Student firstStudent, Lecture secondLecture, Student secondStudent, Move parentMove) { 386 if (!firstStudent.canUnenroll(firstLecture) || !firstStudent.canEnroll(secondLecture)) 387 return null; 388 if (secondStudent != null && (!secondStudent.canUnenroll(secondLecture) || !secondStudent.canEnroll(firstLecture))) 389 return null; 390 if (firstLecture.getParent() != null && secondLecture.getParent() == null) 391 return null; 392 if (firstLecture.getParent() == null && secondLecture.getParent() != null) 393 return null; 394 395 Move move = new Move(firstLecture, firstStudent, secondLecture, secondStudent); 396 397 if (parentMove == null) { 398 Lecture l1 = firstLecture, l2 = secondLecture; 399 while (l1.getParent() != null && l2.getParent() != null && !l1.getParent().equals(l2.getParent())) { 400 Lecture p1 = l1.getParent(); 401 Lecture p2 = l2.getParent(); 402 if (assignment.getValue(p1) == null || assignment.getValue(p2) == null) return null; 403 double w1 = firstStudent.getOfferingWeight(p1.getConfiguration()); 404 double w2 = (secondStudent == null ? 0.0 : secondStudent.getOfferingWeight(p2.getConfiguration())); 405 if (w1 != w2) { 406 if (p1.nrWeightedStudents() - w1 + w2 > sEps + p1.classLimit(assignment)) 407 return null; 408 if (p2.nrWeightedStudents() - w2 + w1 > sEps + p2.classLimit(assignment)) 409 return null; 410 } 411 if (firstStudent.canUnenroll(p2) && firstStudent.canEnroll(p1) && (secondStudent == null || (secondStudent.canUnenroll(p1) && secondStudent.canEnroll(p2)))) { 412 move.addChildMove(new Move(p1, firstStudent, p2, secondStudent)); 413 } else { 414 return null; 415 } 416 l1 = p1; l2 = p2; 417 } 418 } 419 420 if (firstLecture.hasAnyChildren() != secondLecture.hasAnyChildren()) 421 return null; 422 if (firstLecture.hasAnyChildren()) { 423 if (secondStudent != null) { 424 for (Long subpartId: firstLecture.getChildrenSubpartIds()) { 425 Lecture firstChildLecture = firstLecture.getChild(firstStudent, subpartId); 426 Lecture secondChildLecture = secondLecture.getChild(secondStudent, subpartId); 427 if (firstChildLecture == null || secondChildLecture == null) 428 return null; 429 double firstStudentWeight = firstStudent.getOfferingWeight(firstChildLecture.getConfiguration()); 430 double secondStudentWeight = secondStudent.getOfferingWeight(secondChildLecture.getConfiguration()); 431 if (firstStudentWeight != secondStudentWeight) { 432 if (firstChildLecture.nrWeightedStudents() - firstStudentWeight + secondStudentWeight > sEps 433 + firstChildLecture.classLimit(assignment)) 434 return null; 435 if (secondChildLecture.nrWeightedStudents() - secondStudentWeight + firstStudentWeight > sEps 436 + secondChildLecture.classLimit(assignment)) 437 return null; 438 } 439 if (assignment.getValue(firstChildLecture) != null && assignment.getValue(secondChildLecture) != null) { 440 Move m = createMove(assignment, firstChildLecture, firstStudent, secondChildLecture, secondStudent, move); 441 if (m == null) 442 return null; 443 move.addChildMove(m); 444 } else 445 return null; 446 } 447 } else { 448 for (Long subpartId: firstLecture.getChildrenSubpartIds()) { 449 Lecture firstChildLecture = firstLecture.getChild(firstStudent, subpartId); 450 if (firstChildLecture == null || assignment.getValue(firstChildLecture) == null) 451 return null; 452 double firstStudentWeight = firstStudent.getOfferingWeight(firstChildLecture.getConfiguration()); 453 List<Lecture> secondChildLectures = secondLecture.getChildren(subpartId); 454 if (secondChildLectures == null || secondChildLectures.isEmpty()) 455 return null; 456 List<Move> bestMoves = null; 457 double bestDelta = 0; 458 for (Lecture secondChildLecture : secondChildLectures) { 459 if (assignment.getValue(secondChildLecture) == null) 460 continue; 461 if (secondChildLecture.nrWeightedStudents() + firstStudentWeight > sEps 462 + secondChildLecture.classLimit(assignment)) 463 continue; 464 Move m = createMove(assignment, firstChildLecture, firstStudent, secondChildLecture, secondStudent, move); 465 if (m == null) 466 continue; 467 double delta = m.getDelta(assignment); 468 if (bestMoves == null || delta < bestDelta) { 469 if (bestMoves == null) 470 bestMoves = new ArrayList<Move>(); 471 else 472 bestMoves.clear(); 473 bestMoves.add(m); 474 bestDelta = delta; 475 } else if (delta == bestDelta) { 476 bestMoves.add(m); 477 } 478 } 479 if (bestDelta >= 0 || bestMoves == null) 480 return null; 481 Move m = ToolBox.random(bestMoves); 482 move.addChildMove(m); 483 } 484 } 485 } 486 return move; 487 } 488 489 public class Move { 490 Lecture iFirstLecture = null; 491 Student iFirstStudent = null; 492 Lecture iSecondLecture = null; 493 Student iSecondStudent = null; 494 List<Move> iChildMoves = null; 495 496 private Move(Lecture firstLecture, Student firstStudent, Lecture secondLecture, Student secondStudent) { 497 iFirstLecture = firstLecture; 498 iFirstStudent = firstStudent; 499 iSecondLecture = secondLecture; 500 iSecondStudent = secondStudent; 501 } 502 503 public Lecture firstLecture() { 504 return iFirstLecture; 505 } 506 507 public Student firstStudent() { 508 return iFirstStudent; 509 } 510 511 public Lecture secondLecture() { 512 return iSecondLecture; 513 } 514 515 public Student secondStudent() { 516 return iSecondStudent; 517 } 518 519 public void addChildMove(Move move) { 520 if (iChildMoves == null) 521 iChildMoves = new ArrayList<Move>(); 522 iChildMoves.add(move); 523 } 524 525 public List<Move> getChildMoves() { 526 return iChildMoves; 527 } 528 529 public Move getUndoMove() { 530 Move ret = new Move(iSecondLecture, iFirstStudent, iFirstLecture, iSecondStudent); 531 if (iChildMoves != null) 532 for (Move move: iChildMoves) 533 ret.addChildMove(move.getUndoMove()); 534 return ret; 535 } 536 537 public boolean perform(Assignment<Lecture, Placement> assignment) { 538 double conflicts = firstLecture().getModel().getCriterion(StudentConflict.class).getValue(assignment) + 539 firstLecture().getModel().getCriterion(StudentCommittedConflict.class).getValue(assignment); 540 for (Lecture lecture : firstStudent().getLectures()) { 541 if (lecture.equals(firstLecture())) 542 continue; 543 JenrlConstraint jenrl = firstLecture().jenrlConstraint(lecture); 544 if (jenrl == null) 545 continue; 546 jenrl.decJenrl(assignment, firstStudent()); 547 if (jenrl.getNrStudents() == 0) { 548 jenrl.getContext(assignment).unassigned(assignment, null); 549 Object[] vars = jenrl.variables().toArray(); 550 for (int j = 0; j < vars.length; j++) 551 jenrl.removeVariable((Lecture) vars[j]); 552 iModel.removeConstraint(jenrl); 553 } 554 } 555 if (secondStudent() != null) { 556 for (Lecture lecture : secondStudent().getLectures()) { 557 if (lecture.equals(secondLecture())) 558 continue; 559 JenrlConstraint jenrl = secondLecture().jenrlConstraint(lecture); 560 if (jenrl == null) 561 continue; 562 jenrl.decJenrl(assignment, secondStudent()); 563 if (jenrl.getNrStudents() == 0) { 564 jenrl.getContext(assignment).unassigned(assignment, null); 565 Object[] vars = jenrl.variables().toArray(); 566 for (int j = 0; j < vars.length; j++) 567 jenrl.removeVariable((Lecture) vars[j]); 568 iModel.removeConstraint(jenrl); 569 } 570 } 571 } 572 573 firstLecture().removeStudent(assignment, firstStudent()); 574 firstStudent().removeLecture(firstLecture()); 575 secondLecture().addStudent(assignment, firstStudent()); 576 firstStudent().addLecture(secondLecture()); 577 if (secondStudent() != null) { 578 secondLecture().removeStudent(assignment, secondStudent()); 579 secondStudent().removeLecture(secondLecture()); 580 firstLecture().addStudent(assignment, secondStudent()); 581 secondStudent().addLecture(firstLecture()); 582 } 583 584 for (Lecture lecture : firstStudent().getLectures()) { 585 if (lecture.equals(secondLecture())) 586 continue; 587 JenrlConstraint jenrl = secondLecture().jenrlConstraint(lecture); 588 if (jenrl == null) { 589 jenrl = new JenrlConstraint(); 590 jenrl.addVariable(secondLecture()); 591 jenrl.addVariable(lecture); 592 iModel.addConstraint(jenrl); 593 // sLogger.debug(getName()+": add jenr {conf="+jenrl.isInConflict()+", lect="+anotherLecture.getName()+", jenr="+jenrl+"}"); 594 } 595 jenrl.incJenrl(assignment, firstStudent()); 596 } 597 if (secondStudent() != null) { 598 for (Lecture lecture : secondStudent().getLectures()) { 599 if (lecture.equals(firstLecture())) 600 continue; 601 JenrlConstraint jenrl = firstLecture().jenrlConstraint(lecture); 602 if (jenrl == null) { 603 jenrl = new JenrlConstraint(); 604 jenrl.addVariable(lecture); 605 jenrl.addVariable(firstLecture()); 606 iModel.addConstraint(jenrl); 607 // sLogger.debug(getName()+": add jenr {conf="+jenrl.isInConflict()+", lect="+anotherLecture.getName()+", jenr="+jenrl+"}"); 608 } 609 jenrl.incJenrl(assignment, secondStudent()); 610 } 611 } 612 613 if (getChildMoves() != null) { 614 for (Move move : getChildMoves()) { 615 move.perform(assignment); 616 } 617 } 618 // sLogger.debug("Solution after swap is "+iModel.getInfo()+"."); 619 return firstLecture().getModel().getCriterion(StudentConflict.class).getValue(assignment) + firstLecture().getModel().getCriterion(StudentCommittedConflict.class).getValue(assignment) < conflicts; 620 } 621 622 public double getDelta(Assignment<Lecture, Placement> assignment) { 623 double delta = 0; 624 for (Lecture lecture : firstStudent().getLectures()) { 625 if (assignment.getValue(lecture) == null || lecture.equals(firstLecture())) 626 continue; 627 JenrlConstraint jenrl = firstLecture().jenrlConstraint(lecture); 628 if (jenrl == null) 629 continue; 630 if (jenrl.isInConflict(assignment)) 631 delta -= jenrl.getJenrlWeight(firstStudent()); 632 } 633 if (secondStudent() != null) { 634 for (Lecture lecture : secondStudent().getLectures()) { 635 if (assignment.getValue(lecture) == null || lecture.equals(secondLecture())) 636 continue; 637 JenrlConstraint jenrl = secondLecture().jenrlConstraint(lecture); 638 if (jenrl == null) 639 continue; 640 if (jenrl.isInConflict(assignment)) 641 delta -= jenrl.getJenrlWeight(secondStudent()); 642 } 643 } 644 645 for (Lecture lecture : firstStudent().getLectures()) { 646 if (assignment.getValue(lecture) == null || lecture.equals(firstLecture())) 647 continue; 648 JenrlConstraint jenrl = secondLecture().jenrlConstraint(lecture); 649 if (jenrl != null) { 650 if (jenrl.isInConflict(assignment)) 651 delta += jenrl.getJenrlWeight(firstStudent()); 652 } else { 653 if (JenrlConstraint.isInConflict(assignment.getValue(secondLecture()), assignment.getValue(lecture), iModel.getDistanceMetric(), iModel.getStudentWorkDayLimit())) 654 delta += firstStudent().getJenrlWeight(secondLecture(), lecture); 655 } 656 } 657 if (secondStudent() != null) { 658 for (Lecture lecture : secondStudent().getLectures()) { 659 if (assignment.getValue(lecture) == null || lecture.equals(secondLecture())) 660 continue; 661 JenrlConstraint jenrl = firstLecture().jenrlConstraint(lecture); 662 if (jenrl != null) { 663 if (jenrl.isInConflict(assignment)) 664 delta += jenrl.getJenrlWeight(secondStudent()); 665 } else { 666 if (JenrlConstraint.isInConflict(assignment.getValue(firstLecture()), assignment.getValue(lecture), iModel.getDistanceMetric(), iModel.getStudentWorkDayLimit())) 667 delta += secondStudent().getJenrlWeight(firstLecture(), lecture); 668 } 669 } 670 } 671 672 Placement p1 = assignment.getValue(firstLecture()); 673 Placement p2 = assignment.getValue(secondLecture()); 674 delta += firstStudent().countConflictPlacements(p2) - firstStudent().countConflictPlacements(p1); 675 if (secondStudent() != null) 676 delta += secondStudent().countConflictPlacements(p1) - secondStudent().countConflictPlacements(p2); 677 678 if (getChildMoves() != null) { 679 for (Move move : getChildMoves()) { 680 delta += move.getDelta(assignment); 681 } 682 } 683 return delta; 684 } 685 686 public boolean isTabu() { 687 return false; 688 } 689 690 @Override 691 public String toString() { 692 return "Move{" + firstStudent() + "/" + firstLecture() + " <-> " + secondStudent() + "/" + secondLecture() 693 + ", ch=" + getChildMoves() + "}"; 694 695 } 696 697 } 698 699 public MoveBetweenCfgs createMove(Assignment<Lecture, Placement> assignment, Configuration firstConfig, Student firstStudent, Configuration secondConfig, 700 Student secondStudent) { 701 MoveBetweenCfgs m = new MoveBetweenCfgs(firstConfig, firstStudent, secondConfig, secondStudent); 702 703 for (Long subpartId: firstConfig.getTopSubpartIds()) { 704 if (!addLectures(assignment, firstStudent, secondStudent, m.firstLectures(), firstConfig.getTopLectures(subpartId))) 705 return null; 706 } 707 708 for (Long subpartId: secondConfig.getTopSubpartIds()) { 709 if (!addLectures(assignment, secondStudent, firstStudent, m.secondLectures(), secondConfig.getTopLectures(subpartId))) 710 return null; 711 } 712 713 if (m.firstLectures().isEmpty() || m.secondLectures().isEmpty()) return null; 714 715 return m; 716 } 717 718 private boolean addLectures(Assignment<Lecture, Placement> assignment, Student student, Student newStudent, Set<Lecture> studentLectures, 719 Collection<Lecture> lectures) { 720 Lecture lecture = null; 721 if (lectures == null) 722 return false; 723 724 if (student != null) { 725 for (Lecture l : lectures) { 726 if (l.students().contains(student)) { 727 lecture = l; 728 if (!student.canUnenroll(lecture)) return false; 729 break; 730 } 731 } 732 } else { 733 int bestValue = 0; 734 Lecture bestLecture = null; 735 for (Lecture l : lectures) { 736 int val = test(assignment, newStudent, l); 737 if (val < 0) 738 continue; 739 if (bestLecture == null || bestValue > val) { 740 bestValue = val; 741 bestLecture = l; 742 } 743 } 744 lecture = bestLecture; 745 } 746 747 if (lecture == null) 748 return false; 749 if (newStudent != null && !newStudent.canEnroll(lecture)) 750 return false; 751 if (lecture.getModel() == null) return false; 752 studentLectures.add(lecture); 753 if (lecture.getChildrenSubpartIds() != null) { 754 for (Long subpartId: lecture.getChildrenSubpartIds()) { 755 if (!addLectures(assignment, student, newStudent, studentLectures, lecture.getChildren(subpartId))) 756 return false; 757 } 758 } 759 760 return true; 761 } 762 763 public int test(Assignment<Lecture, Placement> assignment, Student student, Lecture lecture) { 764 if (assignment.getValue(lecture) == null) 765 return -1; 766 double studentWeight = student.getOfferingWeight(lecture.getConfiguration()); 767 if (lecture.nrWeightedStudents() + studentWeight > sEps + lecture.classLimit(assignment)) 768 return -1; 769 if (!student.canEnroll(lecture)) 770 return -1; 771 772 int test = 0; 773 for (Lecture x : student.getLectures()) { 774 if (assignment.getValue(x) == null) 775 continue; 776 if (JenrlConstraint.isInConflict(assignment.getValue(lecture), assignment.getValue(x), iModel.getDistanceMetric(), iModel.getStudentWorkDayLimit())) 777 test++; 778 } 779 test += student.countConflictPlacements(assignment.getValue(lecture)); 780 781 if (lecture.getChildrenSubpartIds() != null) { 782 for (Long subpartId: lecture.getChildrenSubpartIds()) { 783 int bestTest = -1; 784 for (Lecture child : lecture.getChildren(subpartId)) { 785 int t = test(assignment, student, child); 786 if (t < 0) 787 continue; 788 if (bestTest < 0 || bestTest > t) 789 bestTest = t; 790 } 791 if (bestTest < 0) 792 return -1; 793 test += bestTest; 794 } 795 } 796 return test; 797 } 798 799 public class MoveBetweenCfgs { 800 Configuration iFirstConfig = null; 801 Set<Lecture> iFirstLectures = new HashSet<Lecture>(); 802 Student iFirstStudent = null; 803 Configuration iSecondConfig = null; 804 Set<Lecture> iSecondLectures = new HashSet<Lecture>(); 805 Student iSecondStudent = null; 806 807 public MoveBetweenCfgs(Configuration firstConfig, Student firstStudent, Configuration secondConfig, 808 Student secondStudent) { 809 iFirstConfig = firstConfig; 810 iFirstStudent = firstStudent; 811 iSecondConfig = secondConfig; 812 iSecondStudent = secondStudent; 813 } 814 815 public Configuration firstConfiguration() { 816 return iFirstConfig; 817 } 818 819 public Student firstStudent() { 820 return iFirstStudent; 821 } 822 823 public Set<Lecture> firstLectures() { 824 return iFirstLectures; 825 } 826 827 public Configuration secondConfiguration() { 828 return iSecondConfig; 829 } 830 831 public Student secondStudent() { 832 return iSecondStudent; 833 } 834 835 public Set<Lecture> secondLectures() { 836 return iSecondLectures; 837 } 838 839 public MoveBetweenCfgs getUndoMove() { 840 MoveBetweenCfgs ret = new MoveBetweenCfgs(iSecondConfig, iFirstStudent, iFirstConfig, iSecondStudent); 841 ret.secondLectures().addAll(iFirstLectures); 842 ret.firstLectures().addAll(iSecondLectures); 843 return ret; 844 } 845 846 public boolean perform(Assignment<Lecture, Placement> assignment) { 847 double conflicts = firstLectures().iterator().next().getModel().getCriterion(StudentConflict.class).getValue(assignment) + 848 firstLectures().iterator().next().getModel().getCriterion(StudentCommittedConflict.class).getValue(assignment); 849 firstStudent().removeConfiguration(firstConfiguration()); 850 firstStudent().addConfiguration(secondConfiguration()); 851 for (Lecture lecture : firstStudent().getLectures()) { 852 853 for (Lecture firstLecture : firstLectures()) { 854 if (firstLecture.equals(lecture)) 855 continue; 856 if (firstLectures().contains(lecture) 857 && firstLecture.getClassId().compareTo(lecture.getClassId()) > 0) 858 continue; 859 860 JenrlConstraint jenrl = firstLecture.jenrlConstraint(lecture); 861 if (jenrl == null) 862 continue; 863 jenrl.decJenrl(assignment, firstStudent()); 864 if (jenrl.getNrStudents() == 0) { 865 jenrl.getContext(assignment).unassigned(assignment, null); 866 Object[] vars = jenrl.variables().toArray(); 867 for (int k = 0; k < vars.length; k++) 868 jenrl.removeVariable((Lecture) vars[k]); 869 iModel.removeConstraint(jenrl); 870 } 871 } 872 } 873 874 if (secondStudent() != null) { 875 secondStudent().removeConfiguration(secondConfiguration()); 876 secondStudent().addConfiguration(firstConfiguration()); 877 for (Lecture lecture : secondStudent().getLectures()) { 878 879 for (Lecture secondLecture : secondLectures()) { 880 if (secondLecture.equals(lecture)) 881 continue; 882 if (secondLectures().contains(lecture) 883 && secondLecture.getClassId().compareTo(lecture.getClassId()) > 0) 884 continue; 885 886 JenrlConstraint jenrl = secondLecture.jenrlConstraint(lecture); 887 if (jenrl == null) 888 continue; 889 jenrl.decJenrl(assignment, secondStudent()); 890 if (jenrl.getNrStudents() == 0) { 891 jenrl.getContext(assignment).unassigned(assignment, null); 892 Object[] vars = jenrl.variables().toArray(); 893 for (int k = 0; k < vars.length; k++) 894 jenrl.removeVariable((Lecture) vars[k]); 895 iModel.removeConstraint(jenrl); 896 } 897 } 898 } 899 } 900 901 for (Lecture firstLecture : firstLectures()) { 902 firstLecture.removeStudent(assignment, firstStudent()); 903 firstStudent().removeLecture(firstLecture); 904 if (secondStudent() != null) { 905 firstLecture.addStudent(assignment, secondStudent()); 906 secondStudent().addLecture(firstLecture); 907 } 908 } 909 for (Lecture secondLecture : secondLectures()) { 910 secondLecture.addStudent(assignment, firstStudent()); 911 firstStudent().addLecture(secondLecture); 912 if (secondStudent() != null) { 913 secondLecture.removeStudent(assignment, secondStudent()); 914 secondStudent().removeLecture(secondLecture); 915 } 916 } 917 918 for (Lecture lecture : firstStudent().getLectures()) { 919 920 for (Lecture secondLecture : secondLectures()) { 921 if (secondLecture.equals(lecture)) 922 continue; 923 if (secondLectures().contains(lecture) 924 && secondLecture.getClassId().compareTo(lecture.getClassId()) > 0) 925 continue; 926 927 JenrlConstraint jenrl = secondLecture.jenrlConstraint(lecture); 928 if (jenrl == null) { 929 jenrl = new JenrlConstraint(); 930 jenrl.addVariable(secondLecture); 931 jenrl.addVariable(lecture); 932 iModel.addConstraint(jenrl); 933 } 934 jenrl.incJenrl(assignment, firstStudent()); 935 } 936 } 937 938 if (secondStudent() != null) { 939 for (Lecture lecture : secondStudent().getLectures()) { 940 941 for (Lecture firstLecture : firstLectures()) { 942 if (firstLecture.equals(lecture)) 943 continue; 944 if (firstLectures().contains(lecture) 945 && firstLecture.getClassId().compareTo(lecture.getClassId()) > 0) 946 continue; 947 948 JenrlConstraint jenrl = firstLecture.jenrlConstraint(lecture); 949 if (jenrl == null) { 950 jenrl = new JenrlConstraint(); 951 jenrl.addVariable(firstLecture); 952 jenrl.addVariable(lecture); 953 iModel.addConstraint(jenrl); 954 } 955 jenrl.incJenrl(assignment, secondStudent()); 956 } 957 } 958 } 959 return firstLectures().iterator().next().getModel().getCriterion(StudentConflict.class).getValue(assignment) + 960 firstLectures().iterator().next().getModel().getCriterion(StudentCommittedConflict.class).getValue(assignment) < conflicts; 961 } 962 963 public double getDelta(Assignment<Lecture, Placement> assignment) { 964 double delta = 0; 965 966 for (Lecture lecture : firstStudent().getLectures()) { 967 if (assignment.getValue(lecture) == null) 968 continue; 969 970 for (Lecture firstLecture : firstLectures()) { 971 if (assignment.getValue(firstLecture) == null || firstLecture.equals(lecture)) 972 continue; 973 JenrlConstraint jenrl = firstLecture.jenrlConstraint(lecture); 974 if (jenrl == null) 975 continue; 976 if (jenrl.isInConflict(assignment)) 977 delta -= jenrl.getJenrlWeight(firstStudent()); 978 } 979 980 for (Lecture secondLecture : secondLectures()) { 981 if (assignment.getValue(secondLecture) == null || secondLecture.equals(lecture)) 982 continue; 983 JenrlConstraint jenrl = secondLecture.jenrlConstraint(lecture); 984 if (jenrl != null) { 985 if (jenrl.isInConflict(assignment)) 986 delta += jenrl.getJenrlWeight(firstStudent()); 987 } else { 988 if (JenrlConstraint.isInConflict(assignment.getValue(secondLecture), assignment.getValue(lecture), iModel.getDistanceMetric(), iModel.getStudentWorkDayLimit())) 989 delta += firstStudent().getJenrlWeight(secondLecture, lecture); 990 } 991 } 992 } 993 994 if (secondStudent() != null) { 995 for (Lecture lecture : secondStudent().getLectures()) { 996 if (assignment.getValue(lecture) == null) 997 continue; 998 999 for (Lecture secondLecture : secondLectures()) { 1000 if (assignment.getValue(secondLecture) == null || secondLecture.equals(lecture)) 1001 continue; 1002 JenrlConstraint jenrl = secondLecture.jenrlConstraint(lecture); 1003 if (jenrl == null) 1004 continue; 1005 if (jenrl.isInConflict(assignment)) 1006 delta -= jenrl.getJenrlWeight(secondStudent()); 1007 } 1008 1009 for (Lecture firstLecture : firstLectures()) { 1010 if (assignment.getValue(firstLecture) == null || firstLecture.equals(lecture)) 1011 continue; 1012 JenrlConstraint jenrl = firstLecture.jenrlConstraint(lecture); 1013 if (jenrl != null) { 1014 if (jenrl.isInConflict(assignment)) 1015 delta += jenrl.getJenrlWeight(secondStudent()); 1016 } else { 1017 if (JenrlConstraint.isInConflict(assignment.getValue(firstLecture), assignment.getValue(lecture), iModel.getDistanceMetric(), iModel.getStudentWorkDayLimit())) 1018 delta += secondStudent().getJenrlWeight(firstLecture, lecture); 1019 } 1020 } 1021 } 1022 } 1023 1024 for (Lecture firstLecture : firstLectures()) { 1025 Placement p1 = assignment.getValue(firstLecture); 1026 if (p1 == null) 1027 continue; 1028 delta -= firstStudent().countConflictPlacements(p1); 1029 if (secondStudent() != null) 1030 delta += secondStudent().countConflictPlacements(p1); 1031 } 1032 1033 for (Lecture secondLecture : secondLectures()) { 1034 Placement p2 = assignment.getValue(secondLecture); 1035 if (p2 == null) 1036 continue; 1037 delta += firstStudent().countConflictPlacements(p2); 1038 if (secondStudent() != null) 1039 delta -= secondStudent().countConflictPlacements(p2); 1040 } 1041 1042 return delta; 1043 } 1044 1045 public boolean isTabu() { 1046 return false; 1047 } 1048 1049 @Override 1050 public String toString() { 1051 return "Move{" + firstStudent() + "/" + firstConfiguration().getConfigId() + " <-> " + secondStudent() 1052 + "/" + secondConfiguration().getConfigId() + "}"; 1053 } 1054 1055 } 1056}