001package net.sf.cpsolver.ifs.perturbations;
002
003import java.util.Collection;
004import java.util.Locale;
005import java.util.Map;
006import java.util.Set;
007
008import net.sf.cpsolver.ifs.extension.Extension;
009import net.sf.cpsolver.ifs.extension.ViolatedInitials;
010import net.sf.cpsolver.ifs.model.Model;
011import net.sf.cpsolver.ifs.model.Value;
012import net.sf.cpsolver.ifs.model.Variable;
013import net.sf.cpsolver.ifs.solution.Solution;
014import net.sf.cpsolver.ifs.solver.Solver;
015import net.sf.cpsolver.ifs.util.DataProperties;
016
017/**
018 * Default computation of perturbation penalty (minimal perturbation problem). <br>
019 * <br>
020 * A distance function can be defined with the help of perturbations. A
021 * perturbation is a variable that has a different value in the solutions of the
022 * initial and the new problem. Some perturbations must be present in each new
023 * solution. So called input perturbation means that a variable must have
024 * different values in the initial and changed problem because of some input
025 * changes (e.g., a course must be scheduled at a different time in the changed
026 * problem). The distance function can be defined as the number of additional
027 * perturbations. They are given by subtraction of the final number of
028 * perturbations and the number of input perturbations (variables without
029 * initial assignments). <br>
030 * <br>
031 * This implementation is easily extendable. It disassemble all the available
032 * cases into a comparison of the initial and the assigned value different each
033 * other. So, the only method which is needed to be changed is
034 * {@link DefaultPerturbationsCounter#getPenalty(Value, Value)}. Its current
035 * implementation is:
036 * <ul>
037 * <code>
038 * protected double getPenalty(Value assignedValue, Value initialValue) {<br>
039 * &nbsp;&nbsp;&nbsp;&nbsp;return 1.0;<br>
040 * }<br>
041 * </code>
042 * </ul>
043 * It is called only when assignedValue is different to initialValue.
044 * 
045 * @see Solver
046 * @see Solution
047 * @see Variable
048 * 
049 * @version IFS 1.2 (Iterative Forward Search)<br>
050 *          Copyright (C) 2006 - 2010 Tomáš Müller<br>
051 *          <a href="mailto:muller@unitime.org">muller@unitime.org</a><br>
052 *          <a href="http://muller.unitime.org">http://muller.unitime.org</a><br>
053 * <br>
054 *          This library is free software; you can redistribute it and/or modify
055 *          it under the terms of the GNU Lesser General Public License as
056 *          published by the Free Software Foundation; either version 3 of the
057 *          License, or (at your option) any later version. <br>
058 * <br>
059 *          This library is distributed in the hope that it will be useful, but
060 *          WITHOUT ANY WARRANTY; without even the implied warranty of
061 *          MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
062 *          Lesser General Public License for more details. <br>
063 * <br>
064 *          You should have received a copy of the GNU Lesser General Public
065 *          License along with this library; if not see
066 *          <a href='http://www.gnu.org/licenses/'>http://www.gnu.org/licenses/</a>.
067 */
068
069public class DefaultPerturbationsCounter<V extends Variable<V, T>, T extends Value<V, T>> implements
070        PerturbationsCounter<V, T> {
071    private ViolatedInitials<V, T> iViolatedInitials = null;
072    protected static java.text.DecimalFormat sDoubleFormat = new java.text.DecimalFormat("0.00",
073            new java.text.DecimalFormatSymbols(Locale.US));
074
075    /**
076     * Constructor
077     * 
078     * @param properties
079     *            input configuration
080     */
081    public DefaultPerturbationsCounter(DataProperties properties) {
082    }
083
084    /** Initialization */
085    @Override
086    public void init(Solver<V, T> solver) {
087        for (Extension<V, T> extension : solver.getExtensions()) {
088            if (ViolatedInitials.class.isInstance(extension))
089                iViolatedInitials = (ViolatedInitials<V, T>) extension;
090        }
091    }
092
093    @Override
094    public double getPerturbationPenalty(Model<V, T> model) {
095        double penalty = 0.0;
096        for (V variable : model.perturbVariables()) {
097            if (variable.getAssignment() != null && variable.getInitialAssignment() != null
098                    && !variable.getAssignment().equals(variable.getInitialAssignment()))
099                penalty += getPenaltyD(variable.getAssignment(), variable.getInitialAssignment());
100        }
101        return penalty;
102    }
103
104    @Override
105    public double getPerturbationPenalty(Model<V, T> model, Collection<V> variables) {
106        double penalty = 0.0;
107        for (V variable : variables) {
108            if (variable.getAssignment() != null && variable.getInitialAssignment() != null
109                    && !variable.getAssignment().equals(variable.getInitialAssignment()))
110                penalty += getPenaltyD(variable.getAssignment(), variable.getInitialAssignment());
111        }
112        return penalty;
113    }
114
115    protected ViolatedInitials<V, T> getViolatedInitials() {
116        return iViolatedInitials;
117    }
118
119    /**
120     * Computes perturbation penalty between assigned and initial value of the
121     * same lecture. It is called only when assignedValue is different to
122     * initialValue.
123     * 
124     * @param assignedValue
125     *            value assigned to a varuable (null when variable is
126     *            unassigned)
127     * @param initialValue
128     *            initial value of the same varaible (always not null)
129     */
130    protected double getPenalty(T assignedValue, T initialValue) {
131        return 1.0;
132    }
133
134    /**
135     * Case A: initial value of a different unassigned variable cannot be
136     * assigned (computed by {@link ViolatedInitials})
137     * 
138     * @param selectedValue
139     *            value which is going to be assigned to its variable
140     * @param initialValue
141     *            value of a different variable, which is currently assigned but
142     *            which need to be unassifned Different variable, which is
143     *            unassigned and whose initial value is in conflict with the
144     *            selected value.
145     */
146    protected double getPenaltyA(T selectedValue, T initialValue) {
147        return getPenalty(null, initialValue);
148    }
149
150    /**
151     * Case B: initial value is unassigned from a conflicting variable.
152     * 
153     * @param selectedValue
154     *            value which is going to be unassigned to its variable
155     * @param assignedValue
156     *            value currently assigned to a conflicting variable (different
157     *            from the one of selectedVariable)
158     * @param initialValue
159     *            initial value of the conflicting variable of assignedValue
160     */
161    protected double getPenaltyB(T selectedValue, T assignedValue, T initialValue) {
162        return getPenalty(assignedValue, initialValue);
163    }
164
165    /**
166     * Case C: non-initial value is unassigned from a conflicting variable.
167     * 
168     * @param selectedValue
169     *            value which is going to be unassigned to its variable
170     * @param assignedValue
171     *            value currently assigned to a conflicting variable (different
172     *            from the one of selectedVariable)
173     * @param initialValue
174     *            initial value of the conflicting variable of assignedValue
175     */
176    protected double getPenaltyC(T selectedValue, T assignedValue, T initialValue) {
177        return -getPenalty(assignedValue, initialValue);
178    }
179
180    /**
181     * Case D: different than initial value is assigned to the varaible
182     * 
183     * @param selectedValue
184     *            value which is going to be unassigned to its variable
185     * @param initialValue
186     *            initial value of the same variable
187     */
188    protected double getPenaltyD(T selectedValue, T initialValue) {
189        return getPenalty(selectedValue, initialValue);
190    }
191
192    @Override
193    public double getPerturbationPenalty(Model<V, T> model, T selectedValue, Collection<T> conflicts) {
194        double penalty = 0;
195        Set<T> violations = (getViolatedInitials() == null ? null : getViolatedInitials().getViolatedInitials(
196                selectedValue));
197        if (violations != null)
198            for (T aValue : violations) {
199                if (aValue.variable().getAssignment() == null)
200                    penalty += getPenaltyA(selectedValue, aValue);
201            }
202        if (conflicts != null) {
203            for (T conflictValue : conflicts) {
204                T initialValue = conflictValue.variable().getInitialAssignment();
205                if (initialValue != null) {
206                    if (initialValue.equals(conflictValue))
207                        penalty += getPenaltyB(selectedValue, conflictValue, initialValue);
208                    else {
209                        if (violations == null || !violations.contains(initialValue))
210                            penalty += getPenaltyC(selectedValue, conflictValue, initialValue);
211                    }
212                }
213            }
214        }
215        if (selectedValue.variable().getInitialAssignment() != null
216                && !selectedValue.equals(selectedValue.variable().getInitialAssignment()))
217            penalty += getPenaltyD(selectedValue, selectedValue.variable().getInitialAssignment());
218        return penalty;
219    }
220
221    @Override
222    public void getInfo(Map<String, String> info, Model<V, T> model) {
223        if (model.variablesWithInitialValue().size() > 0)
224            info.put("Perturbations: Total penalty", sDoubleFormat.format(getPerturbationPenalty(model)));
225    }
226
227    @Override
228    public void getInfo(Map<String, String> info, Model<V, T> model, Collection<V> variables) {
229        if (model.variablesWithInitialValue().size() > 0)
230            info.put("Perturbations: Total penalty", sDoubleFormat.format(getPerturbationPenalty(model, variables)));
231    }
232}