001package org.cpsolver.ifs.heuristics; 002 003import java.lang.reflect.Constructor; 004import java.util.Map; 005import java.util.Set; 006 007import org.cpsolver.ifs.extension.ConflictStatistics; 008import org.cpsolver.ifs.extension.Extension; 009import org.cpsolver.ifs.model.Constraint; 010import org.cpsolver.ifs.model.Neighbour; 011import org.cpsolver.ifs.model.SimpleNeighbour; 012import org.cpsolver.ifs.model.Value; 013import org.cpsolver.ifs.model.Variable; 014import org.cpsolver.ifs.model.WeakeningConstraint; 015import org.cpsolver.ifs.solution.Solution; 016import org.cpsolver.ifs.solver.Solver; 017import org.cpsolver.ifs.solver.SolverListener; 018import org.cpsolver.ifs.util.DataProperties; 019 020 021/** 022 * Standard neighbour selection criterion. <br> 023 * <br> 024 * This criterion is using the provided variable and value selection criteria. 025 * In each step, a variable is selected first using the 026 * {@link VariableSelection}. Then, a value is selected to the selected 027 * variable, using the {@link ValueSelection}. A {@link SimpleNeighbour} 028 * containing the selected value is returned. <br> 029 * <br> 030 * Note: the use of neighbour select criteria extends the former implementation 031 * of the IFS algorithm which was only able to use variable and value selection 032 * criteria and therefore only one value was assigned in each iteration. <br> 033 * <br> 034 * Parameters: <br> 035 * <table border='1' summary='Related Solver Parameters'> 036 * <tr> 037 * <th>Parameter</th> 038 * <th>Type</th> 039 * <th>Comment</th> 040 * </tr> 041 * <tr> 042 * <td>Value.Class</td> 043 * <td>{@link String}</td> 044 * <td>Fully qualified class name of the value selection criterion (see 045 * {@link ValueSelection}, e.g. {@link GeneralValueSelection})</td> 046 * </tr> 047 * <tr> 048 * <td>Variable.Class</td> 049 * <td>{@link String}</td> 050 * <td>Fully qualified class name of the variable selection criterion (see 051 * {@link VariableSelection}, e.g. {@link GeneralVariableSelection})</td> 052 * </tr> 053 * </table> 054 * 055 * @see Solver 056 * 057 * @version IFS 1.3 (Iterative Forward Search)<br> 058 * Copyright (C) 2006 - 2014 Tomáš Müller<br> 059 * <a href="mailto:muller@unitime.org">muller@unitime.org</a><br> 060 * <a href="http://muller.unitime.org">http://muller.unitime.org</a><br> 061 * <br> 062 * This library is free software; you can redistribute it and/or modify 063 * it under the terms of the GNU Lesser General Public License as 064 * published by the Free Software Foundation; either version 3 of the 065 * License, or (at your option) any later version. <br> 066 * <br> 067 * This library is distributed in the hope that it will be useful, but 068 * WITHOUT ANY WARRANTY; without even the implied warranty of 069 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 070 * Lesser General Public License for more details. <br> 071 * <br> 072 * You should have received a copy of the GNU Lesser General Public 073 * License along with this library; if not see <a href='http://www.gnu.org/licenses'>http://www.gnu.org/licenses</a>. 074 * 075 * @param <V> Variable 076 * @param <T> Value 077 **/ 078public class StandardNeighbourSelection<V extends Variable<V, T>, T extends Value<V, T>> implements NeighbourSelection<V, T> { 079 protected static org.apache.log4j.Logger sLogger = org.apache.log4j.Logger.getLogger(StandardNeighbourSelection.class); 080 081 private ValueSelection<V, T> iValueSelection = null; 082 private VariableSelection<V, T> iVariableSelection = null; 083 private Solver<V, T> iSolver = null; 084 private ConflictStatistics<V, T> iStat = null; 085 086 /** Sets value selection criterion 087 * @param valueSelection value selection criterion 088 **/ 089 public void setValueSelection(ValueSelection<V, T> valueSelection) { 090 iValueSelection = valueSelection; 091 } 092 093 /** Sets variable selection criterion 094 * @param variableSelection variable selection criterion 095 **/ 096 public void setVariableSelection(VariableSelection<V, T> variableSelection) { 097 iVariableSelection = variableSelection; 098 } 099 100 /** Returns value selection criterion 101 * @return value selection criterion 102 **/ 103 public ValueSelection<V, T> getValueSelection() { 104 return iValueSelection; 105 } 106 107 /** Returns variable selection criterion 108 * @return variable selection criterion 109 **/ 110 public VariableSelection<V, T> getVariableSelection() { 111 return iVariableSelection; 112 } 113 114 /** 115 * Constructor 116 * 117 * @param properties 118 * configuration 119 * @throws Exception thrown when initialization fails 120 */ 121 @SuppressWarnings("unchecked") 122 public StandardNeighbourSelection(DataProperties properties) throws Exception { 123 String valueSelectionClassName = properties.getProperty("Value.Class", "org.cpsolver.ifs.heuristics.GeneralValueSelection"); 124 sLogger.info("Using " + valueSelectionClassName); 125 Class<?> valueSelectionClass = Class.forName(valueSelectionClassName); 126 Constructor<?> valueSelectionConstructor = valueSelectionClass.getConstructor(new Class[] { DataProperties.class }); 127 setValueSelection((ValueSelection<V, T>) valueSelectionConstructor.newInstance(new Object[] { properties })); 128 129 String variableSelectionClassName = properties.getProperty("Variable.Class", "org.cpsolver.ifs.heuristics.GeneralVariableSelection"); 130 sLogger.info("Using " + variableSelectionClassName); 131 Class<?> variableSelectionClass = Class.forName(variableSelectionClassName); 132 Constructor<?> variableSelectionConstructor = variableSelectionClass.getConstructor(new Class[] { DataProperties.class }); 133 setVariableSelection((VariableSelection<V, T>) variableSelectionConstructor.newInstance(new Object[] { properties })); 134 } 135 136 /** 137 * Initialization -- methods 138 * {@link org.cpsolver.ifs.heuristics.VariableSelection#init(Solver)} and 139 * {@link org.cpsolver.ifs.heuristics.ValueSelection#init(Solver)} are 140 * called. 141 */ 142 @Override 143 public void init(Solver<V, T> solver) { 144 getValueSelection().init(solver); 145 getVariableSelection().init(solver); 146 iSolver = solver; 147 for (Extension<V, T> ext: solver.getExtensions()) 148 if (ext instanceof ConflictStatistics) 149 iStat = (ConflictStatistics<V, T>)ext; 150 } 151 152 /** Use the provided variable selection criterion to select a variable 153 * @param solution current solution 154 * @return selected variable 155 **/ 156 public V selectVariable(Solution<V, T> solution) { 157 // Variable selection 158 V variable = getVariableSelection().selectVariable(solution); 159 for (SolverListener<V, T> listener : iSolver.getSolverListeners()) 160 if (!listener.variableSelected(solution.getAssignment(), solution.getIteration(), variable)) 161 return null; 162 if (variable == null) 163 sLogger.debug("No variable selected."); 164 165 if (variable != null && variable.values(solution.getAssignment()).isEmpty()) { 166 sLogger.debug("Variable " + variable.getName() + " has no values."); 167 return null; 168 } 169 return variable; 170 } 171 172 /** 173 * Use the provided value selection criterion to select a value to the 174 * selected variable 175 * @param solution current solution 176 * @param variable selected variable 177 * @return selected value 178 */ 179 @SuppressWarnings("unchecked") 180 public T selectValue(Solution<V, T> solution, V variable) { 181 // Value selection 182 T value = getValueSelection().selectValue(solution, variable); 183 for (SolverListener<V, T> listener : iSolver.getSolverListeners()) 184 if (!listener.valueSelected(solution.getAssignment(), solution.getIteration(), variable, value)) 185 return null; 186 187 if (value == null) { 188 sLogger.debug("No value selected for variable " + variable + "."); 189 for (Constraint<V, T> constraint: variable.hardConstraints()) { 190 if (constraint.isHard() && constraint instanceof WeakeningConstraint) 191 ((WeakeningConstraint<V, T>)constraint).weaken(solution.getAssignment()); 192 } 193 for (Constraint<V, T> constraint: solution.getModel().globalConstraints()) { 194 if (constraint.isHard() && constraint instanceof WeakeningConstraint) 195 ((WeakeningConstraint<V, T>)constraint).weaken(solution.getAssignment()); 196 } 197 return null; 198 } else { 199 for (Constraint<V, T> constraint: variable.hardConstraints()) { 200 if (constraint instanceof WeakeningConstraint && constraint.inConflict(solution.getAssignment(), value)) 201 ((WeakeningConstraint<V, T>)constraint).weaken(solution.getAssignment()); 202 } 203 for (Constraint<V, T> constraint: solution.getModel().globalConstraints()) { 204 if (constraint instanceof WeakeningConstraint && constraint.inConflict(solution.getAssignment(), value)) 205 ((WeakeningConstraint<V, T>)constraint).weaken(solution.getAssignment()); 206 } 207 } 208 return value; 209 } 210 211 /** 212 * Select neighbour. A value is selected to the selected variable. 213 */ 214 @Override 215 public Neighbour<V, T> selectNeighbour(Solution<V, T> solution) { 216 V variable = selectVariable(solution); 217 if (variable == null) 218 return null; 219 T value = selectValue(solution, variable); 220 if (value == null) 221 return null; 222 if (iSolver.hasSingleSolution()) { 223 Set<T> conflicts = solution.getModel().conflictValues(solution.getAssignment(), value); 224 if (iStat != null) 225 for (Map.Entry<Constraint<V, T>, Set<T>> entry: solution.getModel().conflictConstraints(solution.getAssignment(), value).entrySet()) 226 iStat.constraintAfterAssigned(solution.getAssignment(), solution.getIteration(), entry.getKey(), value, entry.getValue()); 227 // for (T conflict: conflicts) 228 // iStat.variableUnassigned(solution.getIteration(), conflict, value); 229 return new SimpleNeighbour<V, T>(variable, value, conflicts); 230 } else { 231 return new SimpleNeighbour<V, T>(variable, value); 232 } 233 } 234}