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