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}