001 package net.sf.cpsolver.studentsct.heuristics;
002
003 import java.text.DecimalFormat;
004
005 import net.sf.cpsolver.ifs.heuristics.RoundRobinNeighbourSelection;
006 import net.sf.cpsolver.ifs.solution.Solution;
007 import net.sf.cpsolver.ifs.solver.Solver;
008 import net.sf.cpsolver.ifs.util.DataProperties;
009 import net.sf.cpsolver.studentsct.StudentSectioningModel;
010 import net.sf.cpsolver.studentsct.heuristics.selection.BacktrackSelection;
011 import net.sf.cpsolver.studentsct.heuristics.selection.BranchBoundSelection;
012 import net.sf.cpsolver.studentsct.heuristics.selection.RandomUnassignmentSelection;
013 import net.sf.cpsolver.studentsct.heuristics.selection.ResectionIncompleteStudentsSelection;
014 import net.sf.cpsolver.studentsct.heuristics.selection.ResectionUnassignedStudentsSelection;
015 import net.sf.cpsolver.studentsct.heuristics.selection.RndUnProblStudSelection;
016 import net.sf.cpsolver.studentsct.heuristics.selection.StandardSelection;
017 import net.sf.cpsolver.studentsct.heuristics.selection.SwapStudentSelection;
018
019 /**
020 * (Batch) student sectioning neighbour selection.
021 * It is based on {@link RoundRobinNeighbourSelection}, the following steps are involved:
022 * <ul>
023 * <li>Phase 1: section all students using incremental branch & bound (no unassignments) ({@link BranchBoundSelection} is used)
024 * <li>Phase 2: pick a student (one by one) with an incomplete schedule, try to find an improvement ({@link SwapStudentSelection} is used)
025 * <li>Phase 3: use standard value selection for some time ({@link StandardSelection} is used)
026 * <li>Phase 4: use backtrack neighbour selection ({@link BacktrackSelection} is used)
027 * <li>Phase 5: pick a student (one by one) with an incomplete schedule, try to find an improvement, identify problematic students
028 * ({@link SwapStudentSelection} is used)
029 * <li>Phase 6: random unassignment of some problematic students ({@link RndUnProblStudSelection} is used)
030 * <li>Phase 7: resection incomplete students ({@link ResectionIncompleteStudentsSelection} is used)
031 * <li>Phase 8: resection of students that were unassigned in step 6 ({@link ResectionUnassignedStudentsSelection} is used)
032 * <li>Phase 9: pick a student (one by one) with an incomplete schedule, try to find an improvement ({@link SwapStudentSelection} is used)
033 * <li>Phase 10: use standard value selection for some time ({@link StandardSelection} with {@link RouletteWheelRequestSelection} is used)
034 * <li>Phase 11: pick a student (one by one) with an incomplete schedule, try to find an improvement ({@link SwapStudentSelection} is used)
035 * <li>Phase 12: use backtrack neighbour selection ({@link BacktrackSelection} is used)
036 * <li>Phase 13: random unassignment of some students ({@link RandomUnassignmentSelection} is used)
037 * </ul>
038 *
039 * <br><br>
040 *
041 * @version
042 * StudentSct 1.1 (Student Sectioning)<br>
043 * Copyright (C) 2007 Tomáš Müller<br>
044 * <a href="mailto:muller@unitime.org">muller@unitime.org</a><br>
045 * Lazenska 391, 76314 Zlin, Czech Republic<br>
046 * <br>
047 * This library is free software; you can redistribute it and/or
048 * modify it under the terms of the GNU Lesser General Public
049 * License as published by the Free Software Foundation; either
050 * version 2.1 of the License, or (at your option) any later version.
051 * <br><br>
052 * This library is distributed in the hope that it will be useful,
053 * but WITHOUT ANY WARRANTY; without even the implied warranty of
054 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
055 * Lesser General Public License for more details.
056 * <br><br>
057 * You should have received a copy of the GNU Lesser General Public
058 * License along with this library; if not, write to the Free Software
059 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
060 */
061
062 public class StudentSctNeighbourSelection extends RoundRobinNeighbourSelection {
063 private static org.apache.log4j.Logger sLog = org.apache.log4j.Logger.getLogger(StudentSctNeighbourSelection.class);
064 private static DecimalFormat sDF = new DecimalFormat("0.000");
065
066 public StudentSctNeighbourSelection(DataProperties properties) throws Exception {
067 super(properties);
068 }
069
070 public void init(Solver solver) {
071 super.init(solver);
072 setup(solver);
073 }
074
075 public void setup(Solver solver) {
076 //Phase 1: section all students using incremental branch & bound (no unassignments)
077 registerSelection(new BranchBoundSelection(solver.getProperties()));
078
079 //Phase 2: pick a student (one by one) with an incomplete schedule, try to find an improvement
080 registerSelection(new SwapStudentSelection(solver.getProperties()));
081
082 //Phase 3: use standard value selection for some time
083 registerSelection(new StandardSelection(solver.getProperties(), getVariableSelection(), getValueSelection()));
084
085 //Phase 4: use backtrack neighbour selection
086 registerSelection(new BacktrackSelection(solver.getProperties()));
087
088 //Phase 5: pick a student (one by one) with an incomplete schedule, try to find an improvement, identify problematic students
089 SwapStudentSelection swapStudentSelection = new SwapStudentSelection(solver.getProperties());
090 registerSelection(swapStudentSelection);
091
092 //Phase 6: random unassignment of some problematic students
093 registerSelection(new RndUnProblStudSelection(solver.getProperties(), swapStudentSelection));
094
095 //Phase 7: resection incomplete students
096 registerSelection(new ResectionIncompleteStudentsSelection(solver.getProperties()));
097
098 //Phase 8: resection of students that were unassigned in step 6
099 registerSelection(new ResectionUnassignedStudentsSelection(solver.getProperties()));
100
101 //Phase 9: pick a student (one by one) with an incomplete schedule, try to find an improvement
102 registerSelection(new SwapStudentSelection(solver.getProperties()));
103
104 //Phase 10: use standard value selection for some time
105 registerSelection(new StandardSelection(solver.getProperties(), new RouletteWheelRequestSelection(solver.getProperties()), getValueSelection()));
106
107 //Phase 11: pick a student (one by one) with an incomplete schedule, try to find an improvement
108 registerSelection(new SwapStudentSelection(solver.getProperties()));
109
110 //Phase 12: use backtrack neighbour selection
111 registerSelection(new BacktrackSelection(solver.getProperties()));
112
113 //Phase 13: random unassignment of some students
114 registerSelection(new RandomUnassignmentSelection(solver.getProperties()));
115 }
116
117 public void changeSelection(Solution solution) {
118 super.changeSelection(solution);
119 StudentSectioningModel m = (StudentSectioningModel)solution.getModel();
120 sLog.debug("**CURR** "+
121 (m.getNrRealStudents(false)>0?"RRq:"+m.getNrAssignedRealRequests(false)+"/"+m.getNrRealRequests(false)+", ":"")+
122 (m.getNrLastLikeStudents(false)>0?"DRq:"+m.getNrAssignedLastLikeRequests(false)+"/"+m.getNrLastLikeRequests(false)+", ":"")+
123 (m.getNrRealStudents(false)>0?"RS:"+m.getNrCompleteRealStudents(false)+"/"+m.getNrRealStudents(false)+", ":"")+
124 (m.getNrLastLikeStudents(false)>0?"DS:"+m.getNrCompleteLastLikeStudents(false)+"/"+m.getNrLastLikeStudents(false)+", ":"")+
125 "V:"+sDF.format(m.getTotalValue())+
126 (m.getDistanceConflict()==null?"":", DC:"+sDF.format(m.getDistanceConflict().getTotalNrConflicts())));
127 }
128
129 }