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}