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