001package org.cpsolver.studentsct.heuristics.selection;
002
003import java.util.ConcurrentModificationException;
004import java.util.Set;
005
006import org.cpsolver.ifs.assignment.Assignment;
007import org.cpsolver.ifs.heuristics.NeighbourSelection;
008import org.cpsolver.ifs.heuristics.ValueSelection;
009import org.cpsolver.ifs.heuristics.VariableSelection;
010import org.cpsolver.ifs.model.Neighbour;
011import org.cpsolver.ifs.model.SimpleNeighbour;
012import org.cpsolver.ifs.solution.Solution;
013import org.cpsolver.ifs.solver.Solver;
014import org.cpsolver.ifs.util.DataProperties;
015import org.cpsolver.ifs.util.Progress;
016import org.cpsolver.studentsct.filter.StudentFilter;
017import org.cpsolver.studentsct.heuristics.AssignmentCheck;
018import org.cpsolver.studentsct.heuristics.EnrollmentSelection;
019import org.cpsolver.studentsct.model.Enrollment;
020import org.cpsolver.studentsct.model.Request;
021import org.cpsolver.studentsct.model.Request.RequestPriority;
022
023
024/**
025 * Use the provided variable and value selection for some time. The provided
026 * variable and value selection is used for the number of iterations equal to
027 * the number of all variables in the problem. If a complete solution is found,
028 * the neighbour selection is stopped (it returns null).
029 * 
030 * <br>
031 * <br>
032 * Parameters: <br>
033 * <table border='1' summary='Related Solver Parameters'>
034 * <tr>
035 * <th>Parameter</th>
036 * <th>Type</th>
037 * <th>Comment</th>
038 * </tr>
039 * <tr>
040 * <td>Neighbour.StandardIterations</td>
041 * <td>{@link Long}</td>
042 * <td>Number of iterations to perform. If -1, number of iterations is set to
043 * the number of unassigned variables.</td>
044 * </tr>
045 * </table>
046 * <br>
047 * <br>
048 * 
049 * @version StudentSct 1.3 (Student Sectioning)<br>
050 *          Copyright (C) 2007 - 2014 Tomáš Müller<br>
051 *          <a href="mailto:muller@unitime.org">muller@unitime.org</a><br>
052 *          <a href="http://muller.unitime.org">http://muller.unitime.org</a><br>
053 * <br>
054 *          This library is free software; you can redistribute it and/or modify
055 *          it under the terms of the GNU Lesser General Public License as
056 *          published by the Free Software Foundation; either version 3 of the
057 *          License, or (at your option) any later version. <br>
058 * <br>
059 *          This library is distributed in the hope that it will be useful, but
060 *          WITHOUT ANY WARRANTY; without even the implied warranty of
061 *          MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
062 *          Lesser General Public License for more details. <br>
063 * <br>
064 *          You should have received a copy of the GNU Lesser General Public
065 *          License along with this library; if not see
066 *          <a href='http://www.gnu.org/licenses/'>http://www.gnu.org/licenses/</a>.
067 */
068public class StandardSelection implements NeighbourSelection<Request, Enrollment>, AssignmentCheck<Request, Enrollment> {
069    private long iIteration = 0;
070    protected ValueSelection<Request, Enrollment> iValueSelection = null;
071    protected VariableSelection<Request, Enrollment> iVariableSelection = null;
072    protected long iNrIterations = -1;
073    protected boolean iPreferPriorityStudents = true;
074    protected long iConflictTimeOut = -7200;
075    protected long iWorsenTimeOut = -7200;
076    protected long iTimeOut = -3600;
077    protected boolean iCanConflict = true;
078    protected boolean iCanWorsen = true;
079    protected boolean iCanWorsenCritical = false;
080    protected boolean iCanHigherPriorityConflict = true;
081
082    /**
083     * Constructor (variable and value selection are expected to be already
084     * initialized).
085     * 
086     * @param properties
087     *            configuration
088     * @param variableSelection
089     *            variable selection
090     * @param valueSelection
091     *            value selection
092     */
093    public StandardSelection(DataProperties properties, VariableSelection<Request, Enrollment> variableSelection,
094            ValueSelection<Request, Enrollment> valueSelection) {
095        iVariableSelection = variableSelection;
096        iValueSelection = valueSelection;
097        iPreferPriorityStudents = properties.getPropertyBoolean("Sectioning.PriorityStudentsFirstSelection.AllIn", true);
098        iTimeOut = properties.getPropertyLong("Neighbour.StandardTimeOut", 0);
099        if (iTimeOut < 0)
100            iTimeOut = Math.max(0, properties.getPropertyLong("Termination.TimeOut", -1l) + iTimeOut);
101        iConflictTimeOut = properties.getPropertyLong("Neighbour.StandardConflictTimeOut", - properties.getPropertyLong("Termination.TimeOut", 0) / 10);
102        if (iConflictTimeOut < 0)
103            iConflictTimeOut = Math.max(0, properties.getPropertyLong("Termination.TimeOut", -1l) + iConflictTimeOut);
104        iWorsenTimeOut = properties.getPropertyLong("Neighbour.StandardWorsenTimeOut", - 3 * properties.getPropertyLong("Termination.TimeOut", 0) / 10);
105        if (iWorsenTimeOut < 0)
106            iWorsenTimeOut = Math.max(0, properties.getPropertyLong("Termination.TimeOut", -1l) + iWorsenTimeOut);
107        iCanConflict = properties.getPropertyBoolean("Neighbour.StandardCanConflict", true);
108        iCanWorsen = properties.getPropertyBoolean("Neighbour.StandardCanWorsen", true);
109        iCanHigherPriorityConflict = properties.getPropertyBoolean("Neighbour.StandardCanHigherPriorityConflict", true);
110        iCanWorsenCritical = properties.getPropertyBoolean("Neighbour.CriticalStandardCanWorsen", false);
111    }
112
113    /** Initialization */
114    @Override
115    public void init(Solver<Request, Enrollment> solver) {
116        StudentFilter filter = null;
117        if (iVariableSelection instanceof UnassignedRequestSelection)
118            filter = ((UnassignedRequestSelection)iVariableSelection).getFilter();
119        init(solver, "Ifs" + (filter == null ? "" : " (" + filter.getName().toLowerCase() + " students)") + "...");
120    }
121    
122    protected void init(Solver<Request, Enrollment> solver, String name) {
123        iVariableSelection.init(solver);
124        iValueSelection.init(solver);
125        iIteration = 0;
126        iNrIterations = solver.getProperties().getPropertyLong("Neighbour.StandardIterations", -1);
127        if (iNrIterations < 0)
128            iNrIterations = solver.currentSolution().getModel().nrUnassignedVariables(solver.currentSolution().getAssignment());
129        if (iTimeOut > 0 && solver.currentSolution().getTime() > iTimeOut)
130            iNrIterations = 0;
131        iCanConflict = solver.getProperties().getPropertyBoolean("Neighbour.StandardCanConflict", true);
132        if (iCanConflict && iConflictTimeOut > 0 && solver.currentSolution().getTime() > iConflictTimeOut)
133            iCanConflict = false;
134        if (iCanWorsen && iWorsenTimeOut > 0 && solver.currentSolution().getTime() > iWorsenTimeOut)
135            iCanWorsen = false;
136        if (!iCanConflict)
137            name = "No-Conf " + name;
138        else if (!iCanWorsen)
139            name = "Improving " + name;
140        if (iNrIterations > 0)
141            Progress.getInstance(solver.currentSolution().getModel()).setPhase(name, iNrIterations);
142    }
143    
144    /**
145     * Check if the given conflicting enrollment can be unassigned
146     * @param conflict given enrollment
147     * @return if running MPP, do not unassign initial enrollments
148     */
149    @Override
150    public boolean canUnassign(Enrollment enrollment, Enrollment conflict, Assignment<Request, Enrollment> assignment) {
151        if (!iCanConflict) return false;
152        if (!iCanHigherPriorityConflict && conflict.getRequest().getPriority() < enrollment.getRequest().getPriority()) return false;
153        if (conflict.getRequest().isMPP() && conflict.equals(conflict.getRequest().getInitialAssignment())) return false;
154        if (conflict.getRequest().getStudent().hasMinCredit()) {
155            float credit = conflict.getRequest().getStudent().getAssignedCredit(assignment) - conflict.getCredit();
156            if (credit < conflict.getRequest().getStudent().getMinCredit()) return false;
157        }
158        if (!conflict.getRequest().isAlternative() && conflict.getRequest().getRequestPriority().isHigher(enrollment.getRequest())) return false;
159        if (iPreferPriorityStudents || conflict.getRequest().getRequestPriority().isSame(enrollment.getRequest())) {
160            if (conflict.getStudent().getPriority().isHigher(enrollment.getStudent())) return false;
161        }
162        return true;
163    }
164    
165    /**
166     * Check whether the given neighbors can be returned
167     * @return by default, any neighbors is accepted
168     */
169    public boolean accept(SimpleNeighbour<Request, Enrollment> n, Solution<Request, Enrollment> solution) {
170        if (!iCanWorsenCritical && RequestPriority.Important.isCritical(n.getVariable()))
171            return n.value(solution.getAssignment()) <= 0.0;
172        if (iCanWorsen) return true;
173        return n.value(solution.getAssignment()) <= 0.0;
174    }
175
176    /**
177     * Employ the provided {@link VariableSelection} and {@link ValueSelection}
178     * and return the selected value as {@link SimpleNeighbour}. The selection
179     * is stopped (null is returned) after the number of iterations equal to the
180     * number of variables in the problem or when a complete solution is found.
181     */
182    @Override
183    public Neighbour<Request, Enrollment> selectNeighbour(Solution<Request, Enrollment> solution) {
184        if (solution.getModel().unassignedVariables(solution.getAssignment()).isEmpty() || ++iIteration >= iNrIterations)
185            return null;
186        Progress.getInstance(solution.getModel()).incProgress();
187        attempts: for (int i = 0; i < 10; i++) {
188            try {
189                Request request = iVariableSelection.selectVariable(solution);
190                if (request == null) continue;
191                Enrollment enrollment =
192                        (iValueSelection instanceof EnrollmentSelection)
193                                ? ((EnrollmentSelection)iValueSelection).selectValue(solution, request, this)
194                                : iValueSelection.selectValue(solution, request);
195                if (enrollment == null) continue;
196                Set<Enrollment> conflicts = enrollment.variable().getModel().conflictValues(solution.getAssignment(), enrollment);
197                if (conflicts.contains(enrollment)) continue;
198                for (Enrollment conflict: conflicts)
199                    if (!canUnassign(enrollment, conflict, solution.getAssignment())) continue attempts;
200                SimpleNeighbour<Request, Enrollment> n = new SimpleNeighbour<Request, Enrollment>(request, enrollment, conflicts);
201                if (accept(n, solution)) return n;
202            } catch (ConcurrentModificationException e) {}
203        }
204        return null;
205    }
206
207}