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        init(solver, "Ifs...");
090    }
091    
092    protected void init(Solver<Request, Enrollment> solver, String name) {
093        iVariableSelection.init(solver);
094        iValueSelection.init(solver);
095        iIteration = 0;
096        iNrIterations = solver.getProperties().getPropertyLong("Neighbour.StandardIterations", -1);
097        if (iNrIterations < 0)
098            iNrIterations = solver.currentSolution().getModel().nrUnassignedVariables(solver.currentSolution().getAssignment());
099        Progress.getInstance(solver.currentSolution().getModel()).setPhase(name, iNrIterations);
100    }
101    
102    /**
103     * Check if the given enrollment can be unassigned
104     * @param enrollment given enrollment
105     * @return if running MPP, do not unassign initial enrollments
106     */
107    public boolean canUnassign(Enrollment enrollment, Assignment<Request, Enrollment> assignment) {
108        if (enrollment.getRequest().isMPP() && enrollment.equals(enrollment.getRequest().getInitialAssignment())) return false;
109        if (enrollment.getRequest().getStudent().hasMinCredit()) {
110            float credit = enrollment.getRequest().getStudent().getAssignedCredit(assignment) - enrollment.getCredit();
111            if (credit < enrollment.getRequest().getStudent().getMinCredit()) return false;
112        }
113        if (!enrollment.getRequest().isAlternative() && enrollment.getRequest().isCritical()) return false;
114        return true;
115    }
116
117    /**
118     * Employ the provided {@link VariableSelection} and {@link ValueSelection}
119     * and return the selected value as {@link SimpleNeighbour}. The selection
120     * is stopped (null is returned) after the number of iterations equal to the
121     * number of variables in the problem or when a complete solution is found.
122     */
123    @Override
124    public Neighbour<Request, Enrollment> selectNeighbour(Solution<Request, Enrollment> solution) {
125        if (solution.getModel().unassignedVariables(solution.getAssignment()).isEmpty() || ++iIteration >= iNrIterations)
126            return null;
127        Progress.getInstance(solution.getModel()).incProgress();
128        attempts: for (int i = 0; i < 10; i++) {
129            Request request = iVariableSelection.selectVariable(solution);
130            if (request == null) continue;
131            Enrollment enrollment = iValueSelection.selectValue(solution, request);
132            if (enrollment == null) continue;
133            Set<Enrollment> conflicts = enrollment.variable().getModel().conflictValues(solution.getAssignment(), enrollment);
134            if (conflicts.contains(enrollment)) continue;
135            for (Enrollment conflict: conflicts)
136                if (!canUnassign(conflict, solution.getAssignment())) continue attempts;
137            return new SimpleNeighbour<Request, Enrollment>(request, enrollment, conflicts);
138        }
139        return null;
140    }
141
142}