    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}