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