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