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