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