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.studentsct.heuristics.selection.AssignInitialSelection;
011import org.cpsolver.studentsct.heuristics.selection.BacktrackSelection;
012import org.cpsolver.studentsct.heuristics.selection.BranchBoundSelection;
013import org.cpsolver.studentsct.heuristics.selection.CriticalBacktrackSelection;
014import org.cpsolver.studentsct.heuristics.selection.CriticalCoursesBranchAndBoundSelection;
015import org.cpsolver.studentsct.heuristics.selection.CriticalStandardSelection;
016import org.cpsolver.studentsct.heuristics.selection.MinCreditBranchAndBoundSelection;
017import org.cpsolver.studentsct.heuristics.selection.PriorityConstructionSelection;
018import org.cpsolver.studentsct.heuristics.selection.RandomUnassignmentSelection;
019import org.cpsolver.studentsct.heuristics.selection.ResectionIncompleteStudentsSelection;
020import org.cpsolver.studentsct.heuristics.selection.ResectionUnassignedStudentsSelection;
021import org.cpsolver.studentsct.heuristics.selection.RndUnProblStudSelection;
022import org.cpsolver.studentsct.heuristics.selection.ShuffleStudentsSelection;
023import org.cpsolver.studentsct.heuristics.selection.StandardSelection;
024import org.cpsolver.studentsct.heuristics.selection.StudentEnrollmentSwapSelection;
025import org.cpsolver.studentsct.heuristics.selection.SwapStudentSelection;
026import org.cpsolver.studentsct.model.Enrollment;
027import org.cpsolver.studentsct.model.Request;
028
029/**
030 * (Batch) student sectioning neighbour selection. It is based on
031 * {@link RoundRobinNeighbourSelection}, the following steps are involved:
032 * <ul>
033 * <li>Phase 1: section all students using incremental branch &amp; bound (no
034 * unassignments) ({@link BranchBoundSelection} is used)
035 * <li>Phase 2: pick a student (one by one) with an incomplete schedule, try to
036 * find an improvement ({@link SwapStudentSelection} is used)
037 * <li>Phase 3: use standard value selection for some time (
038 * {@link StandardSelection} is used)
039 * <li>Phase 4: use backtrack neighbour selection ({@link BacktrackSelection} is
040 * used)
041 * <li>Phase 5: pick a student (one by one) with an incomplete schedule, try to
042 * find an improvement, identify problematic students (
043 * {@link SwapStudentSelection} is used)
044 * <li>Phase 6: random unassignment of some problematic students (
045 * {@link RndUnProblStudSelection} is used)
046 * <li>Phase 7: resection incomplete students (
047 * {@link ResectionIncompleteStudentsSelection} is used)
048 * <li>Phase 8: resection of students that were unassigned in step 6 (
049 * {@link ResectionUnassignedStudentsSelection} is used)
050 * <li>Phase 9: pick a student (one by one) with an incomplete schedule, try to
051 * find an improvement ({@link SwapStudentSelection} is used)
052 * <li>Phase 10: use standard value selection for some time (
053 * {@link StandardSelection} with {@link RouletteWheelRequestSelection} is used)
054 * <li>Phase 11: pick a student (one by one) with an incomplete schedule, try to
055 * find an improvement ({@link SwapStudentSelection} is used)
056 * <li>Phase 12: use backtrack neighbour selection ({@link BacktrackSelection}
057 * is used)
058 * <li>Phase 13: random unassignment of some students (
059 * {@link RandomUnassignmentSelection} is used)
060 * </ul>
061 * 
062 * <br>
063 * <br>
064 * 
065 * @version StudentSct 1.3 (Student Sectioning)<br>
066 *          Copyright (C) 2007 - 2014 Tomas Muller<br>
067 *          <a href="mailto:muller@unitime.org">muller@unitime.org</a><br>
068 *          <a href="http://muller.unitime.org">http://muller.unitime.org</a><br>
069 * <br>
070 *          This library is free software; you can redistribute it and/or modify
071 *          it under the terms of the GNU Lesser General Public License as
072 *          published by the Free Software Foundation; either version 3 of the
073 *          License, or (at your option) any later version. <br>
074 * <br>
075 *          This library is distributed in the hope that it will be useful, but
076 *          WITHOUT ANY WARRANTY; without even the implied warranty of
077 *          MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
078 *          Lesser General Public License for more details. <br>
079 * <br>
080 *          You should have received a copy of the GNU Lesser General Public
081 *          License along with this library; if not see
082 *          <a href='http://www.gnu.org/licenses/'>http://www.gnu.org/licenses/</a>.
083 */
084
085public class StudentSctNeighbourSelection extends RoundRobinNeighbourSelection<Request, Enrollment> implements SolverListener<Request, Enrollment> {
086    private boolean iUseConstruction = false;
087    private boolean iUseCriticalCoursesSelection = true;
088    private boolean iUseMinCreditSelection = true;
089    private boolean iMPP = false;
090    private boolean iShuffleStudentsSelection = false;
091
092    public StudentSctNeighbourSelection(DataProperties properties) throws Exception {
093        super(properties);
094        iUseConstruction = properties.getPropertyBoolean("Sectioning.UsePriorityConstruction", iUseConstruction);
095        iUseCriticalCoursesSelection = properties.getPropertyBoolean("Sectioning.UseCriticalCoursesSelection", iUseCriticalCoursesSelection);
096        iUseMinCreditSelection = properties.getPropertyBoolean("Sectioning.UseMinCreditSelection", iUseMinCreditSelection);
097        iMPP = properties.getPropertyBoolean("General.MPP", false);
098        iShuffleStudentsSelection = properties.getPropertyBoolean("Shuffle.Enabled", true) && properties.getPropertyBoolean("Load.RequestGroups", false);
099    }
100
101    @Override
102    public void init(Solver<Request, Enrollment> solver) {
103        super.init(solver);
104        setup(solver);
105        solver.setUpdateProgress(false);
106        solver.addSolverListener(this);
107    }
108
109    public void setup(Solver<Request, Enrollment> solver) {
110        if (iMPP)
111            registerSelection(new AssignInitialSelection(solver.getProperties()));
112        
113        if (iUseCriticalCoursesSelection) {
114            registerSelection(new CriticalCoursesBranchAndBoundSelection(solver.getProperties()));
115            
116            registerSelection(new CriticalBacktrackSelection(solver.getProperties()));
117            
118            registerSelection(new CriticalStandardSelection(solver.getProperties(), getValueSelection()));
119            
120            registerSelection(new CriticalBacktrackSelection(solver.getProperties()));
121        }
122        
123        if (iUseMinCreditSelection)
124            registerSelection(new MinCreditBranchAndBoundSelection(solver.getProperties()));
125        
126        // Phase 1: section all students using incremental branch & bound (no
127        // unassignments)
128        registerSelection(iUseConstruction && !iUseMinCreditSelection ?
129                new PriorityConstructionSelection(solver.getProperties()) :
130                new BranchBoundSelection(solver.getProperties()));
131
132        // Phase 2: pick a student (one by one) with an incomplete schedule, try
133        // to find an improvement
134        registerSelection(new SwapStudentSelection(solver.getProperties()));
135
136        // Phase 3A: use backtrack neighbour selection
137        registerSelection(new BacktrackSelection(solver.getProperties()));
138        
139        // Phase 3B: enrollment swap selection
140        registerSelection(new StudentEnrollmentSwapSelection(solver.getProperties()));
141        
142        // Phase 4: use standard value selection for some time
143        registerSelection(new StandardSelection(solver.getProperties(), getVariableSelection(), getValueSelection()));
144
145        // Phase 5: pick a student (one by one) with an incomplete schedule, try
146        // to find an improvement, identify problematic students
147        SwapStudentSelection swapStudentSelection = new SwapStudentSelection(solver.getProperties());
148        registerSelection(swapStudentSelection);
149
150        // Phase 6: random unassignment of some problematic students
151        registerSelection(new RndUnProblStudSelection(solver.getProperties(), swapStudentSelection));
152
153        // Phase 7: resection incomplete students
154        registerSelection(new ResectionIncompleteStudentsSelection(solver.getProperties()));
155
156        // Phase 8: resection of students that were unassigned in step 6
157        registerSelection(new ResectionUnassignedStudentsSelection(solver.getProperties()));
158
159        // Phase 9: pick a student (one by one) with an incomplete schedule, try
160        // to find an improvement
161        registerSelection(new SwapStudentSelection(solver.getProperties()));
162
163        // Phase 10: use standard value selection for some time
164        registerSelection(new StandardSelection(solver.getProperties(), new RouletteWheelRequestSelection(solver.getProperties()), getValueSelection()));
165
166        // Phase 11: pick a student (one by one) with an incomplete schedule,
167        // try to find an improvement
168        registerSelection(new SwapStudentSelection(solver.getProperties()));
169        
170        // Phase 12A: enrollment swap selection
171        registerSelection(new StudentEnrollmentSwapSelection(solver.getProperties()));
172
173        // Phase 12B: use backtrack neighbour selection
174        registerSelection(new BacktrackSelection(solver.getProperties()));
175        
176        if (iShuffleStudentsSelection) {
177            // Phase 13: try shuffling students around request groups
178            registerSelection(new ShuffleStudentsSelection(solver.getProperties()));
179            
180            // Phase 14: use backtrack neighbour selection to fix unassignments from the previous phase
181            registerSelection(new BacktrackSelection(solver.getProperties()));
182        }
183        
184        // Phase 15: random unassignment of some students
185        registerSelection(new RandomUnassignmentSelection(solver.getProperties()));
186    }
187
188    @Override
189    public void changeSelection(int selectionIndex) {
190        super.changeSelection(selectionIndex);
191    }
192
193    @Override
194    public boolean variableSelected(Assignment<Request, Enrollment> assignment, long iteration, Request variable) {
195        return true;
196    }
197
198    @Override
199    public boolean valueSelected(Assignment<Request, Enrollment> assignment, long iteration, Request variable, Enrollment value) {
200        return true;
201    }
202
203    @Override
204    public boolean neighbourSelected(Assignment<Request, Enrollment> assignment, long iteration, Neighbour<Request, Enrollment> neighbour) {
205        return true;
206    }
207
208    @Override
209    public void neighbourFailed(Assignment<Request, Enrollment> assignment, long iteration, Neighbour<Request, Enrollment> neighbour) {
210        NeighbourSelection<Request, Enrollment> selection = getSelection();
211        if (neighbour instanceof BranchBoundSelection.BranchBoundNeighbour && selection instanceof BranchBoundSelection)
212            ((BranchBoundSelection)selection).addStudent(((BranchBoundSelection.BranchBoundNeighbour)neighbour).getStudent());
213    }
214
215}