    001package net.sf.cpsolver.ifs.criteria;
    002
    003import java.util.ArrayList;
    004import java.util.Collection;
    005import java.util.Locale;
    006import java.util.Map;
    007import java.util.Set;
    008
    009import net.sf.cpsolver.ifs.model.Constraint;
    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.solver.Solver;
    014import net.sf.cpsolver.ifs.util.DataProperties;
    015
    016/**
    017 * Abstract Criterion. <br>
    018 * <br>
    019 * An optimization objective can be split into several (optimization) criteria
    020 * and modeled as a weighted sum of these. This makes the implementation of a particular problem
    021 * more versatile as it allows for an easier modification of the optimization objective.
    022 * <br>
    023 * This class implements most of the {@link Criterion} except of the {@link Criterion#getValue(Value, Set)}.
    024 *
    025 * @version IFS 1.2 (Iterative Forward Search)<br>
    026 *          Copyright (C) 2006 - 2011 Tomáš Müller<br>
    027 *          <a href="mailto:muller@unitime.org">muller@unitime.org</a><br>
    028 *          <a href="http://muller.unitime.org">http://muller.unitime.org</a><br>
    029 * <br>
    030 *          This library is free software; you can redistribute it and/or modify
    031 *          it under the terms of the GNU Lesser General Public License as
    032 *          published by the Free Software Foundation; either version 3 of the
    033 *          License, or (at your option) any later version. <br>
    034 * <br>
    035 *          This library is distributed in the hope that it will be useful, but
    036 *          WITHOUT ANY WARRANTY; without even the implied warranty of
    037 *          MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
    038 *          Lesser General Public License for more details. <br>
    039 * <br>
    040 *          You should have received a copy of the GNU Lesser General Public
    041 *          License along with this library; if not see
    042 *          <a href='http://www.gnu.org/licenses/'>http://www.gnu.org/licenses/</a>.
    043 */
    044public abstract class AbstractCriterion<V extends Variable<V, T>, T extends Value<V, T>> implements Criterion<V, T> {
    045    private Model<V, T> iModel;
    046    protected double iBest = 0.0, iValue = 0.0, iWeight = 0.0;
    047    private double[] iBounds = null;
    048    protected static java.text.DecimalFormat sDoubleFormat = new java.text.DecimalFormat("0.##",
    049            new java.text.DecimalFormatSymbols(Locale.US));
    050    protected static java.text.DecimalFormat sPercentFormat = new java.text.DecimalFormat("0.##",
    051            new java.text.DecimalFormatSymbols(Locale.US));
    052    protected boolean iDebug = false;
    053
    054    /**
    055     * Defines how the overall value of the criterion should be automatically updated (using {@link Criterion#getValue(Value, Set)}).
    056     */
    057    protected static enum ValueUpdateType {
    058        /** Update is done before an unassignment (decrement) and before an assignment (increment). */
    059        BeforeUnassignedBeforeAssigned,
    060        /** Update is done after an unassignment (decrement) and before an assignment (increment). */
    061        AfterUnassignedBeforeAssigned,
    062        /** Update is done before an unassignment (decrement) and after an assignment (increment). */
    063        BeforeUnassignedAfterAssigned,
    064        /** Update is done after an unassignment (decrement) and after an assignment (increment). This is the default. */
    065        AfterUnassignedAfterAssigned,
    066        /** Criterion is to be updated manually (e.g., using {@link Criterion#inc(double)}). */
    067        NoUpdate
    068    }
    069    protected ValueUpdateType iValueUpdateType = ValueUpdateType.BeforeUnassignedAfterAssigned;
    070
    071    /** Defines weight name (to be used to get the criterion weight from the configuration). */
    072    public String getWeightName() {
    073        return "Weight." + getClass().getName().substring(1 + getClass().getName().lastIndexOf('.'));
    074    }
    075
    076    /** Defines default weight (when {@link AbstractCriterion#getWeightName()} parameter is not present in the criterion). */
    077    public double getWeightDefault(DataProperties config) {
    078        return 0.0;
    079    }
    080
    081    @Override
    082    public boolean init(Solver<V, T> solver) {
    083        iModel = solver.currentSolution().getModel();
    084        iWeight = solver.getProperties().getPropertyDouble(getWeightName(), getWeightDefault(solver.getProperties()));
    085        iDebug = solver.getProperties().getPropertyBoolean(
    086                "Debug." + getClass().getName().substring(1 + getClass().getName().lastIndexOf('.')),
    087                solver.getProperties().getPropertyBoolean("Debug.Criterion", false));
    088        return true;
    089    }
    090
    091    /** Returns current model */
    092    public Model<V, T> getModel() { return iModel; }
    093
    094    @Override
    095    public double getValue() {
    096        return iValue;
    097    }
    098
    099    @Override
    100    public double getBest() {
    101        return iBest;
    102    }
    103
    104    @Override
    105    public double getValue(Collection<V> variables) {
    106        double ret = 0;
    107        for (V v: variables) {
    108            T t = v.getAssignment();
    109            if (t != null) ret += getValue(t, null);
    110        }
    111        return ret;
    112    }
    113
    114
    115    @Override
    116    public double getWeight() {
    117        return iWeight;
    118    }
    119
    120    @Override
    121    public double getWeightedBest() {
    122        return getWeight() == 0.0 ? 0.0 : getWeight() * getBest();
    123    }
    124
    125    @Override
    126    public double getWeightedValue() {
    127        return (getWeight() == 0.0 ? 0.0 : getWeight() * getValue());
    128    }
    129
    130    @Override
    131    public double getWeightedValue(T value, Set<T> conflicts) {
    132        return (getWeight() == 0.0 ? 0.0 : getWeight() * getValue(value, conflicts));
    133    }
    134
    135    @Override
    136    public double getWeightedValue(Collection<V> variables) {
    137        return (getWeight() == 0.0 ? 0.0 : getWeight() * getValue(variables));
    138    }
    139
    140    /** Compute bounds (bounds are being cached by default). */
    141    protected double[] computeBounds() {
    142        return getBounds(new ArrayList<V>(getModel().variables()));
    143    }
    144
    145    @Override
    146    public double[] getBounds() {
    147        if (iBounds == null) iBounds = computeBounds();
    148        return (iBounds == null ? new double[] {0.0, 0.0} : iBounds);
    149    }
    150
    151    @Override
    152    public double[] getBounds(Collection<V> variables) {
    153        double[] bounds = new double[] { 0.0, 0.0 };
    154        for (V v: variables) {
    155            Double min = null, max = null;
    156            for (T t: v.values()) {
    157                double value = getValue(t, null);
    158                if (min == null) { min = value; max = value; continue; }
    159                min = Math.min(min, value);
    160                max = Math.max(max, value);
    161            }
    162            if (min != null) {
    163                bounds[0] += min;
    164                bounds[1] += max;
    165            }
    166        }
    167        return bounds;
    168    }
    169
    170    @Override
    171    public void beforeAssigned(long iteration, T value) {
    172        switch (iValueUpdateType) {
    173            case AfterUnassignedBeforeAssigned:
    174            case BeforeUnassignedBeforeAssigned:
    175                iValue += getValue(value, null);
    176        }
    177    }
    178
    179    @Override
    180    public void afterAssigned(long iteration, T value) {
    181        switch (iValueUpdateType) {
    182            case AfterUnassignedAfterAssigned:
    183            case BeforeUnassignedAfterAssigned:
    184                iValue += getValue(value, null);
    185        }
    186    }
    187
    188    @Override
    189    public void beforeUnassigned(long iteration, T value) {
    190        switch (iValueUpdateType) {
    191            case BeforeUnassignedAfterAssigned:
    192            case BeforeUnassignedBeforeAssigned:
    193                iValue -= getValue(value, null);
    194        }
    195    }
    196
    197    @Override
    198    public void afterUnassigned(long iteration, T value) {
    199        switch (iValueUpdateType) {
    200            case AfterUnassignedAfterAssigned:
    201            case AfterUnassignedBeforeAssigned:
    202                iValue -= getValue(value, null);
    203        }
    204    }
    205
    206    @Override
    207    public void bestSaved() {
    208        iBest = iValue;
    209    }
    210
    211    @Override
    212    public void bestRestored() {
    213        iValue = iBest;
    214    }
    215
    216    @Override
    217    public void inc(double value) {
    218        iValue += value;
    219    }
    220
    221    @Override
    222    public String getName() {
    223        return getClass().getName().substring(1 + getClass().getName().lastIndexOf('.')).replaceAll("(?<=[^A-Z])([A-Z])"," $1");
    224    }
    225
    226    /** Clear bounds cache */
    227    protected void clearCache() {
    228        iBounds = null;
    229    }
    230
    231    @Override
    232    public void variableAdded(V variable) {
    233        clearCache();
    234    }
    235    @Override
    236    public void variableRemoved(V variable) {
    237        clearCache();
    238    }
    239    @Override
    240    public void constraintAdded(Constraint<V, T> constraint) {
    241        clearCache();
    242    }
    243    @Override
    244    public void constraintRemoved(Constraint<V, T> constraint) {
    245        clearCache();
    246    }
    247
    248    protected String getPerc(double value, double min, double max) {
    249        if (max == min)
    250            return sPercentFormat.format(100.0);
    251        return sPercentFormat.format(100.0 - 100.0 * (value - min) / (max - min));
    252    }
    253
    254    protected String getPercRev(double value, double min, double max) {
    255        if (max == min)
    256            return sPercentFormat.format(0.0);
    257        return sPercentFormat.format(100.0 * (value - min) / (max - min));
    258    }
    259
    260    @Override
    261    public void getInfo(Map<String, String> info) {
    262        if (iDebug) {
    263            double val = getValue(), w = getWeightedValue(), prec = getValue(getModel().variables());
    264            double[] bounds = getBounds();
    265            if (bounds[0] <= val && val <= bounds[1] && bounds[0] < bounds[1])
    266                info.put("[C] " + getName(),
    267                        getPerc(val, bounds[0], bounds[1]) + "% (value: " + sDoubleFormat.format(val) +
    268                        (prec != val ? ", precise:" + sDoubleFormat.format(prec) : "") +
    269                        ", weighted:" + sDoubleFormat.format(w) +
    270                        ", bounds: " + sDoubleFormat.format(bounds[0]) + "&hellip;" + sDoubleFormat.format(bounds[1]) + ")");
    271            else if (bounds[1] <= val && val <= bounds[0] && bounds[1] < bounds[0])
    272                info.put("[C] " + getName(),
    273                        getPercRev(val, bounds[1], bounds[0]) + "% (value: " + sDoubleFormat.format(val) +
    274                        (prec != val ? ", precise:" + sDoubleFormat.format(prec) : "") +
    275                        ", weighted:" + sDoubleFormat.format(w) +
    276                        ", bounds: " + sDoubleFormat.format(bounds[1]) + "&hellip;" + sDoubleFormat.format(bounds[0]) + ")");
    277            else if (bounds[0] != val || val != bounds[1])
    278                info.put("[C] " + getName(),
    279                        sDoubleFormat.format(val) + " (" +
    280                        (prec != val ? "precise:" + sDoubleFormat.format(prec) + ", ": "") +
    281                        "weighted:" + sDoubleFormat.format(w) +
    282                        (bounds[0] != bounds[1] ? ", bounds: " + sDoubleFormat.format(bounds[0]) + "&hellip;" + sDoubleFormat.format(bounds[1]) : "") +
    283                        ")");
    284        }
    285    }
    286
    287    @Override
    288    public void getInfo(Map<String, String> info, Collection<V> variables) {
    289        if (iDebug) {
    290            double val = getValue(variables), w = getWeightedValue(variables);
    291            double[] bounds = getBounds(variables);
    292            if (bounds[0] <= val && val <= bounds[1])
    293                info.put("[C] " + getName(),
    294                        getPerc(val, bounds[0], bounds[1]) + "% (value: " + sDoubleFormat.format(val) +
    295                        ", weighted:" + sDoubleFormat.format(w) +
    296                        ", bounds: " + sDoubleFormat.format(bounds[0]) + "&hellip;" + sDoubleFormat.format(bounds[1]) + ")");
    297            else if (bounds[1] <= val && val <= bounds[0])
    298                info.put("[C] " + getName(),
    299                        getPercRev(val, bounds[1], bounds[0]) + "% (value: " + sDoubleFormat.format(val) +
    300                        ", weighted:" + sDoubleFormat.format(w) +
    301                        ", bounds: " + sDoubleFormat.format(bounds[1]) + "&hellip;" + sDoubleFormat.format(bounds[0]) + ")");
    302            else if (bounds[0] != val || val != bounds[1])
    303                info.put("[C] " + getName(),
    304                        sDoubleFormat.format(val) + " (weighted:" + sDoubleFormat.format(w) +
    305                        (bounds[0] != bounds[1] ? ", bounds: " + sDoubleFormat.format(bounds[0]) + "&hellip;" + sDoubleFormat.format(bounds[1]) : "") +
    306                        ")");
    307        }
    308    }
    309}