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    }