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