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