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