    001package org.cpsolver.studentsct.heuristics;
    002
    003import java.util.Iterator;
    004
    005import org.cpsolver.ifs.assignment.Assignment;
    006import org.cpsolver.ifs.heuristics.NeighbourSelection;
    007import org.cpsolver.ifs.heuristics.RoundRobinNeighbourSelection;
    008import org.cpsolver.ifs.model.Neighbour;
    009import org.cpsolver.ifs.solver.Solver;
    010import org.cpsolver.ifs.solver.SolverListener;
    011import org.cpsolver.ifs.util.DataProperties;
    012import org.cpsolver.studentsct.StudentSectioningModel;
    013import org.cpsolver.studentsct.filter.PriortyStudentFilter;
    014import org.cpsolver.studentsct.filter.StudentFilter;
    015import org.cpsolver.studentsct.heuristics.selection.AssignInitialSelection;
    016import org.cpsolver.studentsct.heuristics.selection.BacktrackSelection;
    017import org.cpsolver.studentsct.heuristics.selection.BranchBoundSelection;
    018import org.cpsolver.studentsct.heuristics.selection.CriticalBacktrackSelection;
    019import org.cpsolver.studentsct.heuristics.selection.CriticalCoursesBranchAndBoundSelection;
    020import org.cpsolver.studentsct.heuristics.selection.CriticalStandardSelection;
    021import org.cpsolver.studentsct.heuristics.selection.MinCreditBranchAndBoundSelection;
    022import org.cpsolver.studentsct.heuristics.selection.PriorityConstructionSelection;
    023import org.cpsolver.studentsct.heuristics.selection.RandomUnassignmentSelection;
    024import org.cpsolver.studentsct.heuristics.selection.ResectionIncompleteStudentsSelection;
    025import org.cpsolver.studentsct.heuristics.selection.ResectionUnassignedStudentsSelection;
    026import org.cpsolver.studentsct.heuristics.selection.RndUnProblStudSelection;
    027import org.cpsolver.studentsct.heuristics.selection.ShuffleStudentsSelection;
    028import org.cpsolver.studentsct.heuristics.selection.StandardSelection;
    029import org.cpsolver.studentsct.heuristics.selection.StudentEnrollmentSwapSelection;
    030import org.cpsolver.studentsct.heuristics.selection.SwapStudentSelection;
    031import org.cpsolver.studentsct.heuristics.selection.UnassignedRequestSelection;
    032import org.cpsolver.studentsct.model.Enrollment;
    033import org.cpsolver.studentsct.model.Request;
    034import org.cpsolver.studentsct.model.Request.RequestPriority;
    035import org.cpsolver.studentsct.model.Student.StudentPriority;
    036
    037/**
    038 * (Batch) student sectioning neighbour selection. It is based on
    039 * {@link RoundRobinNeighbourSelection}, the following steps are involved:
    040 * <ul>
    041 * <li>Phase 1: section all students using incremental branch &amp; bound (no
    042 * unassignments) ({@link BranchBoundSelection} is used)
    043 * <li>Phase 2: pick a student (one by one) with an incomplete schedule, try to
    044 * find an improvement ({@link SwapStudentSelection} is used)
    045 * <li>Phase 3: use standard value selection for some time (
    046 * {@link StandardSelection} is used)
    047 * <li>Phase 4: use backtrack neighbour selection ({@link BacktrackSelection} is
    048 * used)
    049 * <li>Phase 5: pick a student (one by one) with an incomplete schedule, try to
    050 * find an improvement, identify problematic students (
    051 * {@link SwapStudentSelection} is used)
    052 * <li>Phase 6: random unassignment of some problematic students (
    053 * {@link RndUnProblStudSelection} is used)
    054 * <li>Phase 7: resection incomplete students (
    055 * {@link ResectionIncompleteStudentsSelection} is used)
    056 * <li>Phase 8: resection of students that were unassigned in step 6 (
    057 * {@link ResectionUnassignedStudentsSelection} is used)
    058 * <li>Phase 9: pick a student (one by one) with an incomplete schedule, try to
    059 * find an improvement ({@link SwapStudentSelection} is used)
    060 * <li>Phase 10: use standard value selection for some time (
    061 * {@link StandardSelection} with {@link RouletteWheelRequestSelection} is used)
    062 * <li>Phase 11: pick a student (one by one) with an incomplete schedule, try to
    063 * find an improvement ({@link SwapStudentSelection} is used)
    064 * <li>Phase 12: use backtrack neighbour selection ({@link BacktrackSelection}
    065 * is used)
    066 * <li>Phase 13: random unassignment of some students (
    067 * {@link RandomUnassignmentSelection} is used)
    068 * </ul>
    069 *
    070 * <br>
    071 * <br>
    072 *
    073 * @author  Tomáš Müller
    074 * @version StudentSct 1.3 (Student Sectioning)<br>
    075 *          Copyright (C) 2007 - 2014 Tomáš Müller<br>
    076 *          <a href="mailto:muller@unitime.org">muller@unitime.org</a><br>
    077 *          <a href="http://muller.unitime.org">http://muller.unitime.org</a><br>
    078 * <br>
    079 *          This library is free software; you can redistribute it and/or modify
    080 *          it under the terms of the GNU Lesser General Public License as
    081 *          published by the Free Software Foundation; either version 3 of the
    082 *          License, or (at your option) any later version. <br>
    083 * <br>
    084 *          This library is distributed in the hope that it will be useful, but
    085 *          WITHOUT ANY WARRANTY; without even the implied warranty of
    086 *          MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
    087 *          Lesser General Public License for more details. <br>
    088 * <br>
    089 *          You should have received a copy of the GNU Lesser General Public
    090 *          License along with this library; if not see
    091 *          <a href='http://www.gnu.org/licenses/'>http://www.gnu.org/licenses/</a>.
    092 */
    093
    094public class StudentSctNeighbourSelection extends RoundRobinNeighbourSelection<Request, Enrollment> implements SolverListener<Request, Enrollment> {
    095    private boolean iUseConstruction = false;
    096    private boolean iUseCriticalCoursesSelection = true;
    097    private boolean iUseMinCreditSelection = true;
    098    private boolean iMPP = false;
    099    private boolean iShuffleStudentsSelection = false;
    100    private boolean iPriorityStudentsFirstSelection = true;
    101    private boolean iPriorityStudentsFirstAllIn = true;
    102    private int iPriorityRounds = 1, iCriticalRounds = 1;
    103    private boolean iPriorityLastRoundAllStudents = false;
    104
    105    public StudentSctNeighbourSelection(DataProperties properties) throws Exception {
    106        super(properties);
    107        iUseConstruction = properties.getPropertyBoolean("Sectioning.UsePriorityConstruction", iUseConstruction);
    108        iUseCriticalCoursesSelection = properties.getPropertyBoolean("Sectioning.UseCriticalCoursesSelection", iUseCriticalCoursesSelection);
    109        iUseMinCreditSelection = properties.getPropertyBoolean("Sectioning.UseMinCreditSelection", iUseMinCreditSelection);
    110        iMPP = properties.getPropertyBoolean("General.MPP", false);
    111        iShuffleStudentsSelection = properties.getPropertyBoolean("Shuffle.Enabled", true) && properties.getPropertyBoolean("Load.RequestGroups", false);
    112        iPriorityStudentsFirstSelection = properties.getPropertyBoolean("Sectioning.PriorityStudentsFirstSelection", iPriorityStudentsFirstSelection);
    113        iPriorityStudentsFirstAllIn = properties.getPropertyBoolean("Sectioning.PriorityStudentsFirstSelection.AllIn", iPriorityStudentsFirstAllIn);
    114        iCriticalRounds = properties.getPropertyInt("Sectioning.CriticalRounds", iCriticalRounds);
    115        iPriorityRounds = properties.getPropertyInt("Sectioning.PriorityRounds", iPriorityRounds);
    116        iPriorityLastRoundAllStudents = properties.getPropertyBoolean("Sectioning.PriorityLastRoundAllStudents", iPriorityLastRoundAllStudents);
    117    }
    118
    119    @Override
    120    public void init(Solver<Request, Enrollment> solver) {
    121        super.init(solver);
    122        setup(solver);
    123        solver.setUpdateProgress(false);
    124        for (Iterator<SolverListener<Request, Enrollment>> i = solver.getSolverListeners().iterator(); i.hasNext(); ) {
    125            SolverListener<Request, Enrollment> listener = i.next();
    126            if (listener instanceof StudentSctNeighbourSelection)
    127                i.remove();
    128        }
    129        solver.addSolverListener(this);
    130    }
    131
    132    public void setup(Solver<Request, Enrollment> solver) {
    133        if (iMPP)
    134            registerSelection(new AssignInitialSelection(solver.getProperties()));
    135
    136        if (iPriorityStudentsFirstSelection && iPriorityStudentsFirstAllIn) {
    137            if (iUseCriticalCoursesSelection) {
    138                for (StudentPriority sp: StudentPriority.values()) {
    139                    if (sp == StudentPriority.Normal) break;
    140                    for (int pr = 0; pr < iPriorityRounds; pr++ ) {
    141                        // last round >> include all students up to the selected priority
    142                        boolean includeHigherPriority = (iPriorityLastRoundAllStudents && sp.ordinal() > 0 && (pr + 1 == iPriorityRounds));
    143
    144                        StudentFilter filter = new PriortyStudentFilter(sp, includeHigherPriority);
    145
    146                        for (RequestPriority rp: RequestPriority.values()) {
    147                            for (int cr = 0; cr < iCriticalRounds; cr++ ) {
    148                                registerSelection(new CriticalCoursesBranchAndBoundSelection(solver.getProperties(), rp).withFilter(filter));
    149
    150                                registerSelection(new CriticalBacktrackSelection(solver.getProperties(), rp).withFilter(filter));
    151
    152                                registerSelection(new CriticalStandardSelection(solver.getProperties(), new UnassignedRequestSelection().withFilter(filter), getValueSelection(), rp));
    153
    154                                registerSelection(new CriticalBacktrackSelection(solver.getProperties(), rp).withFilter(filter));
    155                            }
    156                        }
    157                    }
    158                }
    159            } else {
    160                for (StudentPriority sp: StudentPriority.values()) {
    161                    if (sp == StudentPriority.Normal) break;
    162
    163                    for (int pr = 0; pr < iPriorityRounds; pr++ ) {
    164                        // last round >> include all students up to the selected priority
    165                        boolean includeHigherPriority = (iPriorityLastRoundAllStudents && sp.ordinal() > 0 && (pr + 1 == iPriorityRounds));
    166
    167                        StudentFilter filter = new PriortyStudentFilter(sp, includeHigherPriority);
    168
    169                        registerSelection(new BranchBoundSelection(solver.getProperties()).withFilter(filter));
    170
    171                        registerSelection(new BacktrackSelection(solver.getProperties()).withFilter(filter));
    172
    173                        registerSelection(new StandardSelection(solver.getProperties(), new UnassignedRequestSelection().withFilter(filter), getValueSelection()));
    174
    175                        registerSelection(new BacktrackSelection(solver.getProperties()).withFilter(filter));
    176                    }
    177                }
    178            }
    179        }
    180
    181        if (iUseCriticalCoursesSelection) {
    182            for (RequestPriority rp: RequestPriority.values()) {
    183                if (rp == RequestPriority.Normal) break;
    184                for (int cr = 0; cr < iCriticalRounds; cr++ ) {
    185                    registerSelection(new CriticalCoursesBranchAndBoundSelection(solver.getProperties(), rp));
    186
    187                    registerSelection(new CriticalBacktrackSelection(solver.getProperties(), rp));
    188
    189                    registerSelection(new CriticalStandardSelection(solver.getProperties(), getValueSelection(), rp));
    190
    191                    registerSelection(new CriticalBacktrackSelection(solver.getProperties(), rp));
    192                }
    193            }
    194        }
    195
    196        if (iPriorityStudentsFirstSelection && !iPriorityStudentsFirstAllIn) {
    197            for (StudentPriority sp: StudentPriority.values()) {
    198                if (sp == StudentPriority.Normal) break;
    199                if (((StudentSectioningModel)solver.currentSolution().getModel()).getNbrStudents(sp) == 0) continue;
    200
    201                for (int pr = 0; pr < iPriorityRounds; pr++ ) {
    202                    // last round >> include all students up to the selected priority
    203                    boolean includeHigherPriority = (iPriorityLastRoundAllStudents && sp.ordinal() > 0 && (pr + 1 == iPriorityRounds));
    204
    205                    StudentFilter filter = new PriortyStudentFilter(sp, includeHigherPriority);
    206
    207                    registerSelection(new BranchBoundSelection(solver.getProperties()).withFilter(filter));
    208
    209                    registerSelection(new BacktrackSelection(solver.getProperties()).withFilter(filter));
    210
    211                    registerSelection(new StandardSelection(solver.getProperties(), new UnassignedRequestSelection().withFilter(filter), getValueSelection()));
    212
    213                    registerSelection(new BacktrackSelection(solver.getProperties()).withFilter(filter));
    214                }
    215            }
    216        }
    217
    218        if (iUseMinCreditSelection)
    219            registerSelection(new MinCreditBranchAndBoundSelection(solver.getProperties()));
    220
    221        // Phase 1: section all students using incremental branch & bound (no
    222        // unassignments)
    223        registerSelection(iUseConstruction && !iUseMinCreditSelection ?
    224                new PriorityConstructionSelection(solver.getProperties()) :
    225                new BranchBoundSelection(solver.getProperties()));
    226
    227        // Phase 2: pick a student (one by one) with an incomplete schedule, try
    228        // to find an improvement
    229        registerSelection(new SwapStudentSelection(solver.getProperties()));
    230
    231        // Phase 3A: use backtrack neighbour selection
    232        registerSelection(new BacktrackSelection(solver.getProperties()));
    233
    234        // Phase 3B: enrollment swap selection
    235        registerSelection(new StudentEnrollmentSwapSelection(solver.getProperties()));
    236
    237        // Phase 4: use standard value selection for some time
    238        registerSelection(new StandardSelection(solver.getProperties(), getVariableSelection(), getValueSelection()));
    239
    240        // Phase 5: pick a student (one by one) with an incomplete schedule, try
    241        // to find an improvement, identify problematic students
    242        SwapStudentSelection swapStudentSelection = new SwapStudentSelection(solver.getProperties());
    243        registerSelection(swapStudentSelection);
    244
    245        // Phase 6: random unassignment of some problematic students
    246        registerSelection(new RndUnProblStudSelection(solver.getProperties(), swapStudentSelection));
    247
    248        // Phase 7: resection incomplete students
    249        registerSelection(new ResectionIncompleteStudentsSelection(solver.getProperties()));
    250
    251        // Phase 8: resection of students that were unassigned in step 6
    252        registerSelection(new ResectionUnassignedStudentsSelection(solver.getProperties()));
    253
    254        // Phase 9: pick a student (one by one) with an incomplete schedule, try
    255        // to find an improvement
    256        registerSelection(new SwapStudentSelection(solver.getProperties()));
    257
    258        // Phase 10: use standard value selection for some time
    259        registerSelection(new StandardSelection(solver.getProperties(), new RouletteWheelRequestSelection(solver.getProperties()), getValueSelection()));
    260
    261        // Phase 11: pick a student (one by one) with an incomplete schedule,
    262        // try to find an improvement
    263        registerSelection(new SwapStudentSelection(solver.getProperties()));
    264
    265        // Phase 12A: enrollment swap selection
    266        registerSelection(new StudentEnrollmentSwapSelection(solver.getProperties()));
    267
    268        // Phase 12B: use backtrack neighbour selection
    269        registerSelection(new BacktrackSelection(solver.getProperties()));
    270
    271        if (iShuffleStudentsSelection) {
    272            // Phase 13: try shuffling students around request groups
    273            registerSelection(new ShuffleStudentsSelection(solver.getProperties()));
    274
    275            // Phase 14: use backtrack neighbour selection to fix unassignments from the previous phase
    276            registerSelection(new BacktrackSelection(solver.getProperties()));
    277        }
    278
    279        // Phase 15: reset to best if no improvement has been done in the last cycle
    280        registerSelection(new RestoreBestSolution(solver.getProperties()));
    281
    282        // Phase 16: use backtrack neighbour selection
    283        registerSelection(new BacktrackSelection(solver.getProperties()));
    284
    285        // Phase 17: section all students using incremental branch & bound
    286        registerSelection(new BranchBoundSelection(solver.getProperties()));
    287
    288        // Phase 18: random unassignment of some students
    289        registerSelection(new RandomUnassignmentSelection(solver.getProperties()));
    290    }
    291
    292    @Override
    293    public void changeSelection(int selectionIndex) {
    294        super.changeSelection(selectionIndex);
    295    }
    296
    297    @Override
    298    public boolean variableSelected(Assignment<Request, Enrollment> assignment, long iteration, Request variable) {
    299        return true;
    300    }
    301
    302    @Override
    303    public boolean valueSelected(Assignment<Request, Enrollment> assignment, long iteration, Request variable, Enrollment value) {
    304        return true;
    305    }
    306
    307    @Override
    308    public boolean neighbourSelected(Assignment<Request, Enrollment> assignment, long iteration, Neighbour<Request, Enrollment> neighbour) {
    309        return true;
    310    }
    311
    312    @SuppressWarnings("unchecked")
    313    @Override
    314    public void neighbourFailed(Assignment<Request, Enrollment> assignment, long iteration, Neighbour<Request, Enrollment> neighbour) {
    315        NeighbourSelection<Request, Enrollment> selection = getSelection();
    316        if (selection instanceof SolverListener)
    317            ((SolverListener<Request, Enrollment>)selection).neighbourFailed(assignment, iteration, neighbour);
    318    }
    319}