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