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