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