    001package net.sf.cpsolver.studentsct.heuristics;
    002
    003import net.sf.cpsolver.ifs.heuristics.RoundRobinNeighbourSelection;
    004import net.sf.cpsolver.ifs.solution.Solution;
    005import net.sf.cpsolver.ifs.solver.Solver;
    006import net.sf.cpsolver.ifs.util.DataProperties;
    007import net.sf.cpsolver.ifs.util.ToolBox;
    008import net.sf.cpsolver.studentsct.heuristics.selection.BacktrackSelection;
    009import net.sf.cpsolver.studentsct.heuristics.selection.BranchBoundSelection;
    010import net.sf.cpsolver.studentsct.heuristics.selection.PriorityConstructionSelection;
    011import net.sf.cpsolver.studentsct.heuristics.selection.RandomUnassignmentSelection;
    012import net.sf.cpsolver.studentsct.heuristics.selection.ResectionIncompleteStudentsSelection;
    013import net.sf.cpsolver.studentsct.heuristics.selection.ResectionUnassignedStudentsSelection;
    014import net.sf.cpsolver.studentsct.heuristics.selection.RndUnProblStudSelection;
    015import net.sf.cpsolver.studentsct.heuristics.selection.StandardSelection;
    016import net.sf.cpsolver.studentsct.heuristics.selection.SwapStudentSelection;
    017import net.sf.cpsolver.studentsct.model.Enrollment;
    018import net.sf.cpsolver.studentsct.model.Request;
    019
    020/**
    021 * (Batch) student sectioning neighbour selection. It is based on
    022 * {@link RoundRobinNeighbourSelection}, the following steps are involved:
    023 * <ul>
    024 * <li>Phase 1: section all students using incremental branch & bound (no
    025 * unassignments) ({@link BranchBoundSelection} is used)
    026 * <li>Phase 2: pick a student (one by one) with an incomplete schedule, try to
    027 * find an improvement ({@link SwapStudentSelection} is used)
    028 * <li>Phase 3: use standard value selection for some time (
    029 * {@link StandardSelection} is used)
    030 * <li>Phase 4: use backtrack neighbour selection ({@link BacktrackSelection} is
    031 * used)
    032 * <li>Phase 5: pick a student (one by one) with an incomplete schedule, try to
    033 * find an improvement, identify problematic students (
    034 * {@link SwapStudentSelection} is used)
    035 * <li>Phase 6: random unassignment of some problematic students (
    036 * {@link RndUnProblStudSelection} is used)
    037 * <li>Phase 7: resection incomplete students (
    038 * {@link ResectionIncompleteStudentsSelection} is used)
    039 * <li>Phase 8: resection of students that were unassigned in step 6 (
    040 * {@link ResectionUnassignedStudentsSelection} is used)
    041 * <li>Phase 9: pick a student (one by one) with an incomplete schedule, try to
    042 * find an improvement ({@link SwapStudentSelection} is used)
    043 * <li>Phase 10: use standard value selection for some time (
    044 * {@link StandardSelection} with {@link RouletteWheelRequestSelection} is used)
    045 * <li>Phase 11: pick a student (one by one) with an incomplete schedule, try to
    046 * find an improvement ({@link SwapStudentSelection} is used)
    047 * <li>Phase 12: use backtrack neighbour selection ({@link BacktrackSelection}
    048 * is used)
    049 * <li>Phase 13: random unassignment of some students (
    050 * {@link RandomUnassignmentSelection} is used)
    051 * </ul>
    052 *
    053 * <br>
    054 * <br>
    055 *
    056 * @version StudentSct 1.2 (Student Sectioning)<br>
    057 *          Copyright (C) 2007 - 2010 Tomáš Müller<br>
    058 *          <a href="mailto:muller@unitime.org">muller@unitime.org</a><br>
    059 *          <a href="http://muller.unitime.org">http://muller.unitime.org</a><br>
    060 * <br>
    061 *          This library is free software; you can redistribute it and/or modify
    062 *          it under the terms of the GNU Lesser General Public License as
    063 *          published by the Free Software Foundation; either version 3 of the
    064 *          License, or (at your option) any later version. <br>
    065 * <br>
    066 *          This library is distributed in the hope that it will be useful, but
    067 *          WITHOUT ANY WARRANTY; without even the implied warranty of
    068 *          MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
    069 *          Lesser General Public License for more details. <br>
    070 * <br>
    071 *          You should have received a copy of the GNU Lesser General Public
    072 *          License along with this library; if not see
    073 *          <a href='http://www.gnu.org/licenses/'>http://www.gnu.org/licenses/</a>.
    074 */
    075
    076public class StudentSctNeighbourSelection extends RoundRobinNeighbourSelection<Request, Enrollment> {
    077    private static org.apache.log4j.Logger sLog = org.apache.log4j.Logger.getLogger(StudentSctNeighbourSelection.class);
    078    private boolean iUseConstruction = false;
    079
    080    public StudentSctNeighbourSelection(DataProperties properties) throws Exception {
    081        super(properties);
    082        iUseConstruction = properties.getPropertyBoolean("Sectioning.UsePriorityConstruction", iUseConstruction);
    083    }
    084
    085    @Override
    086    public void init(Solver<Request, Enrollment> solver) {
    087        super.init(solver);
    088        setup(solver);
    089        solver.setUpdateProgress(false);
    090    }
    091
    092    public void setup(Solver<Request, Enrollment> solver) {
    093        // Phase 1: section all students using incremental branch & bound (no
    094        // unassignments)
    095        registerSelection(iUseConstruction ?
    096                new PriorityConstructionSelection(solver.getProperties()) :
    097                new BranchBoundSelection(solver.getProperties()));
    098
    099        // Phase 2: pick a student (one by one) with an incomplete schedule, try
    100        // to find an improvement
    101        registerSelection(new SwapStudentSelection(solver.getProperties()));
    102
    103        // Phase 3: use standard value selection for some time
    104        registerSelection(new StandardSelection(solver.getProperties(), getVariableSelection(), getValueSelection()));
    105
    106        // Phase 4: use backtrack neighbour selection
    107        registerSelection(new BacktrackSelection(solver.getProperties()));
    108
    109        // Phase 5: pick a student (one by one) with an incomplete schedule, try
    110        // to find an improvement, identify problematic students
    111        SwapStudentSelection swapStudentSelection = new SwapStudentSelection(solver.getProperties());
    112        registerSelection(swapStudentSelection);
    113
    114        // Phase 6: random unassignment of some problematic students
    115        registerSelection(new RndUnProblStudSelection(solver.getProperties(), swapStudentSelection));
    116
    117        // Phase 7: resection incomplete students
    118        registerSelection(new ResectionIncompleteStudentsSelection(solver.getProperties()));
    119
    120        // Phase 8: resection of students that were unassigned in step 6
    121        registerSelection(new ResectionUnassignedStudentsSelection(solver.getProperties()));
    122
    123        // Phase 9: pick a student (one by one) with an incomplete schedule, try
    124        // to find an improvement
    125        registerSelection(new SwapStudentSelection(solver.getProperties()));
    126
    127        // Phase 10: use standard value selection for some time
    128        registerSelection(new StandardSelection(solver.getProperties(), new RouletteWheelRequestSelection(solver
    129                .getProperties()), getValueSelection()));
    130
    131        // Phase 11: pick a student (one by one) with an incomplete schedule,
    132        // try to find an improvement
    133        registerSelection(new SwapStudentSelection(solver.getProperties()));
    134
    135        // Phase 12: use backtrack neighbour selection
    136        registerSelection(new BacktrackSelection(solver.getProperties()));
    137
    138        // Phase 13: random unassignment of some students
    139        registerSelection(new RandomUnassignmentSelection(solver.getProperties()));
    140    }
    141
    142    @Override
    143    public void changeSelection(Solution<Request, Enrollment> solution) {
    144        super.changeSelection(solution);
    145        sLog.debug("Current solution: " + ToolBox.dict2string(solution.getExtendedInfo(), 2));
    146    }
    147
    148}