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