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