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