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.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 boolean iUseConstruction = false; 081 private boolean iMPP = false; 082 083 public StudentSctNeighbourSelection(DataProperties properties) throws Exception { 084 super(properties); 085 iUseConstruction = properties.getPropertyBoolean("Sectioning.UsePriorityConstruction", iUseConstruction); 086 iMPP = properties.getPropertyBoolean("General.MPP", false); 087 } 088 089 @Override 090 public void init(Solver<Request, Enrollment> solver) { 091 super.init(solver); 092 setup(solver); 093 solver.setUpdateProgress(false); 094 solver.addSolverListener(this); 095 } 096 097 public void setup(Solver<Request, Enrollment> solver) { 098 if (iMPP) 099 registerSelection(new AssignInitialSelection(solver.getProperties())); 100 101 // Phase 1: section all students using incremental branch & bound (no 102 // unassignments) 103 registerSelection(iUseConstruction ? 104 new PriorityConstructionSelection(solver.getProperties()) : 105 new BranchBoundSelection(solver.getProperties())); 106 107 // Phase 2: pick a student (one by one) with an incomplete schedule, try 108 // to find an improvement 109 registerSelection(new SwapStudentSelection(solver.getProperties())); 110 111 // Phase 3: use standard value selection for some time 112 registerSelection(new StandardSelection(solver.getProperties(), getVariableSelection(), getValueSelection())); 113 114 // Phase 4: use backtrack neighbour selection 115 registerSelection(new BacktrackSelection(solver.getProperties())); 116 117 // Phase 5: pick a student (one by one) with an incomplete schedule, try 118 // to find an improvement, identify problematic students 119 SwapStudentSelection swapStudentSelection = new SwapStudentSelection(solver.getProperties()); 120 registerSelection(swapStudentSelection); 121 122 // Phase 6: random unassignment of some problematic students 123 registerSelection(new RndUnProblStudSelection(solver.getProperties(), swapStudentSelection)); 124 125 // Phase 7: resection incomplete students 126 registerSelection(new ResectionIncompleteStudentsSelection(solver.getProperties())); 127 128 // Phase 8: resection of students that were unassigned in step 6 129 registerSelection(new ResectionUnassignedStudentsSelection(solver.getProperties())); 130 131 // Phase 9: pick a student (one by one) with an incomplete schedule, try 132 // to find an improvement 133 registerSelection(new SwapStudentSelection(solver.getProperties())); 134 135 // Phase 10: use standard value selection for some time 136 registerSelection(new StandardSelection(solver.getProperties(), new RouletteWheelRequestSelection(solver.getProperties()), getValueSelection())); 137 138 // Phase 11: pick a student (one by one) with an incomplete schedule, 139 // try to find an improvement 140 registerSelection(new SwapStudentSelection(solver.getProperties())); 141 142 // Phase 12: use backtrack neighbour selection 143 registerSelection(new BacktrackSelection(solver.getProperties())); 144 145 // Phase 13: random unassignment of some students 146 registerSelection(new RandomUnassignmentSelection(solver.getProperties())); 147 } 148 149 @Override 150 public void changeSelection(int selectionIndex) { 151 super.changeSelection(selectionIndex); 152 } 153 154 @Override 155 public boolean variableSelected(Assignment<Request, Enrollment> assignment, long iteration, Request variable) { 156 return true; 157 } 158 159 @Override 160 public boolean valueSelected(Assignment<Request, Enrollment> assignment, long iteration, Request variable, Enrollment value) { 161 return true; 162 } 163 164 @Override 165 public boolean neighbourSelected(Assignment<Request, Enrollment> assignment, long iteration, Neighbour<Request, Enrollment> neighbour) { 166 return true; 167 } 168 169 @Override 170 public void neighbourFailed(Assignment<Request, Enrollment> assignment, long iteration, Neighbour<Request, Enrollment> neighbour) { 171 NeighbourSelection<Request, Enrollment> selection = getSelection(); 172 if (neighbour instanceof BranchBoundSelection.BranchBoundNeighbour && selection instanceof BranchBoundSelection) 173 ((BranchBoundSelection)selection).addStudent(((BranchBoundSelection.BranchBoundNeighbour)neighbour).getStudent()); 174 } 175 176}