001 package net.sf.cpsolver.studentsct.heuristics;
002
003 import net.sf.cpsolver.ifs.heuristics.RoundRobinNeighbourSelection;
004 import net.sf.cpsolver.ifs.solution.Solution;
005 import net.sf.cpsolver.ifs.solver.Solver;
006 import net.sf.cpsolver.ifs.util.DataProperties;
007 import net.sf.cpsolver.ifs.util.ToolBox;
008 import net.sf.cpsolver.studentsct.heuristics.selection.BacktrackSelection;
009 import net.sf.cpsolver.studentsct.heuristics.selection.BranchBoundSelection;
010 import net.sf.cpsolver.studentsct.heuristics.selection.PriorityConstructionSelection;
011 import net.sf.cpsolver.studentsct.heuristics.selection.RandomUnassignmentSelection;
012 import net.sf.cpsolver.studentsct.heuristics.selection.ResectionIncompleteStudentsSelection;
013 import net.sf.cpsolver.studentsct.heuristics.selection.ResectionUnassignedStudentsSelection;
014 import net.sf.cpsolver.studentsct.heuristics.selection.RndUnProblStudSelection;
015 import net.sf.cpsolver.studentsct.heuristics.selection.StandardSelection;
016 import net.sf.cpsolver.studentsct.heuristics.selection.SwapStudentSelection;
017 import net.sf.cpsolver.studentsct.model.Enrollment;
018 import 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 Tomas Muller<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
076 public 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 }