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