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 }