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