Source code

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