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