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