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