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