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