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