    001package org.cpsolver.coursett.heuristics;
    002
    003import java.util.ArrayList;
    004import java.util.Collection;
    005import java.util.Iterator;
    006import java.util.List;
    007
    008import org.cpsolver.coursett.model.Lecture;
    009import org.cpsolver.coursett.model.Placement;
    010import org.cpsolver.coursett.model.TimetableModel;
    011import org.cpsolver.ifs.assignment.Assignment;
    012import org.cpsolver.ifs.extension.Extension;
    013import org.cpsolver.ifs.extension.MacPropagation;
    014import org.cpsolver.ifs.heuristics.VariableSelection;
    015import org.cpsolver.ifs.solution.Solution;
    016import org.cpsolver.ifs.solver.Solver;
    017import org.cpsolver.ifs.util.DataProperties;
    018import org.cpsolver.ifs.util.ToolBox;
    019
    020
    021/**
    022 * Lecture (variable) selection. <br>
    023 * <br>
    024 * If there are one or more variables unassigned, the variable selection
    025 * criterion picks one of them randomly. We have tried several approaches using
    026 * domain sizes, number of previous assignments, numbers of constraints in which
    027 * the variable participates, etc., but there was no significant improvement in
    028 * this timetabling problem towards the random selection of an unassigned
    029 * variable. The reason is, that it is easy to go back when a wrong variable is
    030 * picked - such a variable is unassigned when there is a conflict with it in
    031 * some of the subsequent iterations. <br>
    032 * <br>
    033 * When all variables are assigned, an evaluation is made for each variable
    034 * according to the above described weights. The variable with the worst
    035 * evaluation is selected. This variable promises the best improvement in
    036 * optimization. <br>
    037 * <br>
    038 * Parameters (selection among unassigned lectures):
    039 * <table border='1' summary='Related Solver Parameters'>
    040 * <tr>
    041 * <th>Parameter</th>
    042 * <th>Type</th>
    043 * <th>Comment</th>
    044 * </tr>
    045 * <tr>
    046 * <td>Lecture.RouletteWheelSelection</td>
    047 * <td>{@link Boolean}</td>
    048 * <td>Roulette wheel selection</td>
    049 * </tr>
    050 * <tr>
    051 * <td>Lecture.RandomWalkProb</td>
    052 * <td>{@link Double}</td>
    053 * <td>Random walk probability</td>
    054 * </tr>
    055 * <tr>
    056 * <td>Lecture.DomainSizeWeight</td>
    057 * <td>{@link Double}</td>
    058 * <td>Domain size weight</td>
    059 * </tr>
    060 * <tr>
    061 * <td>Lecture.NrAssignmentsWeight</td>
    062 * <td>{@link Double}</td>
    063 * <td>Number of assignments weight</td>
    064 * </tr>
    065 * <tr>
    066 * <td>Lecture.InitialAssignmentWeight</td>
    067 * <td>{@link Double}</td>
    068 * <td>Initial assignment weight</td>
    069 * </tr>
    070 * <tr>
    071 * <td>Lecture.NrConstraintsWeight</td>
    072 * <td>{@link Double}</td>
    073 * <td>Number of constraint weight</td>
    074 * </tr>
    075 * </table>
    076 * <br>
    077 * Parameters (selection among assigned lectures, when the solution is
    078 * complete):
    079 * <table border='1' summary='Related Solver Parameters'>
    080 * <tr>
    081 * <th>Parameter</th>
    082 * <th>Type</th>
    083 * <th>Comment</th>
    084 * </tr>
    085 * <tr>
    086 * <td>Comparator.HardStudentConflictWeight</td>
    087 * <td>{@link Double}</td>
    088 * <td>Hard student conflict weight</td>
    089 * </tr>
    090 * <tr>
    091 * <td>Comparator.StudentConflictWeight</td>
    092 * <td>{@link Double}</td>
    093 * <td>Student conflict weight</td>
    094 * </tr>
    095 * <tr>
    096 * <td>Comparator.TimePreferenceWeight</td>
    097 * <td>{@link Double}</td>
    098 * <td>Time preference weight</td>
    099 * </tr>
    100 * <tr>
    101 * <td>Comparator.ContrPreferenceWeight</td>
    102 * <td>{@link Double}</td>
    103 * <td>Group constraint preference weight</td>
    104 * </tr>
    105 * <tr>
    106 * <td>Comparator.RoomPreferenceWeight</td>
    107 * <td>{@link Double}</td>
    108 * <td>Room preference weight</td>
    109 * </tr>
    110 * <tr>
    111 * <td>Comparator.UselessSlotWeight</td>
    112 * <td>{@link Double}</td>
    113 * <td>Useless slot weight</td>
    114 * </tr>
    115 * <tr>
    116 * <td>Comparator.TooBigRoomWeight</td>
    117 * <td>{@link Double}</td>
    118 * <td>Too big room weight</td>
    119 * </tr>
    120 * <tr>
    121 * <td>Comparator.DistanceInstructorPreferenceWeight</td>
    122 * <td>{@link Double}</td>
    123 * <td>Distance (of the rooms of the back-to-back classes) based instructor
    124 * preferences weight</td>
    125 * </tr>
    126 * <tr>
    127 * <td>Comparator.DeptSpreadPenaltyWeight</td>
    128 * <td>{@link Double}</td>
    129 * <td>Department balancing penalty (see
    130 * {@link org.cpsolver.coursett.constraint.DepartmentSpreadConstraint})</td>
    131 * </tr>
    132 * </table>
    133 * <br>
    134 * Parameters (selection among subset of lectures (faster)):
    135 * <table border='1' summary='Related Solver Parameters'>
    136 * <tr>
    137 * <th>Parameter</th>
    138 * <th>Type</th>
    139 * <th>Comment</th>
    140 * </tr>
    141 * <tr>
    142 * <td>Lecture.SelectionSubSet</td>
    143 * <td>{@link Boolean}</td>
    144 * <td>Selection among subset of lectures (faster)</td>
    145 * </tr>
    146 * <tr>
    147 * <td>Lecture.SelectionSubSetMinSize</td>
    148 * <td>{@link Double}</td>
    149 * <td>Minimal subset size</td>
    150 * </tr>
    151 * <tr>
    152 * <td>Lecture.SelectionSubSetPart</td>
    153 * <td>{@link Double}</td>
    154 * <td>Subset size in percentage of all lectures available for selection</td>
    155 * </tr>
    156 * </table>
    157 *
    158 * @see PlacementSelection
    159 * @version CourseTT 1.3 (University Course Timetabling)<br>
    160 *          Copyright (C) 2006 - 2014 Tomáš Müller<br>
    161 *          <a href="mailto:muller@unitime.org">muller@unitime.org</a><br>
    162 *          <a href="http://muller.unitime.org">http://muller.unitime.org</a><br>
    163 * <br>
    164 *          This library is free software; you can redistribute it and/or modify
    165 *          it under the terms of the GNU Lesser General Public License as
    166 *          published by the Free Software Foundation; either version 3 of the
    167 *          License, or (at your option) any later version. <br>
    168 * <br>
    169 *          This library is distributed in the hope that it will be useful, but
    170 *          WITHOUT ANY WARRANTY; without even the implied warranty of
    171 *          MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
    172 *          Lesser General Public License for more details. <br>
    173 * <br>
    174 *          You should have received a copy of the GNU Lesser General Public
    175 *          License along with this library; if not see
    176 *          <a href='http://www.gnu.org/licenses/'>http://www.gnu.org/licenses/</a>.
    177 */
    178public class LectureSelection implements VariableSelection<Lecture, Placement> {
    179    private double iRandomWalkProb;
    180    private double iDomainSizeWeight;
    181    private double iGoodValuesWeight;
    182    private double iConstraintsWeight;
    183    private double iInitialAssignmentWeight;
    184    private boolean iRouletteWheelSelection;
    185    private boolean iUnassignWhenNotGood;
    186
    187    private boolean iSubSetSelection;
    188    private double iSelectionSubSetPart;
    189    private int iSelectionSubSetMinSize;
    190    private boolean iInteractiveMode;
    191
    192    private boolean iRW = false;
    193    private boolean iMPP = false;
    194
    195    private MacPropagation<Lecture, Placement> iProp = null;
    196
    197    private int iTabuSize = 0;
    198    private ArrayList<Lecture> iTabu = null;
    199    private int iTabuPos = 0;
    200
    201    public LectureSelection(DataProperties properties) {
    202        iRouletteWheelSelection = properties.getPropertyBoolean("Lecture.RouletteWheelSelection", true);
    203        iUnassignWhenNotGood = properties.getPropertyBoolean("Lecture.UnassignWhenNotGood", false);
    204        iRW = properties.getPropertyBoolean("General.RandomWalk", true);
    205        iRandomWalkProb = (!iRW ? 0.0 : properties.getPropertyDouble("Lecture.RandomWalkProb", 1.00));
    206        iGoodValuesWeight = properties.getPropertyDouble("Lecture.GoodValueProb", 1.0);
    207        iDomainSizeWeight = properties.getPropertyDouble("Lecture.DomainSizeWeight", 30.0);
    208
    209        iInteractiveMode = properties.getPropertyBoolean("General.InteractiveMode", false);
    210
    211        iConstraintsWeight = properties.getPropertyDouble("Lecture.NrConstraintsWeight", 0.0);
    212        iMPP = properties.getPropertyBoolean("General.MPP", false);
    213        iInitialAssignmentWeight = (!iMPP ? 0.0 : properties.getPropertyDouble("Lecture.InitialAssignmentWeight", 20.0));
    214
    215        iSubSetSelection = properties.getPropertyBoolean("Lecture.SelectionSubSet", true);
    216        iSelectionSubSetMinSize = properties.getPropertyInt("Lecture.SelectionSubSetMinSize", 10);
    217        iSelectionSubSetPart = properties.getPropertyDouble("Lecture.SelectionSubSetPart", 0.2);
    218
    219        iTabuSize = properties.getPropertyInt("Lecture.TabuSize", 20);
    220        if (iTabuSize > 0)
    221            iTabu = new ArrayList<Lecture>(iTabuSize);
    222    }
    223
    224    @Override
    225    public void init(Solver<Lecture, Placement> solver) {
    226        for (Extension<Lecture, Placement> extension : solver.getExtensions()) {
    227            if (MacPropagation.class.isInstance(extension))
    228                iProp = (MacPropagation<Lecture, Placement>) extension;
    229        }
    230    }
    231
    232    @Override
    233    public Lecture selectVariable(Solution<Lecture, Placement> solution) {
    234        TimetableModel model = (TimetableModel) solution.getModel();
    235        Assignment<Lecture, Placement> assignment = solution.getAssignment();
    236        Collection<Lecture> unassignedVariables = model.unassignedVariables(assignment);
    237        if (iInteractiveMode) {
    238            // remove variables that have no values
    239            unassignedVariables = new ArrayList<Lecture>(unassignedVariables.size());
    240            for (Lecture variable : model.unassignedVariables(assignment)) {
    241                if (!variable.values(solution.getAssignment()).isEmpty())
    242                    unassignedVariables.add(variable);
    243            }
    244        }
    245
    246        if (unassignedVariables.isEmpty()) {
    247            Collection<Lecture> variables = model.perturbVariables(assignment);
    248            if (variables.isEmpty())
    249                variables = model.assignedVariables(assignment);
    250
    251            if (iRW && ToolBox.random() <= iRandomWalkProb)
    252                return ToolBox.random(variables);
    253
    254            List<Lecture> selectionVariables = new ArrayList<Lecture>();
    255            double worstValue = 0.0;
    256
    257            for (Iterator<Lecture> i1 = (iSubSetSelection ? ToolBox.subSet(variables, iSelectionSubSetPart, iSelectionSubSetMinSize) : variables).iterator(); i1.hasNext();) {
    258                Lecture selectedVariable = i1.next();
    259
    260                if (iTabu != null && iTabu.contains(selectedVariable))
    261                    continue;
    262
    263                double value = assignment.getValue(selectedVariable).toDouble(assignment);
    264
    265                if (selectionVariables.isEmpty() || value > worstValue) {
    266                    selectionVariables.clear();
    267                    selectionVariables.add(selectedVariable);
    268                    worstValue = value;
    269                } else if (worstValue == value) {
    270                    selectionVariables.add(selectedVariable);
    271                }
    272            }
    273
    274            Lecture selectedVariable = ToolBox.random(selectionVariables);
    275
    276            if (selectedVariable == null)
    277                selectedVariable = ToolBox.random(variables);
    278
    279            if (selectedVariable != null && iTabu != null) {
    280                if (iTabu.size() == iTabuPos)
    281                    iTabu.add(selectedVariable);
    282                else
    283                    iTabu.set(iTabuPos, selectedVariable);
    284                iTabuPos = (iTabuPos + 1) % iTabuSize;
    285            }
    286
    287            return selectedVariable;
    288        } else {
    289            if (ToolBox.random() <= iRandomWalkProb)
    290                return ToolBox.random(unassignedVariables);
    291
    292            if (iProp != null && iUnassignWhenNotGood) {
    293                List<Lecture> noGoodVariables = new ArrayList<Lecture>();
    294                for (Iterator<Lecture> i1 = ToolBox.subSet(unassignedVariables, iSelectionSubSetPart, iSelectionSubSetMinSize).iterator(); i1.hasNext();) {
    295                    Lecture variable = i1.next();
    296                    if (iProp.goodValues(assignment, variable).isEmpty())
    297                        noGoodVariables.add(variable);
    298                }
    299                if (!noGoodVariables.isEmpty()) {
    300                    if (ToolBox.random() < 0.02)
    301                        return ToolBox.random(assignment.assignedVariables());
    302                    for (int attempt = 0; attempt < 10; attempt++) {
    303                        Lecture noGoodVariable = ToolBox.random(noGoodVariables);
    304                        Placement noGoodValue = ToolBox.random(noGoodVariable.values(solution.getAssignment()));
    305                        if (!iProp.noGood(assignment, noGoodValue).isEmpty())
    306                            return ToolBox.random(iProp.noGood(assignment, noGoodValue)).variable();
    307                    }
    308                }
    309            }
    310
    311            if (iRouletteWheelSelection) {
    312                int iMaxDomainSize = 0;
    313                int iMaxGoodDomainSize = 0;
    314                int iMaxConstraints = 0;
    315                Collection<Lecture> variables = (iSubSetSelection ? ToolBox.subSet(unassignedVariables, iSelectionSubSetPart, iSelectionSubSetMinSize) : unassignedVariables);
    316                for (Lecture variable : variables) {
    317
    318                    if (iTabu != null && iTabu.contains(variable))
    319                        continue;
    320
    321                    iMaxDomainSize = Math.max(iMaxDomainSize, variable.values(solution.getAssignment()).size());
    322                    iMaxGoodDomainSize = (iProp == null ? 0 : Math.max(iMaxGoodDomainSize, iProp.goodValues(assignment, variable).size()));
    323                    iMaxConstraints = Math.max(iMaxConstraints, variable.constraints().size());
    324                }
    325
    326                List<Integer> points = new ArrayList<Integer>();
    327                int totalPoints = 0;
    328
    329                for (Lecture variable : variables) {
    330
    331                    long pointsThisVariable = Math.round(
    332                            iDomainSizeWeight * (((double) (iMaxDomainSize - variable.values(solution.getAssignment()).size())) / ((double) iMaxDomainSize)) +
    333                            (iProp == null ? 0.0 : iGoodValuesWeight * (((double) (iMaxGoodDomainSize - iProp.goodValues(assignment, variable).size())) / ((double) iMaxGoodDomainSize))) +
    334                            iConstraintsWeight * (((double) (iMaxConstraints - variable.constraints().size())) / ((double) iMaxConstraints)) +
    335                            iInitialAssignmentWeight * (variable.getInitialAssignment() != null ? model.conflictValues(assignment, variable.getInitialAssignment()).size() : 0.0));
    336                    if (pointsThisVariable > 0) {
    337                        totalPoints += pointsThisVariable;
    338                        points.add(totalPoints);
    339                    }
    340                }
    341
    342                if (totalPoints > 0) {
    343                    int rndPoints = ToolBox.random(totalPoints);
    344                    Iterator<Lecture> x = variables.iterator();
    345                    for (int i = 0; x.hasNext() && i < points.size(); i++) {
    346                        Lecture variable = x.next();
    347                        int tp = points.get(i);
    348                        if (tp > rndPoints) {
    349                            if (variable != null && iTabu != null) {
    350                                if (iTabu.size() == iTabuPos)
    351                                    iTabu.add(variable);
    352                                else
    353                                    iTabu.set(iTabuPos, variable);
    354                                iTabuPos = (iTabuPos + 1) % iTabuSize;
    355                            }
    356                            return variable;
    357                        }
    358                    }
    359                }
    360
    361            } else {
    362
    363                List<Lecture> selectionVariables = null;
    364                long bestGood = 0;
    365                for (Iterator<Lecture> i = ToolBox.subSet(unassignedVariables, iSelectionSubSetPart,
    366                        iSelectionSubSetMinSize).iterator(); i.hasNext();) {
    367                    Lecture variable = i.next();
    368
    369                    if (iTabu != null && iTabu.contains(variable))
    370                        continue;
    371
    372                    long good = (long) (iDomainSizeWeight * variable.values(solution.getAssignment()).size() +
    373                            iGoodValuesWeight * (iProp == null ? 0 : iProp.goodValues(assignment, variable).size()) +
    374                            iConstraintsWeight * variable.constraints().size() +
    375                            iInitialAssignmentWeight * (variable.getInitialAssignment() != null ? model.conflictValues(assignment, variable.getInitialAssignment()).size() : 0.0));
    376                    if (selectionVariables == null || bestGood > good) {
    377                        if (selectionVariables == null)
    378                            selectionVariables = new ArrayList<Lecture>();
    379                        else
    380                            selectionVariables.clear();
    381                        bestGood = good;
    382                        selectionVariables.add(variable);
    383                    } else if (good == bestGood) {
    384                        selectionVariables.add(variable);
    385                    }
    386                }
    387
    388                if (!selectionVariables.isEmpty()) {
    389                    Lecture selectedVariable = ToolBox.random(selectionVariables);
    390
    391                    if (selectedVariable != null && iTabu != null) {
    392                        if (iTabu.size() == iTabuPos)
    393                            iTabu.add(selectedVariable);
    394                        else
    395                            iTabu.set(iTabuPos, selectedVariable);
    396                        iTabuPos = (iTabuPos + 1) % iTabuSize;
    397                    }
    398
    399                    return selectedVariable;
    400                }
    401            }
    402
    403            Lecture selectedVariable = ToolBox.random(unassignedVariables);
    404
    405            if (selectedVariable != null && iTabu != null) {
    406                if (iTabu.size() == iTabuPos)
    407                    iTabu.add(selectedVariable);
    408                else
    409                    iTabu.set(iTabuPos, selectedVariable);
    410                iTabuPos = (iTabuPos + 1) % iTabuSize;
    411            }
    412
    413            return selectedVariable;
    414        }
    415    }
    416
    417}