001 package net.sf.cpsolver.ifs.heuristics;
002
003 import java.lang.reflect.Constructor;
004 import java.util.Enumeration;
005
006 import net.sf.cpsolver.ifs.model.Neighbour;
007 import net.sf.cpsolver.ifs.model.SimpleNeighbour;
008 import net.sf.cpsolver.ifs.model.Value;
009 import net.sf.cpsolver.ifs.model.Variable;
010 import net.sf.cpsolver.ifs.solution.Solution;
011 import net.sf.cpsolver.ifs.solver.Solver;
012 import net.sf.cpsolver.ifs.solver.SolverListener;
013 import net.sf.cpsolver.ifs.util.DataProperties;
014
015 /**
016 * Standard neighbour selection criterion.
017 * <br><br>
018 * This criterion is using the provided variable and value selection criteria.
019 * In each step, a variable is selected first using the {@link VariableSelection}.
020 * Then, a value is selected to the selected variable, using the {@link ValueSelection}.
021 * A {@link SimpleNeighbour} containing the selected value is returned.
022 * <br><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 criteria
025 * and therefore only one value was assigned in each iteration.
026 * <br><br>
027 * Parameters:
028 * <br>
029 * <table border='1'><tr><th>Parameter</th><th>Type</th><th>Comment</th></tr>
030 * <tr><td>Value.Class</td><td>{@link String}</td><td>Fully qualified class name of the value selection criterion (see {@link ValueSelection}, e.g. {@link GeneralValueSelection})</td></tr>
031 * <tr><td>Variable.Class</td><td>{@link String}</td><td>Fully qualified class name of the variable selection criterion (see {@link VariableSelection}, e.g. {@link GeneralVariableSelection})</td></tr>
032 * </table>
033 * @see Solver
034 *
035 * @version
036 * IFS 1.1 (Iterative Forward Search)<br>
037 * Copyright (C) 2006 Tomáš Müller<br>
038 * <a href="mailto:muller@unitime.org">muller@unitime.org</a><br>
039 * Lazenska 391, 76314 Zlin, Czech Republic<br>
040 * <br>
041 * This library is free software; you can redistribute it and/or
042 * modify it under the terms of the GNU Lesser General Public
043 * License as published by the Free Software Foundation; either
044 * version 2.1 of the License, or (at your option) any later version.
045 * <br><br>
046 * This library is distributed in the hope that it will be useful,
047 * but WITHOUT ANY WARRANTY; without even the implied warranty of
048 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
049 * Lesser General Public License for more details.
050 * <br><br>
051 * You should have received a copy of the GNU Lesser General Public
052 * License along with this library; if not, write to the Free Software
053 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
054 **/
055 public class StandardNeighbourSelection implements NeighbourSelection {
056 protected static org.apache.log4j.Logger sLogger = org.apache.log4j.Logger.getLogger(StandardNeighbourSelection.class);
057
058 private ValueSelection iValueSelection = null;
059 private VariableSelection iVariableSelection = null;
060 private Solver iSolver = null;
061
062 /** Sets value selection criterion */
063 public void setValueSelection(ValueSelection valueSelection) { iValueSelection = valueSelection; }
064 /** Sets variable selection criterion */
065 public void setVariableSelection(VariableSelection variableSelection) { iVariableSelection = variableSelection; }
066
067 /** Returns values selection criterion */
068 public ValueSelection getValueSelection() { return iValueSelection; }
069 /** Returns variable selection criterion */
070 public VariableSelection getVariableSelection() { return iVariableSelection; }
071
072 /**
073 * Constructor
074 * @param properties configuration
075 * @throws Exception
076 */
077 public StandardNeighbourSelection(DataProperties properties) throws Exception {
078 String valueSelectionClassName = properties.getProperty("Value.Class","net.sf.cpsolver.ifs.heuristics.GeneralValueSelection");
079 sLogger.info("Using "+valueSelectionClassName);
080 Class valueSelectionClass = Class.forName(valueSelectionClassName);
081 Constructor valueSelectionConstructor = valueSelectionClass.getConstructor(new Class[]{DataProperties.class});
082 setValueSelection((ValueSelection)valueSelectionConstructor.newInstance(new Object[] {properties}));
083
084 String variableSelectionClassName = properties.getProperty("Variable.Class","net.sf.cpsolver.ifs.heuristics.GeneralVariableSelection");
085 sLogger.info("Using "+variableSelectionClassName);
086 Class variableSelectionClass = Class.forName(variableSelectionClassName);
087 Constructor variableSelectionConstructor = variableSelectionClass.getConstructor(new Class[]{DataProperties.class});
088 setVariableSelection((VariableSelection)variableSelectionConstructor.newInstance(new Object[] {properties}));
089 }
090
091
092 /**
093 * Initialization -- methods {@link net.sf.cpsolver.ifs.heuristics.VariableSelection#init(Solver)} and {@link net.sf.cpsolver.ifs.heuristics.ValueSelection#init(Solver)} are called.
094 */
095 public void init(Solver solver) {
096 getValueSelection().init(solver);
097 getVariableSelection().init(solver);
098 iSolver = solver;
099 }
100
101 /** Use the provided variable selection criterion to select a variable */
102 public Variable selectVariable(Solution solution) {
103 // Variable selection
104 Variable variable = getVariableSelection().selectVariable(solution);
105 for (Enumeration i=iSolver.getSolverListeners().elements();i.hasMoreElements();)
106 if (!((SolverListener)i.nextElement()).variableSelected(solution.getIteration(), variable)) return null;
107 if (variable == null) sLogger.debug("No variable selected.");
108
109 if (variable != null && !variable.hasValues()) {
110 sLogger.debug("Variable "+variable.getName()+" has no values.");
111 return null;
112 }
113 return variable;
114 }
115
116 /** Use the provided value selection criterion to select a value to the selected variable */
117 public Value selectValue(Solution solution, Variable variable) {
118 // Value selection
119 Value value = getValueSelection().selectValue(solution, variable);
120 for (Enumeration i=iSolver.getSolverListeners().elements();i.hasMoreElements();)
121 if (!((SolverListener)i.nextElement()).valueSelected(solution.getIteration(), variable, value)) return null;
122
123 if (value == null) {
124 sLogger.debug("No value selected for variable "+variable+".");
125 }
126 return value;
127 }
128
129 /**
130 * Select neighbour. A value is selected to the selected variable.
131 */
132 public Neighbour selectNeighbour(Solution solution) {
133 Variable variable = selectVariable(solution);
134 if (variable==null) return null;
135 Value value = selectValue(solution, variable);
136 if (value==null) return null;
137 return new SimpleNeighbour(variable, value);
138 }
139 }