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