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}