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