001package org.cpsolver.studentsct.heuristics;
002
003import java.util.Iterator;
004
005import org.cpsolver.ifs.assignment.Assignment;
006import org.cpsolver.ifs.heuristics.NeighbourSelection;
007import org.cpsolver.ifs.heuristics.RoundRobinNeighbourSelection;
008import org.cpsolver.ifs.model.Neighbour;
009import org.cpsolver.ifs.solver.Solver;
010import org.cpsolver.ifs.solver.SolverListener;
011import org.cpsolver.ifs.util.DataProperties;
012import org.cpsolver.studentsct.filter.PriortyStudentFilter;
013import org.cpsolver.studentsct.filter.StudentFilter;
014import org.cpsolver.studentsct.heuristics.selection.AssignInitialSelection;
015import org.cpsolver.studentsct.heuristics.selection.BacktrackSelection;
016import org.cpsolver.studentsct.heuristics.selection.BranchBoundSelection;
017import org.cpsolver.studentsct.heuristics.selection.CriticalBacktrackSelection;
018import org.cpsolver.studentsct.heuristics.selection.CriticalCoursesBranchAndBoundSelection;
019import org.cpsolver.studentsct.heuristics.selection.CriticalStandardSelection;
020import org.cpsolver.studentsct.heuristics.selection.MinCreditBranchAndBoundSelection;
021import org.cpsolver.studentsct.heuristics.selection.PriorityConstructionSelection;
022import org.cpsolver.studentsct.heuristics.selection.RandomUnassignmentSelection;
023import org.cpsolver.studentsct.heuristics.selection.ResectionIncompleteStudentsSelection;
024import org.cpsolver.studentsct.heuristics.selection.ResectionUnassignedStudentsSelection;
025import org.cpsolver.studentsct.heuristics.selection.RndUnProblStudSelection;
026import org.cpsolver.studentsct.heuristics.selection.ShuffleStudentsSelection;
027import org.cpsolver.studentsct.heuristics.selection.StandardSelection;
028import org.cpsolver.studentsct.heuristics.selection.StudentEnrollmentSwapSelection;
029import org.cpsolver.studentsct.heuristics.selection.SwapStudentSelection;
030import org.cpsolver.studentsct.heuristics.selection.UnassignedRequestSelection;
031import org.cpsolver.studentsct.model.Enrollment;
032import org.cpsolver.studentsct.model.Request;
033import org.cpsolver.studentsct.model.Request.RequestPriority;
034import org.cpsolver.studentsct.model.Student.StudentPriority;
035
036/**
037 * (Batch) student sectioning neighbour selection. It is based on
038 * {@link RoundRobinNeighbourSelection}, the following steps are involved:
039 * <ul>
040 * <li>Phase 1: section all students using incremental branch &amp; bound (no
041 * unassignments) ({@link BranchBoundSelection} is used)
042 * <li>Phase 2: pick a student (one by one) with an incomplete schedule, try to
043 * find an improvement ({@link SwapStudentSelection} is used)
044 * <li>Phase 3: use standard value selection for some time (
045 * {@link StandardSelection} is used)
046 * <li>Phase 4: use backtrack neighbour selection ({@link BacktrackSelection} is
047 * used)
048 * <li>Phase 5: pick a student (one by one) with an incomplete schedule, try to
049 * find an improvement, identify problematic students (
050 * {@link SwapStudentSelection} is used)
051 * <li>Phase 6: random unassignment of some problematic students (
052 * {@link RndUnProblStudSelection} is used)
053 * <li>Phase 7: resection incomplete students (
054 * {@link ResectionIncompleteStudentsSelection} is used)
055 * <li>Phase 8: resection of students that were unassigned in step 6 (
056 * {@link ResectionUnassignedStudentsSelection} is used)
057 * <li>Phase 9: pick a student (one by one) with an incomplete schedule, try to
058 * find an improvement ({@link SwapStudentSelection} is used)
059 * <li>Phase 10: use standard value selection for some time (
060 * {@link StandardSelection} with {@link RouletteWheelRequestSelection} is used)
061 * <li>Phase 11: pick a student (one by one) with an incomplete schedule, try to
062 * find an improvement ({@link SwapStudentSelection} is used)
063 * <li>Phase 12: use backtrack neighbour selection ({@link BacktrackSelection}
064 * is used)
065 * <li>Phase 13: random unassignment of some students (
066 * {@link RandomUnassignmentSelection} is used)
067 * </ul>
068 * 
069 * <br>
070 * <br>
071 * 
072 * @version StudentSct 1.3 (Student Sectioning)<br>
073 *          Copyright (C) 2007 - 2014 Tomas Muller<br>
074 *          <a href="mailto:muller@unitime.org">muller@unitime.org</a><br>
075 *          <a href="http://muller.unitime.org">http://muller.unitime.org</a><br>
076 * <br>
077 *          This library is free software; you can redistribute it and/or modify
078 *          it under the terms of the GNU Lesser General Public License as
079 *          published by the Free Software Foundation; either version 3 of the
080 *          License, or (at your option) any later version. <br>
081 * <br>
082 *          This library is distributed in the hope that it will be useful, but
083 *          WITHOUT ANY WARRANTY; without even the implied warranty of
084 *          MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
085 *          Lesser General Public License for more details. <br>
086 * <br>
087 *          You should have received a copy of the GNU Lesser General Public
088 *          License along with this library; if not see
089 *          <a href='http://www.gnu.org/licenses/'>http://www.gnu.org/licenses/</a>.
090 */
091
092public class StudentSctNeighbourSelection extends RoundRobinNeighbourSelection<Request, Enrollment> implements SolverListener<Request, Enrollment> {
093    private boolean iUseConstruction = false;
094    private boolean iUseCriticalCoursesSelection = true;
095    private boolean iUseMinCreditSelection = true;
096    private boolean iMPP = false;
097    private boolean iShuffleStudentsSelection = false;
098    private boolean iPriorityStudentsFirstSelection = true;
099    private boolean iPriorityStudentsFirstAllIn = true;
100
101    public StudentSctNeighbourSelection(DataProperties properties) throws Exception {
102        super(properties);
103        iUseConstruction = properties.getPropertyBoolean("Sectioning.UsePriorityConstruction", iUseConstruction);
104        iUseCriticalCoursesSelection = properties.getPropertyBoolean("Sectioning.UseCriticalCoursesSelection", iUseCriticalCoursesSelection);
105        iUseMinCreditSelection = properties.getPropertyBoolean("Sectioning.UseMinCreditSelection", iUseMinCreditSelection);
106        iMPP = properties.getPropertyBoolean("General.MPP", false);
107        iShuffleStudentsSelection = properties.getPropertyBoolean("Shuffle.Enabled", true) && properties.getPropertyBoolean("Load.RequestGroups", false);
108        iPriorityStudentsFirstSelection = properties.getPropertyBoolean("Sectioning.PriorityStudentsFirstSelection", iPriorityStudentsFirstSelection);
109        iPriorityStudentsFirstAllIn = properties.getPropertyBoolean("Sectioning.PriorityStudentsFirstSelection.AllIn", iPriorityStudentsFirstAllIn);
110    }
111
112    @Override
113    public void init(Solver<Request, Enrollment> solver) {
114        super.init(solver);
115        setup(solver);
116        solver.setUpdateProgress(false);
117        for (Iterator<SolverListener<Request, Enrollment>> i = solver.getSolverListeners().iterator(); i.hasNext(); ) {
118            SolverListener<Request, Enrollment> listener = i.next();
119            if (listener instanceof StudentSctNeighbourSelection)
120                i.remove();
121        }
122        solver.addSolverListener(this);
123    }
124
125    public void setup(Solver<Request, Enrollment> solver) {
126        if (iMPP)
127            registerSelection(new AssignInitialSelection(solver.getProperties()));
128        
129        if (iPriorityStudentsFirstSelection && iPriorityStudentsFirstAllIn) {
130            if (iUseCriticalCoursesSelection) {
131                for (StudentPriority sp: StudentPriority.values()) {
132                    if (sp == StudentPriority.Normal) break;
133                    StudentFilter filter = new PriortyStudentFilter(sp, false);
134                    
135                    for (RequestPriority rp: RequestPriority.values()) {
136                        registerSelection(new CriticalCoursesBranchAndBoundSelection(solver.getProperties(), rp).withFilter(filter));
137                        
138                        registerSelection(new CriticalBacktrackSelection(solver.getProperties(), rp).withFilter(filter));
139                        
140                        registerSelection(new CriticalStandardSelection(solver.getProperties(), new UnassignedRequestSelection().withFilter(filter), getValueSelection(), rp));
141                        
142                        registerSelection(new CriticalBacktrackSelection(solver.getProperties(), rp).withFilter(filter));
143                    }
144                }
145            } else {
146                for (StudentPriority sp: StudentPriority.values()) {
147                    if (sp == StudentPriority.Normal) break;
148                    StudentFilter filter = new PriortyStudentFilter(sp, false);
149                
150                    registerSelection(new BranchBoundSelection(solver.getProperties()).withFilter(filter));
151                    
152                    registerSelection(new BacktrackSelection(solver.getProperties()).withFilter(filter));
153                    
154                    registerSelection(new StandardSelection(solver.getProperties(), new UnassignedRequestSelection().withFilter(filter), getValueSelection()));
155                    
156                    registerSelection(new BacktrackSelection(solver.getProperties()).withFilter(filter));
157                }
158            }
159        }
160        
161        if (iUseCriticalCoursesSelection) {
162            for (RequestPriority rp: RequestPriority.values()) {
163                if (rp == RequestPriority.Normal) break;
164                registerSelection(new CriticalCoursesBranchAndBoundSelection(solver.getProperties(), rp));
165                
166                registerSelection(new CriticalBacktrackSelection(solver.getProperties(), rp));
167                
168                registerSelection(new CriticalStandardSelection(solver.getProperties(), getValueSelection(), rp));
169                
170                registerSelection(new CriticalBacktrackSelection(solver.getProperties(), rp));
171            }
172        }
173        
174        if (iPriorityStudentsFirstSelection && !iPriorityStudentsFirstAllIn) {
175            for (StudentPriority sp: StudentPriority.values()) {
176                if (sp == StudentPriority.Normal) break;
177                StudentFilter filter = new PriortyStudentFilter(sp, false);
178            
179                registerSelection(new BranchBoundSelection(solver.getProperties()).withFilter(filter));
180                
181                registerSelection(new BacktrackSelection(solver.getProperties()).withFilter(filter));
182                
183                registerSelection(new StandardSelection(solver.getProperties(), new UnassignedRequestSelection().withFilter(filter), getValueSelection()));
184                
185                registerSelection(new BacktrackSelection(solver.getProperties()).withFilter(filter));
186            }
187        }
188        
189        if (iUseMinCreditSelection)
190            registerSelection(new MinCreditBranchAndBoundSelection(solver.getProperties()));
191        
192        // Phase 1: section all students using incremental branch & bound (no
193        // unassignments)
194        registerSelection(iUseConstruction && !iUseMinCreditSelection ?
195                new PriorityConstructionSelection(solver.getProperties()) :
196                new BranchBoundSelection(solver.getProperties()));
197
198        // Phase 2: pick a student (one by one) with an incomplete schedule, try
199        // to find an improvement
200        registerSelection(new SwapStudentSelection(solver.getProperties()));
201
202        // Phase 3A: use backtrack neighbour selection
203        registerSelection(new BacktrackSelection(solver.getProperties()));
204        
205        // Phase 3B: enrollment swap selection
206        registerSelection(new StudentEnrollmentSwapSelection(solver.getProperties()));
207        
208        // Phase 4: use standard value selection for some time
209        registerSelection(new StandardSelection(solver.getProperties(), getVariableSelection(), getValueSelection()));
210
211        // Phase 5: pick a student (one by one) with an incomplete schedule, try
212        // to find an improvement, identify problematic students
213        SwapStudentSelection swapStudentSelection = new SwapStudentSelection(solver.getProperties());
214        registerSelection(swapStudentSelection);
215
216        // Phase 6: random unassignment of some problematic students
217        registerSelection(new RndUnProblStudSelection(solver.getProperties(), swapStudentSelection));
218
219        // Phase 7: resection incomplete students
220        registerSelection(new ResectionIncompleteStudentsSelection(solver.getProperties()));
221
222        // Phase 8: resection of students that were unassigned in step 6
223        registerSelection(new ResectionUnassignedStudentsSelection(solver.getProperties()));
224
225        // Phase 9: pick a student (one by one) with an incomplete schedule, try
226        // to find an improvement
227        registerSelection(new SwapStudentSelection(solver.getProperties()));
228
229        // Phase 10: use standard value selection for some time
230        registerSelection(new StandardSelection(solver.getProperties(), new RouletteWheelRequestSelection(solver.getProperties()), getValueSelection()));
231
232        // Phase 11: pick a student (one by one) with an incomplete schedule,
233        // try to find an improvement
234        registerSelection(new SwapStudentSelection(solver.getProperties()));
235        
236        // Phase 12A: enrollment swap selection
237        registerSelection(new StudentEnrollmentSwapSelection(solver.getProperties()));
238
239        // Phase 12B: use backtrack neighbour selection
240        registerSelection(new BacktrackSelection(solver.getProperties()));
241        
242        if (iShuffleStudentsSelection) {
243            // Phase 13: try shuffling students around request groups
244            registerSelection(new ShuffleStudentsSelection(solver.getProperties()));
245            
246            // Phase 14: use backtrack neighbour selection to fix unassignments from the previous phase
247            registerSelection(new BacktrackSelection(solver.getProperties()));
248        }
249        
250        // Phase 15: reset to best if no improvement has been done in the last cycle
251        registerSelection(new RestoreBestSolution(solver.getProperties()));
252        
253        // Phase 16: random unassignment of some students
254        registerSelection(new RandomUnassignmentSelection(solver.getProperties()));
255    }
256
257    @Override
258    public void changeSelection(int selectionIndex) {
259        super.changeSelection(selectionIndex);
260    }
261
262    @Override
263    public boolean variableSelected(Assignment<Request, Enrollment> assignment, long iteration, Request variable) {
264        return true;
265    }
266
267    @Override
268    public boolean valueSelected(Assignment<Request, Enrollment> assignment, long iteration, Request variable, Enrollment value) {
269        return true;
270    }
271
272    @Override
273    public boolean neighbourSelected(Assignment<Request, Enrollment> assignment, long iteration, Neighbour<Request, Enrollment> neighbour) {
274        return true;
275    }
276
277    @SuppressWarnings("unchecked")
278    @Override
279    public void neighbourFailed(Assignment<Request, Enrollment> assignment, long iteration, Neighbour<Request, Enrollment> neighbour) {
280        NeighbourSelection<Request, Enrollment> selection = getSelection();
281        if (selection instanceof SolverListener)
282            ((SolverListener<Request, Enrollment>)selection).neighbourFailed(assignment, iteration, neighbour);
283    }
284}