    001package net.sf.cpsolver.coursett.heuristics;
    002
    003import java.util.ArrayList;
    004import java.util.Collection;
    005import java.util.List;
    006import java.util.Set;
    007
    008import net.sf.cpsolver.coursett.criteria.TimetablingCriterion;
    009import net.sf.cpsolver.coursett.model.Lecture;
    010import net.sf.cpsolver.coursett.model.Placement;
    011import net.sf.cpsolver.coursett.model.TimetableModel;
    012import net.sf.cpsolver.ifs.criteria.Criterion;
    013import net.sf.cpsolver.ifs.extension.Extension;
    014import net.sf.cpsolver.ifs.extension.MacPropagation;
    015import net.sf.cpsolver.ifs.heuristics.ValueSelection;
    016import net.sf.cpsolver.ifs.solution.Solution;
    017import net.sf.cpsolver.ifs.solver.Solver;
    018import net.sf.cpsolver.ifs.util.DataProperties;
    019import net.sf.cpsolver.ifs.util.ToolBox;
    020
    021/**
    022 * Placement (value) selection. <br>
    023 * <br>
    024 * We have implemented a hierarchical handling of the value selection criteria
    025 * (see {@link HeuristicSelector}). <br>
    026 * <br>
    027 * The value selection heuristics also allow for random selection of a value
    028 * with a given probability (random walk, e.g., 2%) and, in the case of MPP, to
    029 * select the initial value (if it exists) with a given probability (e.g., 70%). <br>
    030 * <br>
    031 * Parameters (general):
    032 * <table border='1'>
    033 * <tr>
    034 * <th>Parameter</th>
    035 * <th>Type</th>
    036 * <th>Comment</th>
    037 * </tr>
    038 * <tr>
    039 * <td>Placement.RandomWalkProb</td>
    040 * <td>{@link Double}</td>
    041 * <td>Random walk probability</td>
    042 * </tr>
    043 * <tr>
    044 * <td>Placement.GoodSelectionProb</td>
    045 * <td>{@link Double}</td>
    046 * <td>Good value (not removed from domain) selection probability (MAC related)</td>
    047 * </tr>
    048 * <tr>
    049 * <td>Placement.TabuLength</td>
    050 * <td>{@link Integer}</td>
    051 * <td>Tabu-list length (-1 means do not use tabu-list)</td>
    052 * </tr>
    053 * <tr>
    054 * <td>Placement.MPP_InitialProb</td>
    055 * <td>{@link Double}</td>
    056 * <td>MPP initial selection probability</td>
    057 * </tr>
    058 * <tr>
    059 * <td>Placement.MPP_Limit</td>
    060 * <td>{@link Integer}</td>
    061 * <td>MPP: limit on the number of perturbations (-1 for no limit)</td>
    062 * </tr>
    063 * <tr>
    064 * <td>Placement.MPP_PenaltyLimit</td>
    065 * <td>{@link Double}</td>
    066 * <td>MPP: limit on the perturbations penalty (-1 for no limit)</td>
    067 * </tr>
    068 * </table>
    069 * <br>
    070 * Parameters (for each level of selection):
    071 * <table border='1'>
    072 * <tr>
    073 * <th>Parameter</th>
    074 * <th>Type</th>
    075 * <th>Comment</th>
    076 * </tr>
    077 * <tr>
    078 * <td>Placement.NrAssignmentsWeight1<br>
    079 * Placement.NrAssignmentsWeight2<br>
    080 * Placement.NrAssignmentsWeight3</td>
    081 * <td>{@link Double}</td>
    082 * <td>Number of previous assignments of the value weight</td>
    083 * </tr>
    084 * <tr>
    085 * <td>Placement.NrConflictsWeight1,2,3</td>
    086 * <td>{@link Double}</td>
    087 * <td>Number of conflicts weight</td>
    088 * </tr>
    089 * <tr>
    090 * <td>Placement.WeightedConflictsWeight1,2,3</td>
    091 * <td>{@link Double}</td>
    092 * <td>Weighted conflicts weight (Conflict-based Statistics related)</td>
    093 * </tr>
    094 * <tr>
    095 * <td>Placement.NrPotentialConflictsWeight1,2,3</td>
    096 * <td>{@link Double}</td>
    097 * <td>Number of potential conflicts weight (Conflict-based Statistics related)</td>
    098 * </tr>
    099 * <tr>
    100 * <td>Placement.MPP_DeltaInitialAssignmentWeight1,2,3</td>
    101 * <td>{@link Double}</td>
    102 * <td>Delta initial assigments weight (MPP, violated initials related)</td>
    103 * </tr>
    104 * <tr>
    105 * <td>Placement.NrHardStudConfsWeight1,2,3</td>
    106 * <td>{@link Double}</td>
    107 * <td>Hard student conflicts weight (student conflicts between single-section
    108 * classes)</td>
    109 * </tr>
    110 * <tr>
    111 * <td>Placement.NrStudConfsWeight1,2,3</td>
    112 * <td>{@link Double}</td>
    113 * <td>Student conflicts weight</td>
    114 * </tr>
    115 * <tr>
    116 * <td>Placement.TimePreferenceWeight1,2,3</td>
    117 * <td>{@link Double}</td>
    118 * <td>Time preference weight</td>
    119 * </tr>
    120 * <tr>
    121 * <td>Placement.DeltaTimePreferenceWeight1,2,3</td>
    122 * <td>{@link Double}</td>
    123 * <td>Time preference delta weight (difference between before and after
    124 * assignemnt of the value)</td>
    125 * </tr>
    126 * <tr>
    127 * <td>Placement.ConstrPreferenceWeight1,2,3</td>
    128 * <td>{@link Double}</td>
    129 * <td>Constraint preference weight</td>
    130 * </tr>
    131 * <tr>
    132 * <td>Placement.RoomPreferenceWeight1,2,3</td>
    133 * <td>{@link Double}</td>
    134 * <td>Room preference weight</td>
    135 * </tr>
    136 * <tr>
    137 * <td>Placement.UselessSlotsWeight1,2,3</td>
    138 * <td>{@link Double}</td>
    139 * <td>Useless slot weight</td>
    140 * </tr>
    141 * <tr>
    142 * <td>Placement.TooBigRoomWeight1,2,3</td>
    143 * <td>{@link Double}</td>
    144 * <td>Too big room weight</td>
    145 * </tr>
    146 * <tr>
    147 * <td>Placement.DistanceInstructorPreferenceWeight1,2,3</td>
    148 * <td>{@link Double}</td>
    149 * <td>Distance (of the rooms of the back-to-back classes) based instructor
    150 * preferences weight</td>
    151 * </tr>
    152 * <tr>
    153 * <td>Placement.DeptSpreadPenaltyWeight1,2,3</td>
    154 * <td>{@link Double}</td>
    155 * <td>Department spreading: penalty of when a slot over initial allowance is
    156 * used</td>
    157 * </tr>
    158 * <tr>
    159 * <td>Placement.ThresholdKoef1,2</td>
    160 * <td>{@link Double}</td>
    161 * <td>Threshold koeficient of the level</td>
    162 * </tr>
    163 * </table>
    164 *
    165 * @see PlacementSelection
    166 * @version CourseTT 1.2 (University Course Timetabling)<br>
    167 *          Copyright (C) 2006 - 2010 Tomáš Müller<br>
    168 *          <a href="mailto:muller@unitime.org">muller@unitime.org</a><br>
    169 *          <a href="http://muller.unitime.org">http://muller.unitime.org</a><br>
    170 * <br>
    171 *          This library is free software; you can redistribute it and/or modify
    172 *          it under the terms of the GNU Lesser General Public License as
    173 *          published by the Free Software Foundation; either version 3 of the
    174 *          License, or (at your option) any later version. <br>
    175 * <br>
    176 *          This library is distributed in the hope that it will be useful, but
    177 *          WITHOUT ANY WARRANTY; without even the implied warranty of
    178 *          MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
    179 *          Lesser General Public License for more details. <br>
    180 * <br>
    181 *          You should have received a copy of the GNU Lesser General Public
    182 *          License along with this library; if not see
    183 *          <a href='http://www.gnu.org/licenses/'>http://www.gnu.org/licenses/</a>.
    184 */
    185
    186public class PlacementSelection implements ValueSelection<Lecture, Placement> {
    187    static final int NR_LEVELS = 3;
    188    private static final double PRECISION = 1.0;
    189    private static boolean USE_THRESHOLD = true;
    190    private boolean iUseThreshold = USE_THRESHOLD;
    191
    192    private double iGoodSelectionProb;
    193    public static final String GOOD_SELECTION_PROB = "Placement.GoodSelectionProb";
    194    private double iRandomWalkProb;
    195    public static final String RW_SELECTION_PROB = "Placement.RandomWalkProb";
    196    private double iInitialSelectionProb;
    197    public static final String INITIAL_SELECTION_PROB = "Placement.MPP_InitialProb";
    198    private int iMPPLimit;
    199    public static final String NR_MPP_LIMIT = "Placement.MPP_Limit";
    200    private double iMPPPenaltyLimit;
    201    public static final String NR_MPP_PENALTY_LIMIT = "Placement.MPP_PenaltyLimit";
    202
    203    private double[] iThresholdKoef = new double[NR_LEVELS];
    204    public static final String NR_THRESHOLD_KOEF = "Placement.ThresholdKoef";
    205
    206    private int iTabuSize = 0;
    207    private ArrayList<Placement> iTabu = null;
    208    private int iTabuPos = 0;
    209    public static final String TABU_LENGTH = "Placement.TabuLength";
    210
    211    private MacPropagation<Lecture, Placement> iProp = null;
    212
    213    private boolean iRW = false;
    214    private boolean iMPP = false;
    215
    216    private boolean iCanUnassingSingleton = false;
    217
    218    @Override
    219    public void init(Solver<Lecture, Placement> solver) {
    220        for (Extension<Lecture, Placement> extension : solver.getExtensions()) {
    221            if (MacPropagation.class.isInstance(extension))
    222                iProp = (MacPropagation<Lecture, Placement>) extension;
    223        }
    224    }
    225
    226    public PlacementSelection(DataProperties properties) {
    227        iMPP = properties.getPropertyBoolean("General.MPP", false);
    228        iRW = properties.getPropertyBoolean("General.RandomWalk", true);
    229        iCanUnassingSingleton = properties.getPropertyBoolean("Placement.CanUnassingSingleton", iCanUnassingSingleton);
    230        iRandomWalkProb = (iRW ? properties.getPropertyDouble(RW_SELECTION_PROB, 0.00) : 0.0);
    231        iGoodSelectionProb = properties.getPropertyDouble(GOOD_SELECTION_PROB, 1.00);
    232        iInitialSelectionProb = (iMPP ? properties.getPropertyDouble(INITIAL_SELECTION_PROB, 0.75) : 0.0);
    233        iMPPLimit = (iMPP ? properties.getPropertyInt(NR_MPP_LIMIT, -1) : -1);
    234        iMPPPenaltyLimit = (iMPP ? properties.getPropertyDouble(NR_MPP_PENALTY_LIMIT, -1.0) : -1.0);
    235        iTabuSize = properties.getPropertyInt(TABU_LENGTH, -1);
    236        if (iTabuSize > 0)
    237            iTabu = new ArrayList<Placement>(iTabuSize);
    238        iUseThreshold = properties.getPropertyBoolean("Placement.UseThreshold", USE_THRESHOLD);
    239        for (int level = 0; level < NR_LEVELS; level++)
    240            iThresholdKoef[level] = (USE_THRESHOLD ? properties.getPropertyDouble(NR_THRESHOLD_KOEF + (level + 1), (level == 0 ? 0.1 : 0.0)) : 0.0);
    241    }
    242
    243    @Override
    244    public Placement selectValue(Solution<Lecture, Placement> solution, Lecture var) {
    245        if (var == null)
    246            return null;
    247        Lecture selectedVariable = var;
    248
    249        TimetableModel model = (TimetableModel) solution.getModel();
    250        if (selectedVariable.getInitialAssignment() != null) {
    251            if (iMPPLimit >= 0 && model.perturbVariables().size() >= iMPPLimit) {
    252                if (!containsItselfSingletonOrCommited(model, model.conflictValues(selectedVariable.getInitialAssignment()), selectedVariable.getInitialAssignment()))
    253                    return selectedVariable.getInitialAssignment();
    254            } else if (iMPPPenaltyLimit >= 0.0 && solution.getPerturbationsCounter() != null && solution.getPerturbationsCounter().getPerturbationPenalty(model) > iMPPPenaltyLimit) {
    255                if (!containsItselfSingletonOrCommited(model, model.conflictValues(selectedVariable.getInitialAssignment()), selectedVariable.getInitialAssignment()))
    256                    return selectedVariable.getInitialAssignment();
    257            } else if (selectedVariable.getInitialAssignment() != null && ToolBox.random() <= iInitialSelectionProb) {
    258                if (!containsItselfSingletonOrCommited(model, model.conflictValues(selectedVariable.getInitialAssignment()), selectedVariable.getInitialAssignment()))
    259                    return selectedVariable.getInitialAssignment();
    260            }
    261        }
    262
    263        List<Placement> values = selectedVariable.values();
    264        if (iRW && ToolBox.random() <= iRandomWalkProb) {
    265            for (int i = 0; i < 5; i++) {
    266                Placement ret = ToolBox.random(values);
    267                if (!containsItselfSingletonOrCommited(model, model.conflictValues(ret), ret))
    268                    return ret;
    269            }
    270        }
    271        if (iProp != null && selectedVariable.getAssignment() == null && ToolBox.random() <= iGoodSelectionProb) {
    272            Collection<Placement> goodValues = iProp.goodValues(selectedVariable);
    273            if (!goodValues.isEmpty())
    274                values = new ArrayList<Placement>(goodValues);
    275        }
    276        if (values.size() == 1) {
    277            Placement ret = values.get(0);
    278            if (!containsItselfSingletonOrCommited(model, model.conflictValues(ret), ret))
    279                return ret;
    280        }
    281
    282        long[] bestCost = new long[NR_LEVELS];
    283        List<Placement> selectionValues = null;
    284
    285        HeuristicSelector<Placement> selector = (iUseThreshold ? new HeuristicSelector<Placement>(iThresholdKoef) : null);
    286        for (Placement value : values) {
    287            if (iTabu != null && iTabu.contains(value))
    288                continue;
    289            if (selectedVariable.getAssignment() != null && selectedVariable.getAssignment().equals(value))
    290                continue;
    291
    292            Set<Placement> conflicts = value.variable().getModel().conflictValues(value);
    293
    294            if (containsItselfSingletonOrCommited(model, conflicts, value))
    295                continue;
    296
    297            if (iUseThreshold) {
    298                Double flt = selector.firstLevelThreshold();
    299                double[] costs = new double[NR_LEVELS];
    300                for (int level = 0; level < NR_LEVELS; level++) {
    301                    costs[level] = getCost(level, value, conflicts);
    302                    if (level == 0 && flt != null && costs[0] > flt.doubleValue()) {
    303                        break;
    304                    }
    305                }
    306                if (flt != null && costs[0] > flt.doubleValue())
    307                    continue;
    308                selector.add(costs, value);
    309            } else {
    310                boolean fail = false;
    311                boolean best = false;
    312                for (int level = 0; !fail && level < 1; level++) {
    313                    double val = getCost(level, value, conflicts);
    314                    long cost = Math.round(PRECISION * val);
    315                    if (selectionValues != null && !best) {
    316                        if (cost > bestCost[level]) {
    317                            fail = true;
    318                        }
    319                        if (cost < bestCost[level]) {
    320                            bestCost[level] = cost;
    321                            selectionValues.clear();
    322                            best = true;
    323                        }
    324                    } else {
    325                        bestCost[level] = cost;
    326                    }
    327                }
    328                if (selectionValues == null)
    329                    selectionValues = new ArrayList<Placement>(values.size());
    330                if (!fail)
    331                    selectionValues.add(value);
    332            }
    333        }
    334        // ToolBox.print("Best "+selectionValues.size()+" locations for variable "+selectedVariable.getId()+" have "+bestConflicts+" conflicts ("+bestRemovals+" weighted) and "+bestStudentConflicts+" ("+bestOriginalStudentConflicts+" * "+bestKoef+" + "+bestPenalty+") preference.");
    335        Placement selectedValue = null;
    336        if (iUseThreshold) {
    337            List<HeuristicSelector<Placement>.Element> selectionElements = selector.selection();
    338
    339            if (selectedVariable.getInitialAssignment() != null) {
    340                for (HeuristicSelector<Placement>.Element element : selectionElements) {
    341                    Placement value = element.getObject();
    342                    if (value.equals(selectedVariable.getInitialAssignment())) {
    343                        selectedValue = value;
    344                        break;
    345                    }
    346                }
    347                // &&
    348                // selectionValues.contains(selectedVariable.getInitialAssignment()))
    349                // return selectedVariable.getInitialAssignment();
    350            }
    351
    352            if (selectedValue == null) {
    353                HeuristicSelector<Placement>.Element selection = ToolBox.random(selectionElements);
    354                selectedValue = (selection == null ? null : selection.getObject());
    355            }
    356        } else {
    357            if (selectedVariable.getInitialAssignment() != null
    358                    && selectionValues.contains(selectedVariable.getInitialAssignment()))
    359                return selectedVariable.getInitialAssignment();
    360            selectedValue = ToolBox.random(selectionValues);
    361        }
    362        if (selectedValue != null && iTabu != null) {
    363            if (iTabu.size() == iTabuPos)
    364                iTabu.add(selectedValue);
    365            else
    366                iTabu.set(iTabuPos, selectedValue);
    367            iTabuPos = (iTabuPos + 1) % iTabuSize;
    368        }
    369        return selectedValue;
    370    }
    371
    372    public boolean containsItselfSingletonOrCommited(TimetableModel model, Set<Placement> values,
    373            Placement selectedValue) {
    374        if (values.contains(selectedValue))
    375            return true;
    376        if (model.hasConstantVariables()) {
    377            for (Placement placement : values) {
    378                Lecture lecture = placement.variable();
    379                if (lecture.isCommitted())
    380                    return true;
    381                if (!iCanUnassingSingleton && lecture.isSingleton())
    382                    return true;
    383            }
    384            return false;
    385        } else {
    386            if (iCanUnassingSingleton)
    387                return false;
    388            for (Placement placement : values) {
    389                Lecture lecture = placement.variable();
    390                if (lecture.isSingleton())
    391                    return true;
    392            }
    393            return false;
    394        }
    395    }
    396
    397    private double getCost(int level, Placement value, Set<Placement> conflicts) {
    398        double ret = 0.0;
    399        for (Criterion<Lecture, Placement> criterion: value.variable().getModel().getCriteria()) {
    400            if (criterion instanceof TimetablingCriterion) {
    401                double w = ((TimetablingCriterion)criterion).getPlacementSelectionWeight(level);
    402                if (w != 0.0)
    403                    ret += w * criterion.getValue(value, conflicts);
    404            } else {
    405                ret += criterion.getWeightedValue(value, conflicts);
    406            }
    407        }
    408        return ret;
    409    }
    410
    411}