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.ShuffleStudentsSelection;
019import org.cpsolver.studentsct.heuristics.selection.StandardSelection;
020import org.cpsolver.studentsct.heuristics.selection.SwapStudentSelection;
021import org.cpsolver.studentsct.model.Enrollment;
022import org.cpsolver.studentsct.model.Request;
023
024/**
025 * (Batch) student sectioning neighbour selection. It is based on
026 * {@link RoundRobinNeighbourSelection}, the following steps are involved:
027 * <ul>
028 * <li>Phase 1: section all students using incremental branch &amp; bound (no
029 * unassignments) ({@link BranchBoundSelection} is used)
030 * <li>Phase 2: pick a student (one by one) with an incomplete schedule, try to
031 * find an improvement ({@link SwapStudentSelection} is used)
032 * <li>Phase 3: use standard value selection for some time (
033 * {@link StandardSelection} is used)
034 * <li>Phase 4: use backtrack neighbour selection ({@link BacktrackSelection} is
035 * used)
036 * <li>Phase 5: pick a student (one by one) with an incomplete schedule, try to
037 * find an improvement, identify problematic students (
038 * {@link SwapStudentSelection} is used)
039 * <li>Phase 6: random unassignment of some problematic students (
040 * {@link RndUnProblStudSelection} is used)
041 * <li>Phase 7: resection incomplete students (
042 * {@link ResectionIncompleteStudentsSelection} is used)
043 * <li>Phase 8: resection of students that were unassigned in step 6 (
044 * {@link ResectionUnassignedStudentsSelection} is used)
045 * <li>Phase 9: pick a student (one by one) with an incomplete schedule, try to
046 * find an improvement ({@link SwapStudentSelection} is used)
047 * <li>Phase 10: use standard value selection for some time (
048 * {@link StandardSelection} with {@link RouletteWheelRequestSelection} is used)
049 * <li>Phase 11: pick a student (one by one) with an incomplete schedule, try to
050 * find an improvement ({@link SwapStudentSelection} is used)
051 * <li>Phase 12: use backtrack neighbour selection ({@link BacktrackSelection}
052 * is used)
053 * <li>Phase 13: random unassignment of some students (
054 * {@link RandomUnassignmentSelection} is used)
055 * </ul>
056 * 
057 * <br>
058 * <br>
059 * 
060 * @version StudentSct 1.3 (Student Sectioning)<br>
061 *          Copyright (C) 2007 - 2014 Tomas Muller<br>
062 *          <a href="mailto:muller@unitime.org">muller@unitime.org</a><br>
063 *          <a href="http://muller.unitime.org">http://muller.unitime.org</a><br>
064 * <br>
065 *          This library is free software; you can redistribute it and/or modify
066 *          it under the terms of the GNU Lesser General Public License as
067 *          published by the Free Software Foundation; either version 3 of the
068 *          License, or (at your option) any later version. <br>
069 * <br>
070 *          This library is distributed in the hope that it will be useful, but
071 *          WITHOUT ANY WARRANTY; without even the implied warranty of
072 *          MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
073 *          Lesser General Public License for more details. <br>
074 * <br>
075 *          You should have received a copy of the GNU Lesser General Public
076 *          License along with this library; if not see
077 *          <a href='http://www.gnu.org/licenses/'>http://www.gnu.org/licenses/</a>.
078 */
079
080public class StudentSctNeighbourSelection extends RoundRobinNeighbourSelection<Request, Enrollment> implements SolverListener<Request, Enrollment> {
081    private boolean iUseConstruction = false;
082    private boolean iMPP = false;
083    private boolean iShuffleStudentsSelection = false;
084
085    public StudentSctNeighbourSelection(DataProperties properties) throws Exception {
086        super(properties);
087        iUseConstruction = properties.getPropertyBoolean("Sectioning.UsePriorityConstruction", iUseConstruction);
088        iMPP = properties.getPropertyBoolean("General.MPP", false);
089        iShuffleStudentsSelection = properties.getPropertyBoolean("Shuffle.Enabled", true) && properties.getPropertyBoolean("Load.RequestGroups", false);
090    }
091
092    @Override
093    public void init(Solver<Request, Enrollment> solver) {
094        super.init(solver);
095        setup(solver);
096        solver.setUpdateProgress(false);
097        solver.addSolverListener(this);
098    }
099
100    public void setup(Solver<Request, Enrollment> solver) {
101        if (iMPP)
102            registerSelection(new AssignInitialSelection(solver.getProperties()));
103        
104        // Phase 1: section all students using incremental branch & bound (no
105        // unassignments)
106        registerSelection(iUseConstruction ?
107                new PriorityConstructionSelection(solver.getProperties()) :
108                new BranchBoundSelection(solver.getProperties()));
109
110        // Phase 2: pick a student (one by one) with an incomplete schedule, try
111        // to find an improvement
112        registerSelection(new SwapStudentSelection(solver.getProperties()));
113
114        // Phase 3: use standard value selection for some time
115        registerSelection(new StandardSelection(solver.getProperties(), getVariableSelection(), getValueSelection()));
116
117        // Phase 4: use backtrack neighbour selection
118        registerSelection(new BacktrackSelection(solver.getProperties()));
119
120        // Phase 5: pick a student (one by one) with an incomplete schedule, try
121        // to find an improvement, identify problematic students
122        SwapStudentSelection swapStudentSelection = new SwapStudentSelection(solver.getProperties());
123        registerSelection(swapStudentSelection);
124
125        // Phase 6: random unassignment of some problematic students
126        registerSelection(new RndUnProblStudSelection(solver.getProperties(), swapStudentSelection));
127
128        // Phase 7: resection incomplete students
129        registerSelection(new ResectionIncompleteStudentsSelection(solver.getProperties()));
130
131        // Phase 8: resection of students that were unassigned in step 6
132        registerSelection(new ResectionUnassignedStudentsSelection(solver.getProperties()));
133
134        // Phase 9: pick a student (one by one) with an incomplete schedule, try
135        // to find an improvement
136        registerSelection(new SwapStudentSelection(solver.getProperties()));
137
138        // Phase 10: use standard value selection for some time
139        registerSelection(new StandardSelection(solver.getProperties(), new RouletteWheelRequestSelection(solver.getProperties()), getValueSelection()));
140
141        // Phase 11: pick a student (one by one) with an incomplete schedule,
142        // try to find an improvement
143        registerSelection(new SwapStudentSelection(solver.getProperties()));
144
145        // Phase 12: use backtrack neighbour selection
146        registerSelection(new BacktrackSelection(solver.getProperties()));
147        
148        if (iShuffleStudentsSelection) {
149            // Phase 13: try shuffling students around request groups
150            registerSelection(new ShuffleStudentsSelection(solver.getProperties()));
151            
152            // Phase 14: use backtrack neighbour selection to fix unassignments from the previous phase
153            registerSelection(new BacktrackSelection(solver.getProperties()));
154        }
155        
156        // Phase 15: random unassignment of some students
157        registerSelection(new RandomUnassignmentSelection(solver.getProperties()));
158    }
159
160    @Override
161    public void changeSelection(int selectionIndex) {
162        super.changeSelection(selectionIndex);
163    }
164
165    @Override
166    public boolean variableSelected(Assignment<Request, Enrollment> assignment, long iteration, Request variable) {
167        return true;
168    }
169
170    @Override
171    public boolean valueSelected(Assignment<Request, Enrollment> assignment, long iteration, Request variable, Enrollment value) {
172        return true;
173    }
174
175    @Override
176    public boolean neighbourSelected(Assignment<Request, Enrollment> assignment, long iteration, Neighbour<Request, Enrollment> neighbour) {
177        return true;
178    }
179
180    @Override
181    public void neighbourFailed(Assignment<Request, Enrollment> assignment, long iteration, Neighbour<Request, Enrollment> neighbour) {
182        NeighbourSelection<Request, Enrollment> selection = getSelection();
183        if (neighbour instanceof BranchBoundSelection.BranchBoundNeighbour && selection instanceof BranchBoundSelection)
184            ((BranchBoundSelection)selection).addStudent(((BranchBoundSelection.BranchBoundNeighbour)neighbour).getStudent());
185    }
186
187}