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.model.Enrollment; 018import org.cpsolver.studentsct.model.Request; 019 020 021/** 022 * Use the provided variable and value selection for some time. The provided 023 * variable and value selection is used for the number of iterations equal to 024 * the number of all variables in the problem. If a complete solution is found, 025 * the neighbour selection is stopped (it returns null). 026 * 027 * <br> 028 * <br> 029 * Parameters: <br> 030 * <table border='1' summary='Related Solver Parameters'> 031 * <tr> 032 * <th>Parameter</th> 033 * <th>Type</th> 034 * <th>Comment</th> 035 * </tr> 036 * <tr> 037 * <td>Neighbour.StandardIterations</td> 038 * <td>{@link Long}</td> 039 * <td>Number of iterations to perform. If -1, number of iterations is set to 040 * the number of unassigned variables.</td> 041 * </tr> 042 * </table> 043 * <br> 044 * <br> 045 * 046 * @version StudentSct 1.3 (Student Sectioning)<br> 047 * Copyright (C) 2007 - 2014 Tomáš Müller<br> 048 * <a href="mailto:muller@unitime.org">muller@unitime.org</a><br> 049 * <a href="http://muller.unitime.org">http://muller.unitime.org</a><br> 050 * <br> 051 * This library is free software; you can redistribute it and/or modify 052 * it under the terms of the GNU Lesser General Public License as 053 * published by the Free Software Foundation; either version 3 of the 054 * License, or (at your option) any later version. <br> 055 * <br> 056 * This library is distributed in the hope that it will be useful, but 057 * WITHOUT ANY WARRANTY; without even the implied warranty of 058 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 059 * Lesser General Public License for more details. <br> 060 * <br> 061 * You should have received a copy of the GNU Lesser General Public 062 * License along with this library; if not see 063 * <a href='http://www.gnu.org/licenses/'>http://www.gnu.org/licenses/</a>. 064 */ 065public class StandardSelection implements NeighbourSelection<Request, Enrollment> { 066 private long iIteration = 0; 067 protected ValueSelection<Request, Enrollment> iValueSelection = null; 068 protected VariableSelection<Request, Enrollment> iVariableSelection = null; 069 protected long iNrIterations = -1; 070 protected boolean iPreferPriorityStudents = true; 071 protected long iConflictTimeOut = -7200; 072 protected long iTimeOut = -3600; 073 protected boolean iCanConflict = true; 074 protected boolean iCanHigherPriorityConflict = true; 075 076 /** 077 * Constructor (variable and value selection are expected to be already 078 * initialized). 079 * 080 * @param properties 081 * configuration 082 * @param variableSelection 083 * variable selection 084 * @param valueSelection 085 * value selection 086 */ 087 public StandardSelection(DataProperties properties, VariableSelection<Request, Enrollment> variableSelection, 088 ValueSelection<Request, Enrollment> valueSelection) { 089 iVariableSelection = variableSelection; 090 iValueSelection = valueSelection; 091 iPreferPriorityStudents = properties.getPropertyBoolean("Sectioning.PriorityStudentsFirstSelection.AllIn", true); 092 iTimeOut = properties.getPropertyLong("Neighbour.StandardTimeOut", -3600); 093 if (iTimeOut < 0) 094 iTimeOut = Math.max(0, properties.getPropertyLong("Termination.TimeOut", -1l) + iTimeOut); 095 iConflictTimeOut = properties.getPropertyLong("Neighbour.StandardConflictTimeOut", -7200); 096 if (iConflictTimeOut < 0) 097 iConflictTimeOut = Math.max(0, properties.getPropertyLong("Termination.TimeOut", -1l) + iConflictTimeOut); 098 iCanConflict = properties.getPropertyBoolean("Neighbour.StandardCanConflict", true); 099 iCanHigherPriorityConflict = properties.getPropertyBoolean("Neighbour.StandardCanHigherPriorityConflict", true); 100 } 101 102 /** Initialization */ 103 @Override 104 public void init(Solver<Request, Enrollment> solver) { 105 StudentFilter filter = null; 106 if (iVariableSelection instanceof UnassignedRequestSelection) 107 filter = ((UnassignedRequestSelection)iVariableSelection).getFilter(); 108 init(solver, "Ifs" + (filter == null ? "" : " (" + filter.getName().toLowerCase() + " students)") + "..."); 109 } 110 111 protected void init(Solver<Request, Enrollment> solver, String name) { 112 iVariableSelection.init(solver); 113 iValueSelection.init(solver); 114 iIteration = 0; 115 iNrIterations = solver.getProperties().getPropertyLong("Neighbour.StandardIterations", -1); 116 if (iNrIterations < 0) 117 iNrIterations = solver.currentSolution().getModel().nrUnassignedVariables(solver.currentSolution().getAssignment()); 118 if (iTimeOut > 0 && solver.currentSolution().getTime() > iTimeOut) 119 iNrIterations = 0; 120 iCanConflict = solver.getProperties().getPropertyBoolean("Neighbour.StandardCanConflict", true); 121 if (iCanConflict && iConflictTimeOut > 0 && solver.currentSolution().getTime() > iConflictTimeOut) 122 iCanConflict = false; 123 if (iNrIterations > 0) 124 Progress.getInstance(solver.currentSolution().getModel()).setPhase((iCanConflict ? name : "No-conf " + name), iNrIterations); 125 } 126 127 /** 128 * Check if the given conflicting enrollment can be unassigned 129 * @param conflict given enrollment 130 * @return if running MPP, do not unassign initial enrollments 131 */ 132 public boolean canUnassign(Enrollment enrollment, Enrollment conflict, Assignment<Request, Enrollment> assignment) { 133 if (!iCanConflict) return false; 134 if (!iCanHigherPriorityConflict && conflict.getRequest().getPriority() < enrollment.getRequest().getPriority()) return false; 135 if (conflict.getRequest().isMPP() && conflict.equals(conflict.getRequest().getInitialAssignment())) return false; 136 if (conflict.getRequest().getStudent().hasMinCredit()) { 137 float credit = conflict.getRequest().getStudent().getAssignedCredit(assignment) - conflict.getCredit(); 138 if (credit < conflict.getRequest().getStudent().getMinCredit()) return false; 139 } 140 if (!conflict.getRequest().isAlternative() && conflict.getRequest().getRequestPriority().isHigher(enrollment.getRequest())) return false; 141 if (iPreferPriorityStudents || conflict.getRequest().getRequestPriority().isSame(enrollment.getRequest())) { 142 if (conflict.getStudent().getPriority().isHigher(enrollment.getStudent())) return false; 143 } 144 return true; 145 } 146 147 /** 148 * Employ the provided {@link VariableSelection} and {@link ValueSelection} 149 * and return the selected value as {@link SimpleNeighbour}. The selection 150 * is stopped (null is returned) after the number of iterations equal to the 151 * number of variables in the problem or when a complete solution is found. 152 */ 153 @Override 154 public Neighbour<Request, Enrollment> selectNeighbour(Solution<Request, Enrollment> solution) { 155 if (solution.getModel().unassignedVariables(solution.getAssignment()).isEmpty() || ++iIteration >= iNrIterations) 156 return null; 157 Progress.getInstance(solution.getModel()).incProgress(); 158 attempts: for (int i = 0; i < 10; i++) { 159 try { 160 Request request = iVariableSelection.selectVariable(solution); 161 if (request == null) continue; 162 Enrollment enrollment = iValueSelection.selectValue(solution, request); 163 if (enrollment == null) continue; 164 Set<Enrollment> conflicts = enrollment.variable().getModel().conflictValues(solution.getAssignment(), enrollment); 165 if (conflicts.contains(enrollment)) continue; 166 for (Enrollment conflict: conflicts) 167 if (!canUnassign(enrollment, conflict, solution.getAssignment())) continue attempts; 168 return new SimpleNeighbour<Request, Enrollment>(request, enrollment, conflicts); 169 } catch (ConcurrentModificationException e) {} 170 } 171 return null; 172 } 173 174}