    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}