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