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