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    }