    001package net.sf.cpsolver.studentsct.heuristics;
    002
    003import java.util.ArrayList;
    004import java.util.List;
    005import java.util.Set;
    006
    007import net.sf.cpsolver.ifs.extension.ConflictStatistics;
    008import net.sf.cpsolver.ifs.extension.Extension;
    009import net.sf.cpsolver.ifs.extension.MacPropagation;
    010import net.sf.cpsolver.ifs.extension.ViolatedInitials;
    011import net.sf.cpsolver.ifs.heuristics.GeneralValueSelection;
    012import net.sf.cpsolver.ifs.heuristics.ValueSelection;
    013import net.sf.cpsolver.ifs.solution.Solution;
    014import net.sf.cpsolver.ifs.solver.Solver;
    015import net.sf.cpsolver.ifs.util.DataProperties;
    016import net.sf.cpsolver.ifs.util.ToolBox;
    017import net.sf.cpsolver.studentsct.StudentSectioningModel;
    018import net.sf.cpsolver.studentsct.model.Enrollment;
    019import net.sf.cpsolver.studentsct.model.Request;
    020import net.sf.cpsolver.studentsct.model.Student;
    021
    022/**
    023 * Enrollment selection criterion. It is similar to
    024 * {@link GeneralValueSelection}, however, it is not allowed to assign a
    025 * enrollment to a dummy student {@link Student#isDummy()} that is conflicting
    026 * with an enrollment of a real student.
    027 *
    028 * @version StudentSct 1.2 (Student Sectioning)<br>
    029 *          Copyright (C) 2007 - 2010 Tomáš Müller<br>
    030 *          <a href="mailto:muller@unitime.org">muller@unitime.org</a><br>
    031 *          <a href="http://muller.unitime.org">http://muller.unitime.org</a><br>
    032 * <br>
    033 *          This library is free software; you can redistribute it and/or modify
    034 *          it under the terms of the GNU Lesser General Public License as
    035 *          published by the Free Software Foundation; either version 3 of the
    036 *          License, or (at your option) any later version. <br>
    037 * <br>
    038 *          This library is distributed in the hope that it will be useful, but
    039 *          WITHOUT ANY WARRANTY; without even the implied warranty of
    040 *          MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
    041 *          Lesser General Public License for more details. <br>
    042 * <br>
    043 *          You should have received a copy of the GNU Lesser General Public
    044 *          License along with this library; if not see
    045 *          <a href='http://www.gnu.org/licenses/'>http://www.gnu.org/licenses/</a>.
    046 */
    047public class EnrollmentSelection implements ValueSelection<Request, Enrollment> {
    048    private double iRandomWalkProb = 0.0;
    049    private double iInitialSelectionProb = 0.0;
    050    private double iGoodSelectionProb = 0.0;
    051    private int iMPPLimit = -1;
    052
    053    private double iWeightDeltaInitialAssignment = 0.0;
    054    private double iWeightPotentialConflicts = 0.0;
    055    private double iWeightWeightedCoflicts = 0.0;
    056    private double iWeightCoflicts = 1.0;
    057    private double iWeightNrAssignments = 0.5;
    058    private double iWeightValue = 0.0;
    059
    060    protected int iTabuSize = 0;
    061    protected List<Enrollment> iTabu = null;
    062    protected int iTabuPos = 0;
    063
    064    private boolean iMPP = false;
    065    private ConflictStatistics<Request, Enrollment> iStat = null;
    066    private MacPropagation<Request, Enrollment> iProp = null;
    067    private ViolatedInitials<Request, Enrollment> iViolatedInitials = null;
    068
    069    public EnrollmentSelection() {
    070    }
    071
    072    /**
    073     * Constructor
    074     *
    075     * @param properties
    076     *            input configuration
    077     */
    078    public EnrollmentSelection(DataProperties properties) {
    079        iMPP = properties.getPropertyBoolean("General.MPP", false);
    080        if (iMPP) {
    081            iMPPLimit = properties.getPropertyInt("Value.MPPLimit", -1);
    082            iInitialSelectionProb = properties.getPropertyDouble("Value.InitialSelectionProb", 0.75);
    083            iWeightDeltaInitialAssignment = properties.getPropertyDouble("Value.WeightDeltaInitialAssignments", 0.0);
    084        }
    085        iGoodSelectionProb = properties.getPropertyDouble("Value.GoodSelectionProb", 0.00);
    086        iWeightWeightedCoflicts = properties.getPropertyDouble("Value.WeightWeightedConflicts", 1.0);
    087        iWeightPotentialConflicts = properties.getPropertyDouble("Value.WeightPotentialConflicts", 0.0);
    088
    089        iRandomWalkProb = properties.getPropertyDouble("Value.RandomWalkProb", 0.0);
    090        iWeightCoflicts = properties.getPropertyDouble("Value.WeightConflicts", 1.0);
    091        iWeightNrAssignments = properties.getPropertyDouble("Value.WeightNrAssignments", 0.5);
    092        iWeightValue = properties.getPropertyDouble("Value.WeightValue", 0.0);
    093        iTabuSize = properties.getPropertyInt("Value.Tabu", 0);
    094        if (iTabuSize > 0)
    095            iTabu = new ArrayList<Enrollment>(iTabuSize);
    096    }
    097
    098    /** Initialization */
    099    @Override
    100    public void init(Solver<Request, Enrollment> solver) {
    101        for (Extension<Request, Enrollment> extension : solver.getExtensions()) {
    102            if (ConflictStatistics.class.isInstance(extension))
    103                iStat = (ConflictStatistics<Request, Enrollment>) extension;
    104            if (MacPropagation.class.isInstance(extension))
    105                iProp = (MacPropagation<Request, Enrollment>) extension;
    106            if (ViolatedInitials.class.isInstance(extension))
    107                iViolatedInitials = (ViolatedInitials<Request, Enrollment>) extension;
    108        }
    109    }
    110
    111    /** true, if it is allowed to assign given value */
    112    public boolean isAllowed(Enrollment value) {
    113        return isAllowed(value, null);
    114    }
    115
    116    /** true, if it is allowed to assign given value */
    117    public boolean isAllowed(Enrollment value, Set<Enrollment> conflicts) {
    118        if (value == null)
    119            return true;
    120        StudentSectioningModel model = (StudentSectioningModel) value.variable().getModel();
    121        if (model.getNrLastLikeRequests(false) == 0 || model.getNrRealRequests(false) == 0)
    122            return true;
    123        Request request = value.variable();
    124        if (request.getStudent().isDummy()) {
    125            if (conflicts == null)
    126                conflicts = value.variable().getModel().conflictValues(value);
    127            for (Enrollment conflict : conflicts) {
    128                if (!conflict.getRequest().getStudent().isDummy())
    129                    return false;
    130            }
    131        } else {
    132            if (conflicts == null)
    133                conflicts = value.variable().getModel().conflictValues(value);
    134            if (conflicts.size() > (request.getAssignment() == null ? 1 : 0))
    135                return false;
    136        }
    137        return true;
    138    }
    139
    140    /** Value selection */
    141    @Override
    142    public Enrollment selectValue(Solution<Request, Enrollment> solution, Request selectedVariable) {
    143        if (iMPP) {
    144            if (selectedVariable.getInitialAssignment() != null) {
    145                if (solution.getModel().unassignedVariables().isEmpty()) {
    146                    if (solution.getModel().perturbVariables().size() <= iMPPLimit)
    147                        iMPPLimit = solution.getModel().perturbVariables().size() - 1;
    148                }
    149                if (iMPPLimit >= 0 && solution.getModel().perturbVariables().size() > iMPPLimit) {
    150                    if (isAllowed(selectedVariable.getInitialAssignment()))
    151                        return selectedVariable.getInitialAssignment();
    152                }
    153                if (selectedVariable.getInitialAssignment() != null && ToolBox.random() <= iInitialSelectionProb) {
    154                    if (isAllowed(selectedVariable.getInitialAssignment()))
    155                        return selectedVariable.getInitialAssignment();
    156                }
    157            }
    158        }
    159
    160        List<Enrollment> values = selectedVariable.values();
    161        if (ToolBox.random() <= iRandomWalkProb) {
    162            Enrollment value = ToolBox.random(values);
    163            if (isAllowed(value))
    164                return value;
    165        }
    166        if (iProp != null && selectedVariable.getAssignment() == null && ToolBox.random() <= iGoodSelectionProb) {
    167            Set<Enrollment> goodValues = iProp.goodValues(selectedVariable);
    168            if (!goodValues.isEmpty())
    169                values = new ArrayList<Enrollment>(goodValues);
    170        }
    171        if (values.size() == 1) {
    172            Enrollment value = values.get(0);
    173            if (isAllowed(value))
    174                return value;
    175            else
    176                return null;
    177        }
    178
    179        List<Enrollment> bestValues = null;
    180        double bestWeightedSum = 0;
    181
    182        for (Enrollment value : values) {
    183            if (iTabu != null && iTabu.contains(value))
    184                continue;
    185            if (selectedVariable.getAssignment() != null && selectedVariable.getAssignment().equals(value))
    186                continue;
    187
    188            Set<Enrollment> conf = solution.getModel().conflictValues(value);
    189            if (conf.contains(value))
    190                continue;
    191
    192            if (!isAllowed(value, conf))
    193                continue;
    194
    195            double weightedConflicts = (iStat == null || iWeightWeightedCoflicts == 0.0 ? 0.0 : iStat.countRemovals(
    196                    solution.getIteration(), conf, value));
    197            double potentialConflicts = (iStat == null || iWeightPotentialConflicts == 0.0 ? 0.0 : iStat
    198                    .countPotentialConflicts(solution.getIteration(), value, 3));
    199
    200            long deltaInitialAssignments = 0;
    201            if (iMPP && iWeightDeltaInitialAssignment != 0.0) {
    202                if (iViolatedInitials != null) {
    203                    Set<Enrollment> violations = iViolatedInitials.getViolatedInitials(value);
    204                    if (violations != null) {
    205                        for (Enrollment aValue : violations) {
    206                            if (aValue.variable().getAssignment() == null
    207                                    || aValue.variable().getAssignment().equals(aValue))
    208                                deltaInitialAssignments += 2;
    209                        }
    210                    }
    211                }
    212                for (Enrollment aValue : conf) {
    213                    if (aValue.variable().getInitialAssignment() != null)
    214                        deltaInitialAssignments--;
    215                }
    216                if (selectedVariable.getInitialAssignment() != null
    217                        && !selectedVariable.getInitialAssignment().equals(value)) {
    218                    deltaInitialAssignments++;
    219                }
    220                if (iMPPLimit >= 0
    221                        && (solution.getModel().perturbVariables().size() + deltaInitialAssignments) > iMPPLimit)
    222                    continue;
    223            }
    224
    225            double weightedSum = (iWeightDeltaInitialAssignment * deltaInitialAssignments)
    226                    + (iWeightPotentialConflicts * potentialConflicts) + (iWeightWeightedCoflicts * weightedConflicts)
    227                    + (iWeightCoflicts * conf.size()) + (iWeightNrAssignments * value.countAssignments())
    228                    + (iWeightValue * value.toDouble());
    229
    230            if (bestValues == null || bestWeightedSum > weightedSum) {
    231                bestWeightedSum = weightedSum;
    232                if (bestValues == null)
    233                    bestValues = new ArrayList<Enrollment>();
    234                else
    235                    bestValues.clear();
    236                bestValues.add(value);
    237            } else {
    238                if (bestWeightedSum == weightedSum)
    239                    bestValues.add(value);
    240            }
    241        }
    242
    243        Enrollment selectedValue = (bestValues == null ? null : ToolBox.random(bestValues));
    244        if (selectedValue == null)
    245            selectedValue = ToolBox.random(values);
    246        if (iTabu != null) {
    247            if (iTabu.size() == iTabuPos)
    248                iTabu.add(selectedValue);
    249            else
    250                iTabu.set(iTabuPos, selectedValue);
    251            iTabuPos = (iTabuPos + 1) % iTabuSize;
    252        }
    253        return (bestValues == null ? null : selectedValue);
    254    }
    255
    256}