    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 * @version IFS 1.3 (Iterative Forward Search)<br>
    052 *          Copyright (C) 2006 - 2014 Tomáš Müller<br>
    053 *          <a href="mailto:muller@unitime.org">muller@unitime.org</a><br>
    054 *          <a href="http://muller.unitime.org">http://muller.unitime.org</a><br>
    055 * <br>
    056 *          This library is free software; you can redistribute it and/or modify
    057 *          it under the terms of the GNU Lesser General Public License as
    058 *          published by the Free Software Foundation; either version 3 of the
    059 *          License, or (at your option) any later version. <br>
    060 * <br>
    061 *          This library is distributed in the hope that it will be useful, but
    062 *          WITHOUT ANY WARRANTY; without even the implied warranty of
    063 *          MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
    064 *          Lesser General Public License for more details. <br>
    065 * <br>
    066 *          You should have received a copy of the GNU Lesser General Public
    067 *          License along with this library; if not see
    068 *          <a href='http://www.gnu.org/licenses/'>http://www.gnu.org/licenses/</a>.
    069 *
    070 * @param <V> Variable
    071 * @param <T> Value
    072 */
    073public class DefaultPerturbationsCounter<V extends Variable<V, T>, T extends Value<V, T>> implements PerturbationsCounter<V, T> {
    074    private ViolatedInitials<V, T> iViolatedInitials = null;
    075    protected static java.text.DecimalFormat sDoubleFormat = new java.text.DecimalFormat("0.00", new java.text.DecimalFormatSymbols(Locale.US));
    076
    077    /**
    078     * Constructor
    079     *
    080     * @param properties
    081     *            input configuration
    082     */
    083    public DefaultPerturbationsCounter(DataProperties properties) {
    084    }
    085
    086    /** Initialization */
    087    @Override
    088    public void init(Solver<V, T> solver) {
    089        for (Extension<V, T> extension : solver.getExtensions()) {
    090            if (ViolatedInitials.class.isInstance(extension))
    091                iViolatedInitials = (ViolatedInitials<V, T>) extension;
    092        }
    093    }
    094
    095    @Override
    096    public double getPerturbationPenalty(Assignment<V, T> assignment, Model<V, T> model) {
    097        double penalty = 0.0;
    098        for (V variable : model.variablesWithInitialValue()) {
    099            T value = assignment.getValue(variable);
    100            if (value != null && variable.getInitialAssignment() != null && !value.equals(variable.getInitialAssignment()))
    101                penalty += getPenaltyD(assignment, value, variable.getInitialAssignment());
    102        }
    103        return penalty;
    104    }
    105
    106    @Override
    107    public double getPerturbationPenalty(Assignment<V, T> assignment, Model<V, T> model, Collection<V> variables) {
    108        double penalty = 0.0;
    109        for (V variable : variables) {
    110            T value = assignment.getValue(variable);
    111            if (value != null && variable.getInitialAssignment() != null && !value.equals(variable.getInitialAssignment()))
    112                penalty += getPenaltyD(assignment, value, variable.getInitialAssignment());
    113        }
    114        return penalty;
    115    }
    116
    117    protected ViolatedInitials<V, T> getViolatedInitials() {
    118        return iViolatedInitials;
    119    }
    120
    121    /**
    122     * Computes perturbation penalty between assigned and initial value of the
    123     * same lecture. It is called only when assignedValue is different to
    124     * initialValue.
    125     *
    126     * @param assignment current assignment
    127     * @param assignedValue
    128     *            value assigned to a varuable (null when variable is
    129     *            unassigned)
    130     * @param initialValue
    131     *            initial value of the same varaible (always not null)
    132     * @return penalty
    133     */
    134    protected double getPenalty(Assignment<V, T> assignment, T assignedValue, T initialValue) {
    135        return 1.0;
    136    }
    137
    138    /**
    139     * Case A: initial value of a different unassigned variable cannot be
    140     * assigned (computed by {@link ViolatedInitials})
    141     *
    142     * @param assignment current assignment
    143     * @param selectedValue
    144     *            value which is going to be assigned to its variable
    145     * @param initialValue
    146     *            value of a different variable, which is currently assigned but
    147     *            which need to be unassifned Different variable, which is
    148     *            unassigned and whose initial value is in conflict with the
    149     *            selected value.
    150     * @return penalty
    151     */
    152    protected double getPenaltyA(Assignment<V, T> assignment, T selectedValue, T initialValue) {
    153        return getPenalty(assignment, null, initialValue);
    154    }
    155
    156    /**
    157     * Case B: initial value is unassigned from a conflicting variable.
    158     *
    159     * @param assignment current assignment
    160     * @param selectedValue
    161     *            value which is going to be unassigned to its variable
    162     * @param assignedValue
    163     *            value currently assigned to a conflicting variable (different
    164     *            from the one of selectedVariable)
    165     * @param initialValue
    166     *            initial value of the conflicting variable of assignedValue
    167     * @return penalty
    168     */
    169    protected double getPenaltyB(Assignment<V, T> assignment, T selectedValue, T assignedValue, T initialValue) {
    170        return getPenalty(assignment, assignedValue, initialValue);
    171    }
    172
    173    /**
    174     * Case C: non-initial value is unassigned from a conflicting variable.
    175     *
    176     * @param assignment current assignment
    177     * @param selectedValue
    178     *            value which is going to be unassigned to its variable
    179     * @param assignedValue
    180     *            value currently assigned to a conflicting variable (different
    181     *            from the one of selectedVariable)
    182     * @param initialValue
    183     *            initial value of the conflicting variable of assignedValue
    184     * @return penalty
    185     */
    186    protected double getPenaltyC(Assignment<V, T> assignment, T selectedValue, T assignedValue, T initialValue) {
    187        return -getPenalty(assignment, assignedValue, initialValue);
    188    }
    189
    190    /**
    191     * Case D: different than initial value is assigned to the variable
    192     *
    193     * @param assignment current assignment
    194     * @param selectedValue
    195     *            value which is going to be unassigned to its variable
    196     * @param initialValue
    197     *            initial value of the same variable
    198     * @return penalty
    199     */
    200    protected double getPenaltyD(Assignment<V, T> assignment, T selectedValue, T initialValue) {
    201        return getPenalty(assignment, selectedValue, initialValue);
    202    }
    203
    204    @Override
    205    public double getPerturbationPenalty(Assignment<V, T> assignment, Model<V, T> model, T selectedValue, Collection<T> conflicts) {
    206        double penalty = 0;
    207        Set<T> violations = (getViolatedInitials() == null ? null : getViolatedInitials().getViolatedInitials(selectedValue));
    208        if (violations != null)
    209            for (T aValue : violations) {
    210                if (assignment.getValue(aValue.variable()) == null)
    211                    penalty += getPenaltyA(assignment, selectedValue, aValue);
    212            }
    213        if (conflicts != null) {
    214            for (T conflictValue : conflicts) {
    215                T initialValue = conflictValue.variable().getInitialAssignment();
    216                if (initialValue != null) {
    217                    if (initialValue.equals(conflictValue))
    218                        penalty += getPenaltyB(assignment, selectedValue, conflictValue, initialValue);
    219                    else {
    220                        if (violations == null || !violations.contains(initialValue))
    221                            penalty += getPenaltyC(assignment, selectedValue, conflictValue, initialValue);
    222                    }
    223                }
    224            }
    225        }
    226        if (selectedValue.variable().getInitialAssignment() != null && !selectedValue.equals(selectedValue.variable().getInitialAssignment()))
    227            penalty += getPenaltyD(assignment, selectedValue, selectedValue.variable().getInitialAssignment());
    228        return penalty;
    229    }
    230
    231    @Override
    232    public void getInfo(Assignment<V, T> assignment, Model<V, T> model, Map<String, String> info) {
    233        if (model.variablesWithInitialValue().size() > 0)
    234            info.put("Perturbations: Total penalty", sDoubleFormat.format(getPerturbationPenalty(assignment, model)));
    235    }
    236
    237    @Override
    238    public void getInfo(Assignment<V, T> assignment, Model<V, T> model, Map<String, String> info, Collection<V> variables) {
    239        if (model.variablesWithInitialValue().size() > 0)
    240            info.put("Perturbations: Total penalty", sDoubleFormat.format(getPerturbationPenalty(assignment, model, variables)));
    241    }
    242}