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