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 return m; 714 } 715 716 private boolean addLectures(Assignment<Lecture, Placement> assignment, Student student, Student newStudent, Set<Lecture> studentLectures, 717 Collection<Lecture> lectures) { 718 Lecture lecture = null; 719 if (lectures == null) 720 return false; 721 722 if (student != null) { 723 for (Lecture l : lectures) { 724 if (l.students().contains(student)) { 725 lecture = l; 726 if (!student.canUnenroll(lecture)) return false; 727 break; 728 } 729 } 730 } else { 731 int bestValue = 0; 732 Lecture bestLecture = null; 733 for (Lecture l : lectures) { 734 int val = test(assignment, newStudent, l); 735 if (val < 0) 736 continue; 737 if (bestLecture == null || bestValue > val) { 738 bestValue = val; 739 bestLecture = l; 740 } 741 } 742 lecture = bestLecture; 743 } 744 745 if (lecture == null) 746 return false; 747 if (newStudent != null && !newStudent.canEnroll(lecture)) 748 return false; 749 studentLectures.add(lecture); 750 if (lecture.getChildrenSubpartIds() != null) { 751 for (Long subpartId: lecture.getChildrenSubpartIds()) { 752 if (!addLectures(assignment, student, newStudent, studentLectures, lecture.getChildren(subpartId))) 753 return false; 754 } 755 } 756 757 return true; 758 } 759 760 public int test(Assignment<Lecture, Placement> assignment, Student student, Lecture lecture) { 761 if (assignment.getValue(lecture) == null) 762 return -1; 763 double studentWeight = student.getOfferingWeight(lecture.getConfiguration()); 764 if (lecture.nrWeightedStudents() + studentWeight > sEps + lecture.classLimit(assignment)) 765 return -1; 766 if (!student.canEnroll(lecture)) 767 return -1; 768 769 int test = 0; 770 for (Lecture x : student.getLectures()) { 771 if (assignment.getValue(x) == null) 772 continue; 773 if (JenrlConstraint.isInConflict(assignment.getValue(lecture), assignment.getValue(x), iModel.getDistanceMetric(), iModel.getStudentWorkDayLimit())) 774 test++; 775 } 776 test += student.countConflictPlacements(assignment.getValue(lecture)); 777 778 if (lecture.getChildrenSubpartIds() != null) { 779 for (Long subpartId: lecture.getChildrenSubpartIds()) { 780 int bestTest = -1; 781 for (Lecture child : lecture.getChildren(subpartId)) { 782 int t = test(assignment, student, child); 783 if (t < 0) 784 continue; 785 if (bestTest < 0 || bestTest > t) 786 bestTest = t; 787 } 788 if (bestTest < 0) 789 return -1; 790 test += bestTest; 791 } 792 } 793 return test; 794 } 795 796 public class MoveBetweenCfgs { 797 Configuration iFirstConfig = null; 798 Set<Lecture> iFirstLectures = new HashSet<Lecture>(); 799 Student iFirstStudent = null; 800 Configuration iSecondConfig = null; 801 Set<Lecture> iSecondLectures = new HashSet<Lecture>(); 802 Student iSecondStudent = null; 803 804 public MoveBetweenCfgs(Configuration firstConfig, Student firstStudent, Configuration secondConfig, 805 Student secondStudent) { 806 iFirstConfig = firstConfig; 807 iFirstStudent = firstStudent; 808 iSecondConfig = secondConfig; 809 iSecondStudent = secondStudent; 810 } 811 812 public Configuration firstConfiguration() { 813 return iFirstConfig; 814 } 815 816 public Student firstStudent() { 817 return iFirstStudent; 818 } 819 820 public Set<Lecture> firstLectures() { 821 return iFirstLectures; 822 } 823 824 public Configuration secondConfiguration() { 825 return iSecondConfig; 826 } 827 828 public Student secondStudent() { 829 return iSecondStudent; 830 } 831 832 public Set<Lecture> secondLectures() { 833 return iSecondLectures; 834 } 835 836 public MoveBetweenCfgs getUndoMove() { 837 MoveBetweenCfgs ret = new MoveBetweenCfgs(iSecondConfig, iFirstStudent, iFirstConfig, iSecondStudent); 838 ret.secondLectures().addAll(iFirstLectures); 839 ret.firstLectures().addAll(iSecondLectures); 840 return ret; 841 } 842 843 public boolean perform(Assignment<Lecture, Placement> assignment) { 844 double conflicts = firstLectures().iterator().next().getModel().getCriterion(StudentConflict.class).getValue(assignment) + 845 firstLectures().iterator().next().getModel().getCriterion(StudentCommittedConflict.class).getValue(assignment); 846 firstStudent().removeConfiguration(firstConfiguration()); 847 firstStudent().addConfiguration(secondConfiguration()); 848 for (Lecture lecture : firstStudent().getLectures()) { 849 850 for (Lecture firstLecture : firstLectures()) { 851 if (firstLecture.equals(lecture)) 852 continue; 853 if (firstLectures().contains(lecture) 854 && firstLecture.getClassId().compareTo(lecture.getClassId()) > 0) 855 continue; 856 857 JenrlConstraint jenrl = firstLecture.jenrlConstraint(lecture); 858 if (jenrl == null) 859 continue; 860 jenrl.decJenrl(assignment, firstStudent()); 861 if (jenrl.getNrStudents() == 0) { 862 jenrl.getContext(assignment).unassigned(assignment, null); 863 Object[] vars = jenrl.variables().toArray(); 864 for (int k = 0; k < vars.length; k++) 865 jenrl.removeVariable((Lecture) vars[k]); 866 iModel.removeConstraint(jenrl); 867 } 868 } 869 } 870 871 if (secondStudent() != null) { 872 secondStudent().removeConfiguration(secondConfiguration()); 873 secondStudent().addConfiguration(firstConfiguration()); 874 for (Lecture lecture : secondStudent().getLectures()) { 875 876 for (Lecture secondLecture : secondLectures()) { 877 if (secondLecture.equals(lecture)) 878 continue; 879 if (secondLectures().contains(lecture) 880 && secondLecture.getClassId().compareTo(lecture.getClassId()) > 0) 881 continue; 882 883 JenrlConstraint jenrl = secondLecture.jenrlConstraint(lecture); 884 if (jenrl == null) 885 continue; 886 jenrl.decJenrl(assignment, secondStudent()); 887 if (jenrl.getNrStudents() == 0) { 888 jenrl.getContext(assignment).unassigned(assignment, null); 889 Object[] vars = jenrl.variables().toArray(); 890 for (int k = 0; k < vars.length; k++) 891 jenrl.removeVariable((Lecture) vars[k]); 892 iModel.removeConstraint(jenrl); 893 } 894 } 895 } 896 } 897 898 for (Lecture firstLecture : firstLectures()) { 899 firstLecture.removeStudent(assignment, firstStudent()); 900 firstStudent().removeLecture(firstLecture); 901 if (secondStudent() != null) { 902 firstLecture.addStudent(assignment, secondStudent()); 903 secondStudent().addLecture(firstLecture); 904 } 905 } 906 for (Lecture secondLecture : secondLectures()) { 907 secondLecture.addStudent(assignment, firstStudent()); 908 firstStudent().addLecture(secondLecture); 909 if (secondStudent() != null) { 910 secondLecture.removeStudent(assignment, secondStudent()); 911 secondStudent().removeLecture(secondLecture); 912 } 913 } 914 915 for (Lecture lecture : firstStudent().getLectures()) { 916 917 for (Lecture secondLecture : secondLectures()) { 918 if (secondLecture.equals(lecture)) 919 continue; 920 if (secondLectures().contains(lecture) 921 && secondLecture.getClassId().compareTo(lecture.getClassId()) > 0) 922 continue; 923 924 JenrlConstraint jenrl = secondLecture.jenrlConstraint(lecture); 925 if (jenrl == null) { 926 jenrl = new JenrlConstraint(); 927 jenrl.addVariable(secondLecture); 928 jenrl.addVariable(lecture); 929 iModel.addConstraint(jenrl); 930 } 931 jenrl.incJenrl(assignment, firstStudent()); 932 } 933 } 934 935 if (secondStudent() != null) { 936 for (Lecture lecture : secondStudent().getLectures()) { 937 938 for (Lecture firstLecture : firstLectures()) { 939 if (firstLecture.equals(lecture)) 940 continue; 941 if (firstLectures().contains(lecture) 942 && firstLecture.getClassId().compareTo(lecture.getClassId()) > 0) 943 continue; 944 945 JenrlConstraint jenrl = firstLecture.jenrlConstraint(lecture); 946 if (jenrl == null) { 947 jenrl = new JenrlConstraint(); 948 jenrl.addVariable(firstLecture); 949 jenrl.addVariable(lecture); 950 iModel.addConstraint(jenrl); 951 } 952 jenrl.incJenrl(assignment, secondStudent()); 953 } 954 } 955 } 956 return firstLectures().iterator().next().getModel().getCriterion(StudentConflict.class).getValue(assignment) + 957 firstLectures().iterator().next().getModel().getCriterion(StudentCommittedConflict.class).getValue(assignment) < conflicts; 958 } 959 960 public double getDelta(Assignment<Lecture, Placement> assignment) { 961 double delta = 0; 962 963 for (Lecture lecture : firstStudent().getLectures()) { 964 if (assignment.getValue(lecture) == null) 965 continue; 966 967 for (Lecture firstLecture : firstLectures()) { 968 if (assignment.getValue(firstLecture) == null || firstLecture.equals(lecture)) 969 continue; 970 JenrlConstraint jenrl = firstLecture.jenrlConstraint(lecture); 971 if (jenrl == null) 972 continue; 973 if (jenrl.isInConflict(assignment)) 974 delta -= jenrl.getJenrlWeight(firstStudent()); 975 } 976 977 for (Lecture secondLecture : secondLectures()) { 978 if (assignment.getValue(secondLecture) == null || secondLecture.equals(lecture)) 979 continue; 980 JenrlConstraint jenrl = secondLecture.jenrlConstraint(lecture); 981 if (jenrl != null) { 982 if (jenrl.isInConflict(assignment)) 983 delta += jenrl.getJenrlWeight(firstStudent()); 984 } else { 985 if (JenrlConstraint.isInConflict(assignment.getValue(secondLecture), assignment.getValue(lecture), iModel.getDistanceMetric(), iModel.getStudentWorkDayLimit())) 986 delta += firstStudent().getJenrlWeight(secondLecture, lecture); 987 } 988 } 989 } 990 991 if (secondStudent() != null) { 992 for (Lecture lecture : secondStudent().getLectures()) { 993 if (assignment.getValue(lecture) == null) 994 continue; 995 996 for (Lecture secondLecture : secondLectures()) { 997 if (assignment.getValue(secondLecture) == null || secondLecture.equals(lecture)) 998 continue; 999 JenrlConstraint jenrl = secondLecture.jenrlConstraint(lecture); 1000 if (jenrl == null) 1001 continue; 1002 if (jenrl.isInConflict(assignment)) 1003 delta -= jenrl.getJenrlWeight(secondStudent()); 1004 } 1005 1006 for (Lecture firstLecture : firstLectures()) { 1007 if (assignment.getValue(firstLecture) == null || firstLecture.equals(lecture)) 1008 continue; 1009 JenrlConstraint jenrl = firstLecture.jenrlConstraint(lecture); 1010 if (jenrl != null) { 1011 if (jenrl.isInConflict(assignment)) 1012 delta += jenrl.getJenrlWeight(secondStudent()); 1013 } else { 1014 if (JenrlConstraint.isInConflict(assignment.getValue(firstLecture), assignment.getValue(lecture), iModel.getDistanceMetric(), iModel.getStudentWorkDayLimit())) 1015 delta += secondStudent().getJenrlWeight(firstLecture, lecture); 1016 } 1017 } 1018 } 1019 } 1020 1021 for (Lecture firstLecture : firstLectures()) { 1022 Placement p1 = assignment.getValue(firstLecture); 1023 if (p1 == null) 1024 continue; 1025 delta -= firstStudent().countConflictPlacements(p1); 1026 if (secondStudent() != null) 1027 delta += secondStudent().countConflictPlacements(p1); 1028 } 1029 1030 for (Lecture secondLecture : secondLectures()) { 1031 Placement p2 = assignment.getValue(secondLecture); 1032 if (p2 == null) 1033 continue; 1034 delta += firstStudent().countConflictPlacements(p2); 1035 if (secondStudent() != null) 1036 delta -= secondStudent().countConflictPlacements(p2); 1037 } 1038 1039 return delta; 1040 } 1041 1042 public boolean isTabu() { 1043 return false; 1044 } 1045 1046 @Override 1047 public String toString() { 1048 return "Move{" + firstStudent() + "/" + firstConfiguration().getConfigId() + " <-> " + secondStudent() 1049 + "/" + secondConfiguration().getConfigId() + "}"; 1050 } 1051 1052 } 1053}