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