001package org.cpsolver.studentsct.heuristics.selection;
002
003import java.util.Set;
004
005import org.cpsolver.ifs.assignment.Assignment;
006import org.cpsolver.ifs.heuristics.NeighbourSelection;
007import org.cpsolver.ifs.heuristics.ValueSelection;
008import org.cpsolver.ifs.heuristics.VariableSelection;
009import org.cpsolver.ifs.model.Neighbour;
010import org.cpsolver.ifs.model.SimpleNeighbour;
011import org.cpsolver.ifs.solution.Solution;
012import org.cpsolver.ifs.solver.Solver;
013import org.cpsolver.ifs.util.DataProperties;
014import org.cpsolver.ifs.util.Progress;
015import org.cpsolver.studentsct.model.Enrollment;
016import org.cpsolver.studentsct.model.Request;
017
018
019/**
020 * Use the provided variable and value selection for some time. The provided
021 * variable and value selection is used for the number of iterations equal to
022 * the number of all variables in the problem. If a complete solution is found,
023 * the neighbour selection is stopped (it returns null).
024 * 
025 * <br>
026 * <br>
027 * Parameters: <br>
028 * <table border='1' summary='Related Solver Parameters'>
029 * <tr>
030 * <th>Parameter</th>
031 * <th>Type</th>
032 * <th>Comment</th>
033 * </tr>
034 * <tr>
035 * <td>Neighbour.StandardIterations</td>
036 * <td>{@link Long}</td>
037 * <td>Number of iterations to perform. If -1, number of iterations is set to
038 * the number of unassigned variables.</td>
039 * </tr>
040 * </table>
041 * <br>
042 * <br>
043 * 
044 * @version StudentSct 1.3 (Student Sectioning)<br>
045 *          Copyright (C) 2007 - 2014 Tomas Muller<br>
046 *          <a href="mailto:muller@unitime.org">muller@unitime.org</a><br>
047 *          <a href="http://muller.unitime.org">http://muller.unitime.org</a><br>
048 * <br>
049 *          This library is free software; you can redistribute it and/or modify
050 *          it under the terms of the GNU Lesser General Public License as
051 *          published by the Free Software Foundation; either version 3 of the
052 *          License, or (at your option) any later version. <br>
053 * <br>
054 *          This library is distributed in the hope that it will be useful, but
055 *          WITHOUT ANY WARRANTY; without even the implied warranty of
056 *          MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
057 *          Lesser General Public License for more details. <br>
058 * <br>
059 *          You should have received a copy of the GNU Lesser General Public
060 *          License along with this library; if not see
061 *          <a href='http://www.gnu.org/licenses/'>http://www.gnu.org/licenses/</a>.
062 */
063public class StandardSelection implements NeighbourSelection<Request, Enrollment> {
064    private long iIteration = 0;
065    private ValueSelection<Request, Enrollment> iValueSelection = null;
066    private VariableSelection<Request, Enrollment> iVariableSelection = null;
067    protected long iNrIterations = -1;
068
069    /**
070     * Constructor (variable and value selection are expected to be already
071     * initialized).
072     * 
073     * @param properties
074     *            configuration
075     * @param variableSelection
076     *            variable selection
077     * @param valueSelection
078     *            value selection
079     */
080    public StandardSelection(DataProperties properties, VariableSelection<Request, Enrollment> variableSelection,
081            ValueSelection<Request, Enrollment> valueSelection) {
082        iVariableSelection = variableSelection;
083        iValueSelection = valueSelection;
084    }
085
086    /** Initialization */
087    @Override
088    public void init(Solver<Request, Enrollment> solver) {
089        iIteration = 0;
090        iNrIterations = solver.getProperties().getPropertyLong("Neighbour.StandardIterations", -1);
091        if (iNrIterations > 0)
092            Progress.getInstance(solver.currentSolution().getModel()).setPhase("Ifs...", iNrIterations);
093    }
094    
095    /**
096     * Check if the given enrollment can be unassigned
097     * @param enrollment given enrollment
098     * @return if running MPP, do not unassign initial enrollments
099     */
100    public boolean canUnassign(Enrollment enrollment, Assignment<Request, Enrollment> assignment) {
101        if (enrollment.getRequest().isMPP() && enrollment.equals(enrollment.getRequest().getInitialAssignment())) return false;
102        if (enrollment.getRequest().getStudent().hasMinCredit()) {
103            float credit = enrollment.getRequest().getStudent().getAssignedCredit(assignment) - enrollment.getCredit();
104            if (credit < enrollment.getRequest().getStudent().getMinCredit()) return false;
105        }
106        if (!enrollment.getRequest().isAlternative() && enrollment.getRequest().isCritical()) return false;
107        return true;
108    }
109
110    /**
111     * Employ the provided {@link VariableSelection} and {@link ValueSelection}
112     * and return the selected value as {@link SimpleNeighbour}. The selection
113     * is stopped (null is returned) after the number of iterations equal to the
114     * number of variables in the problem or when a complete solution is found.
115     */
116    @Override
117    public Neighbour<Request, Enrollment> selectNeighbour(Solution<Request, Enrollment> solution) {
118        if (iNrIterations < 0) {
119            iNrIterations = solution.getModel().nrUnassignedVariables(solution.getAssignment());
120            Progress.getInstance(solution.getModel()).setPhase("Ifs...", iNrIterations);
121        }
122        if (solution.getModel().unassignedVariables(solution.getAssignment()).isEmpty() || ++iIteration >= iNrIterations)
123            return null;
124        Progress.getInstance(solution.getModel()).incProgress();
125        attempts: for (int i = 0; i < 10; i++) {
126            Request request = iVariableSelection.selectVariable(solution);
127            if (request == null) continue;
128            Enrollment enrollment = iValueSelection.selectValue(solution, request);
129            if (enrollment == null) continue;
130            Set<Enrollment> conflicts = enrollment.variable().getModel().conflictValues(solution.getAssignment(), enrollment);
131            if (conflicts.contains(enrollment)) continue;
132            for (Enrollment conflict: conflicts)
133                if (!canUnassign(conflict, solution.getAssignment())) continue attempts;
134            return new SimpleNeighbour<Request, Enrollment>(request, enrollment, conflicts);
135        }
136        return null;
137    }
138
139}