    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}