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}