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