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 & 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}