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