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", 0.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, AssignmentCheck<Request, Enrollment> test) {
117        return isAllowed(assignment, value, null, test);
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, AssignmentCheck<Request, Enrollment> test) {
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            // all students are dummy or all are real
132            if (test != null) {
133                // there is an assignment check >> check if all conflicts can be unassigned
134                if (conflicts == null)
135                    conflicts = value.variable().getModel().conflictValues(assignment, value);
136                for (Enrollment conflict : conflicts)
137                    if (!test.canUnassign(value, conflict, assignment)) return false;
138            }
139            return true;
140        }
141        Request request = value.variable();
142        if (request.getStudent().isDummy()) {
143            // dummy student cannot unassign real student
144            if (conflicts == null)
145                conflicts = value.variable().getModel().conflictValues(assignment, value);
146            for (Enrollment conflict : conflicts) {
147                if (!conflict.getRequest().getStudent().isDummy())
148                    return false;
149                if (test != null && !test.canUnassign(value, conflict, assignment))
150                    return false;
151            }
152        } else {
153            // real student
154            if (conflicts == null)
155                conflicts = value.variable().getModel().conflictValues(assignment, value);
156            if (test == null) {
157                // no assignment check >> legacy behavior
158                if (conflicts.size() > (assignment.getValue(request) == null ? 1 : 0))
159                    return false;
160            } else {
161                // there is an assignment check >> check if all conflicts can be unassigned
162                for (Enrollment conflict : conflicts)
163                    if (!test.canUnassign(value, conflict, assignment))
164                        return false;
165            }
166        }
167        return true;
168    }
169
170    /** Value selection */
171    @Override
172    public Enrollment selectValue(Solution<Request, Enrollment> solution, Request selectedVariable) {
173        return selectValue(solution, selectedVariable, null);
174    }
175
176    public Enrollment selectValue(Solution<Request, Enrollment> solution, Request selectedVariable, AssignmentCheck<Request, Enrollment> test) {
177        Assignment<Request, Enrollment> assignment = solution.getAssignment();
178        if (iMPP) {
179            if (selectedVariable.getInitialAssignment() != null) {
180                if (solution.getModel().unassignedVariables(assignment).isEmpty()) {
181                    if (solution.getModel().perturbVariables(assignment).size() <= iMPPLimit)
182                        iMPPLimit = solution.getModel().perturbVariables(assignment).size() - 1;
183                }
184                if (iMPPLimit >= 0 && solution.getModel().perturbVariables(assignment).size() > iMPPLimit) {
185                    if (isAllowed(assignment, selectedVariable.getInitialAssignment(), test))
186                        return selectedVariable.getInitialAssignment();
187                }
188                if (selectedVariable.getInitialAssignment() != null && ToolBox.random() <= iInitialSelectionProb) {
189                    if (isAllowed(assignment, selectedVariable.getInitialAssignment(), test))
190                        return selectedVariable.getInitialAssignment();
191                }
192            }
193        }
194
195        List<Enrollment> values = selectedVariable.values(assignment);
196        if (ToolBox.random() <= iRandomWalkProb) {
197            Enrollment value = ToolBox.random(values);
198            if (isAllowed(assignment, value, test))
199                return value;
200        }
201        if (iProp != null && assignment.getValue(selectedVariable) == null && ToolBox.random() <= iGoodSelectionProb) {
202            Set<Enrollment> goodValues = iProp.goodValues(assignment, selectedVariable);
203            if (!goodValues.isEmpty())
204                values = new ArrayList<Enrollment>(goodValues);
205        }
206        if (values.size() == 1) {
207            Enrollment value = values.get(0);
208            if (isAllowed(assignment, value, test))
209                return value;
210            else
211                return null;
212        }
213
214        List<Enrollment> bestValues = null;
215        double bestWeightedSum = 0;
216
217        for (Enrollment value : values) {
218            if (iTabu != null && iTabu.contains(value))
219                continue;
220            if (assignment.getValue(selectedVariable) != null && assignment.getValue(selectedVariable).equals(value))
221                continue;
222
223            Set<Enrollment> conf = solution.getModel().conflictValues(assignment, value);
224            if (conf.contains(value))
225                continue;
226
227            if (!isAllowed(assignment, value, conf, test))
228                continue;
229
230            double weightedConflicts = (iStat == null || iWeightWeightedCoflicts == 0.0 ? 0.0 : iStat.countRemovals(solution.getIteration(), conf, value));
231            double potentialConflicts = (iStat == null || iWeightPotentialConflicts == 0.0 ? 0.0 : iStat.countPotentialConflicts(assignment, solution.getIteration(), value, 3));
232
233            long deltaInitialAssignments = 0;
234            if (iMPP && iWeightDeltaInitialAssignment != 0.0) {
235                if (iViolatedInitials != null) {
236                    Set<Enrollment> violations = iViolatedInitials.getViolatedInitials(value);
237                    if (violations != null) {
238                        for (Enrollment aValue : violations) {
239                            if (assignment.getValue(aValue.variable()) == null || assignment.getValue(aValue.variable()).equals(aValue))
240                                deltaInitialAssignments += 2;
241                        }
242                    }
243                }
244                for (Enrollment aValue : conf) {
245                    if (aValue.variable().getInitialAssignment() != null)
246                        deltaInitialAssignments--;
247                }
248                if (selectedVariable.getInitialAssignment() != null
249                        && !selectedVariable.getInitialAssignment().equals(value)) {
250                    deltaInitialAssignments++;
251                }
252                if (iMPPLimit >= 0 && (solution.getModel().perturbVariables(assignment).size() + deltaInitialAssignments) > iMPPLimit)
253                    continue;
254            }
255            
256            double val = value.toDouble(assignment);
257            for (Enrollment c: conf)
258                val -= c.toDouble(assignment);
259
260            double weightedSum = (iWeightDeltaInitialAssignment * deltaInitialAssignments)
261                    + (iWeightPotentialConflicts * potentialConflicts) + (iWeightWeightedCoflicts * weightedConflicts)
262                    + (iWeightCoflicts * conf.size())
263                    + (iWeightValue * val);
264
265            if (bestValues == null || bestWeightedSum > weightedSum) {
266                bestWeightedSum = weightedSum;
267                if (bestValues == null)
268                    bestValues = new ArrayList<Enrollment>();
269                else
270                    bestValues.clear();
271                bestValues.add(value);
272            } else {
273                if (bestWeightedSum == weightedSum)
274                    bestValues.add(value);
275            }
276        }
277
278        Enrollment selectedValue = (bestValues == null ? null : ToolBox.random(bestValues));
279        if (selectedValue == null)
280            selectedValue = ToolBox.random(values);
281        if (iTabu != null) {
282            if (iTabu.size() == iTabuPos)
283                iTabu.add(selectedValue);
284            else
285                iTabu.set(iTabuPos, selectedValue);
286            iTabuPos = (iTabuPos + 1) % iTabuSize;
287        }
288        return (bestValues == null ? null : selectedValue);
289    }
290
291}