    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}