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 }