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}