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