    001package org.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 org.cpsolver.coursett.criteria.TimetablingCriterion;
    010import org.cpsolver.ifs.assignment.Assignment;
    011import org.cpsolver.ifs.assignment.context.AssignmentConstraintContext;
    012import org.cpsolver.ifs.assignment.context.AssignmentContext;
    013import org.cpsolver.ifs.assignment.context.AssignmentContextHelper;
    014import org.cpsolver.ifs.assignment.context.AssignmentContextReference;
    015import org.cpsolver.ifs.assignment.context.CanHoldContext;
    016import org.cpsolver.ifs.assignment.context.ConstraintWithContext;
    017import org.cpsolver.ifs.assignment.context.HasAssignmentContext;
    018import org.cpsolver.ifs.model.Constraint;
    019import org.cpsolver.ifs.model.Model;
    020import org.cpsolver.ifs.model.Value;
    021import org.cpsolver.ifs.model.Variable;
    022import org.cpsolver.ifs.solver.Solver;
    023import org.cpsolver.ifs.util.DataProperties;
    024
    025
    026/**
    027 * Abstract Criterion. <br>
    028 * <br>
    029 * An optimization objective can be split into several (optimization) criteria
    030 * and modeled as a weighted sum of these. This makes the implementation of a particular problem
    031 * more versatile as it allows for an easier modification of the optimization objective.
    032 * <br>
    033 * This class implements most of the {@link Criterion} except of the {@link Criterion#getValue(Assignment, Value, Set)}.
    034 *
    035 * @author  Tomáš Müller
    036 * @version IFS 1.3 (Iterative Forward Search)<br>
    037 *          Copyright (C) 2006 - 2014 Tomáš Müller<br>
    038 *          <a href="mailto:muller@unitime.org">muller@unitime.org</a><br>
    039 *          <a href="http://muller.unitime.org">http://muller.unitime.org</a><br>
    040 * <br>
    041 *          This library is free software; you can redistribute it and/or modify
    042 *          it under the terms of the GNU Lesser General Public License as
    043 *          published by the Free Software Foundation; either version 3 of the
    044 *          License, or (at your option) any later version. <br>
    045 * <br>
    046 *          This library is distributed in the hope that it will be useful, but
    047 *          WITHOUT ANY WARRANTY; without even the implied warranty of
    048 *          MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
    049 *          Lesser General Public License for more details. <br>
    050 * <br>
    051 *          You should have received a copy of the GNU Lesser General Public
    052 *          License along with this library; if not see
    053 *          <a href='http://www.gnu.org/licenses/'>http://www.gnu.org/licenses/</a>.
    054 * @param <V> Variable
    055 * @param <T> Value
    056 */
    057public abstract class AbstractCriterion<V extends Variable<V, T>, T extends Value<V, T>> implements Criterion<V, T>, HasAssignmentContext<V, T, AbstractCriterion<V,T>.ValueContext>, CanHoldContext {
    058    private Model<V, T> iModel;
    059    protected double iBest = 0.0, iWeight = 0.0;
    060    protected static java.text.DecimalFormat sDoubleFormat = new java.text.DecimalFormat("0.##",
    061            new java.text.DecimalFormatSymbols(Locale.US));
    062    protected static java.text.DecimalFormat sPercentFormat = new java.text.DecimalFormat("0.##",
    063            new java.text.DecimalFormatSymbols(Locale.US));
    064    protected boolean iDebug = false;
    065
    066    private AssignmentContextReference<V, T, ValueContext> iContextReference = null;
    067    private AssignmentContext[] iContext = new AssignmentContext[CanHoldContext.sMaxSize];
    068    private int iLastCacheId = 0;
    069
    070
    071    /**
    072     * Defines how the overall value of the criterion should be automatically updated (using {@link Criterion#getValue(Value, Set)}).
    073     */
    074    protected static enum ValueUpdateType {
    075        /** Update is done before an unassignment (decrement) and before an assignment (increment). */
    076        BeforeUnassignedBeforeAssigned,
    077        /** Update is done after an unassignment (decrement) and before an assignment (increment). */
    078        AfterUnassignedBeforeAssigned,
    079        /** Update is done before an unassignment (decrement) and after an assignment (increment). */
    080        BeforeUnassignedAfterAssigned,
    081        /** Update is done after an unassignment (decrement) and after an assignment (increment). This is the default. */
    082        AfterUnassignedAfterAssigned,
    083        /** Criterion is to be updated manually (e.g., using {@link Criterion#inc(Assignment, double)}). */
    084        NoUpdate
    085    }
    086    private ValueUpdateType iValueUpdateType = ValueUpdateType.BeforeUnassignedBeforeAssigned;
    087
    088    /** Defines weight name (to be used to get the criterion weight from the configuration).
    089     * @return name of the weight associated with this criterion
    090     **/
    091    public String getWeightName() {
    092        return "Weight." + getClass().getName().substring(1 + getClass().getName().lastIndexOf('.'));
    093    }
    094
    095    /** Defines default weight (when {@link AbstractCriterion#getWeightName()} parameter is not present in the criterion).
    096     * @param config solver configuration
    097     * @return default criterion weight value
    098     **/
    099    public double getWeightDefault(DataProperties config) {
    100        return 0.0;
    101    }
    102
    103    @Override
    104    public void setModel(Model<V,T> model) {
    105        iModel = model;
    106        if (model != null)
    107            iContextReference = model.createReference(this);
    108    }
    109
    110    @Override
    111    public void configure(DataProperties properties) {
    112        iWeight = properties.getPropertyDouble(getWeightName(), getWeightDefault(properties));
    113        iDebug = properties.getPropertyBoolean("Debug." + getClass().getName().substring(1 + getClass().getName().lastIndexOf('.')), properties.getPropertyBoolean("Debug.Criterion", false));
    114    }
    115
    116    @Override
    117    public boolean init(Solver<V, T> solver) {
    118        configure(solver.getProperties());
    119        return true;
    120    }
    121
    122    /**
    123     * Returns current model
    124     * @return problem model
    125     **/
    126    public Model<V, T> getModel() { return iModel; }
    127
    128    /**
    129     * Returns an assignment context associated with this criterion. If there is no
    130     * assignment context associated with this criterion yet, one is created using the
    131     * {@link ConstraintWithContext#createAssignmentContext(Assignment)} method. From that time on,
    132     * this context is kept with the assignment and automatically updated by calling the
    133     * {@link AssignmentConstraintContext#assigned(Assignment, Value)} and {@link AssignmentConstraintContext#unassigned(Assignment, Value)}
    134     * whenever a variable is changed as given by the {@link ValueUpdateType}.
    135     * @param assignment given assignment
    136     * @return assignment context associated with this constraint and the given assignment
    137     */
    138    @Override
    139    public ValueContext getContext(Assignment<V, T> assignment) {
    140        return AssignmentContextHelper.getContext(this, assignment);
    141    }
    142
    143    @Override
    144    public ValueContext createAssignmentContext(Assignment<V,T> assignment) {
    145        return new ValueContext(assignment);
    146    }
    147
    148    @Override
    149    public AssignmentContextReference<V, T, ValueContext> getAssignmentContextReference() { return iContextReference; }
    150
    151    @Override
    152    public void setAssignmentContextReference(AssignmentContextReference<V, T, ValueContext> reference) { iContextReference = reference; }
    153
    154    @Override
    155    public AssignmentContext[] getContext() {
    156        return iContext;
    157    }
    158
    159    @Override
    160    public double getValue(Assignment<V, T> assignment) {
    161        return getContext(assignment).getTotal();
    162    }
    163
    164    @Override
    165    public double getBest() {
    166        return iBest;
    167    }
    168
    169    @Override
    170    public double getValue(Assignment<V, T> assignment, Collection<V> variables) {
    171        double ret = 0;
    172        for (V v: variables) {
    173            T t = assignment.getValue(v);
    174            if (t != null) ret += getValue(assignment, t, null);
    175        }
    176        return ret;
    177    }
    178
    179
    180    @Override
    181    public double getWeight() {
    182        return iWeight;
    183    }
    184
    185    @Override
    186    public double getWeightedBest() {
    187        return getWeight() == 0.0 ? 0.0 : getWeight() * getBest();
    188    }
    189
    190    @Override
    191    public double getWeightedValue(Assignment<V, T> assignment) {
    192        return (getWeight() == 0.0 ? 0.0 : getWeight() * getValue(assignment));
    193    }
    194
    195    @Override
    196    public double getWeightedValue(Assignment<V, T> assignment, T value, Set<T> conflicts) {
    197        return (getWeight() == 0.0 ? 0.0 : getWeight() * getValue(assignment, value, conflicts));
    198    }
    199
    200    @Override
    201    public double getWeightedValue(Assignment<V, T> assignment, Collection<V> variables) {
    202        return (getWeight() == 0.0 ? 0.0 : getWeight() * getValue(assignment, variables));
    203    }
    204
    205    /** Compute bounds (bounds are being cached by default).
    206     * @param assignment current assignment
    207     * @return minimum and maximum of this criterion's value
    208     **/
    209    protected double[] computeBounds(Assignment<V, T> assignment) {
    210        return getBounds(assignment, new ArrayList<V>(getModel().variables()));
    211    }
    212
    213    @Override
    214    public double[] getBounds(Assignment<V, T> assignment) {
    215        return getContext(assignment).getBounds(assignment);
    216    }
    217
    218    @Override
    219    public double[] getBounds(Assignment<V, T> assignment, Collection<V> variables) {
    220        double[] bounds = new double[] { 0.0, 0.0 };
    221        for (V v: variables) {
    222            Double min = null, max = null;
    223            for (T t: v.values(assignment)) {
    224                double value = getValue(assignment, t, null);
    225                if (min == null) { min = value; max = value; continue; }
    226                min = Math.min(min, value);
    227                max = Math.max(max, value);
    228            }
    229            if (min != null) {
    230                bounds[0] += min;
    231                bounds[1] += max;
    232            }
    233        }
    234        return bounds;
    235    }
    236
    237    @Override
    238    public void beforeAssigned(Assignment<V, T> assignment, long iteration, T value) {
    239        switch (getValueUpdateType()) {
    240            case AfterUnassignedBeforeAssigned:
    241            case BeforeUnassignedBeforeAssigned:
    242                getContext(assignment).assigned(assignment, value);
    243        }
    244    }
    245
    246    @Override
    247    public void afterAssigned(Assignment<V, T> assignment, long iteration, T value) {
    248        switch (getValueUpdateType()) {
    249            case AfterUnassignedAfterAssigned:
    250            case BeforeUnassignedAfterAssigned:
    251                getContext(assignment).assigned(assignment, value);
    252        }
    253    }
    254
    255    @Override
    256    public void beforeUnassigned(Assignment<V, T> assignment, long iteration, T value) {
    257        switch (getValueUpdateType()) {
    258            case BeforeUnassignedAfterAssigned:
    259            case BeforeUnassignedBeforeAssigned:
    260                getContext(assignment).unassigned(assignment, value);
    261        }
    262    }
    263
    264    @Override
    265    public void afterUnassigned(Assignment<V, T> assignment, long iteration, T value) {
    266        switch (getValueUpdateType()) {
    267            case AfterUnassignedAfterAssigned:
    268            case AfterUnassignedBeforeAssigned:
    269                getContext(assignment).unassigned(assignment, value);
    270        }
    271    }
    272
    273    @Override
    274    public void bestSaved(Assignment<V, T> assignment) {
    275        iBest = getContext(assignment).getTotal();
    276    }
    277
    278    @Override
    279    public void bestRestored(Assignment<V, T> assignment) {
    280        getContext(assignment).setTotal(iBest);
    281    }
    282
    283    @Override
    284    public void inc(Assignment<V, T> assignment, double value) {
    285        getContext(assignment).inc(value);
    286    }
    287
    288    @Override
    289    public String getName() {
    290        return getClass().getName().substring(1 + getClass().getName().lastIndexOf('.')).replaceAll("(?<=[^A-Z])([A-Z])"," $1");
    291    }
    292
    293    /** Clear bounds cache */
    294    protected void clearCache() {
    295        iLastCacheId++;
    296    }
    297
    298    @Override
    299    public void variableAdded(V variable) {
    300        clearCache();
    301    }
    302
    303    @Override
    304    public void variableRemoved(V variable) {
    305        clearCache();
    306    }
    307
    308    @Override
    309    public void constraintAdded(Constraint<V, T> constraint) {
    310        clearCache();
    311    }
    312
    313    @Override
    314    public void constraintRemoved(Constraint<V, T> constraint) {
    315        clearCache();
    316    }
    317
    318    protected String getPerc(double value, double min, double max) {
    319        if (max == min)
    320            return sPercentFormat.format(100.0);
    321        return sPercentFormat.format(100.0 - 100.0 * (value - min) / (max - min));
    322    }
    323
    324    protected String getPercRev(double value, double min, double max) {
    325        if (max == min)
    326            return sPercentFormat.format(0.0);
    327        return sPercentFormat.format(100.0 * (value - min) / (max - min));
    328    }
    329
    330    @Override
    331    public void getInfo(Assignment<V, T> assignment, Map<String, String> info) {
    332    }
    333
    334    @Override
    335    public void getInfo(Assignment<V, T> assignment, Map<String, String> info, Collection<V> variables) {
    336    }
    337
    338    /**
    339     * Return formatted value of this criterion, as percentage when possible
    340     * @param assignment current assignment
    341     * @return formatted value
    342     */
    343    public String getPercentage(Assignment<V, T> assignment) {
    344        double val = getValue(assignment);
    345        double[] bounds = getBounds(assignment);
    346        if (bounds[0] <= val && val <= bounds[1] && bounds[0] < bounds[1])
    347            return getPerc(val, bounds[0], bounds[1]) + "%";
    348        else if (bounds[1] <= val && val <= bounds[0] && bounds[1] < bounds[0])
    349            return getPercRev(val, bounds[1], bounds[0]) + "%";
    350        else
    351            return sDoubleFormat.format(val);
    352    }
    353
    354    @Override
    355    public void getExtendedInfo(Assignment<V, T> assignment, Map<String, String> info) {
    356        if (iDebug) {
    357            double val = getValue(assignment), w = getWeightedValue(assignment), prec = getValue(assignment, getModel().variables());
    358            double[] bounds = getBounds(assignment);
    359            if (bounds[0] <= val && val <= bounds[1] && bounds[0] < bounds[1])
    360                info.put("[C] " + getName(),
    361                        getPerc(val, bounds[0], bounds[1]) + "% (value: " + sDoubleFormat.format(val) +
    362                        (Math.abs(prec - val) > 0.0001 ? ", precise:" + sDoubleFormat.format(prec) : "") +
    363                        ", weighted:" + sDoubleFormat.format(w) +
    364                        ", bounds: " + sDoubleFormat.format(bounds[0]) + ".." + sDoubleFormat.format(bounds[1]) + ")");
    365            else if (bounds[1] <= val && val <= bounds[0] && bounds[1] < bounds[0])
    366                info.put("[C] " + getName(),
    367                        getPercRev(val, bounds[1], bounds[0]) + "% (value: " + sDoubleFormat.format(val) +
    368                        (Math.abs(prec - val) > 0.0001 ? ", precise:" + sDoubleFormat.format(prec) : "") +
    369                        ", weighted:" + sDoubleFormat.format(w) +
    370                        ", bounds: " + sDoubleFormat.format(bounds[1]) + ".." + sDoubleFormat.format(bounds[0]) + ")");
    371            else if (bounds[0] != val || val != bounds[1])
    372                info.put("[C] " + getName(),
    373                        sDoubleFormat.format(val) + " (" +
    374                        (Math.abs(prec - val) > 0.0001 ? "precise:" + sDoubleFormat.format(prec) + ", ": "") +
    375                        "weighted:" + sDoubleFormat.format(w) +
    376                        (bounds[0] != bounds[1] ? ", bounds: " + sDoubleFormat.format(bounds[0]) + ".." + sDoubleFormat.format(bounds[1]) : "") +
    377                        ")");
    378        }
    379    }
    380
    381    /**
    382     * Assignment context holding current value and the cached bounds.
    383     */
    384    public class ValueContext implements AssignmentContext {
    385        protected double iTotal = 0.0;
    386        private double[] iBounds = null;
    387        private int iCacheId = -1;
    388
    389        /** Create from an assignment
    390         * @param assignment current assignment
    391         **/
    392        protected ValueContext(Assignment<V, T> assignment) {
    393            if (getValueUpdateType() != ValueUpdateType.NoUpdate)
    394                iTotal = AbstractCriterion.this.getValue(assignment, getModel().variables());
    395        }
    396
    397        protected ValueContext() {}
    398
    399        /** Update value when unassigned
    400         * @param assignment current assignment
    401         * @param value recently unassigned value
    402         **/
    403        protected void unassigned(Assignment<V, T> assignment, T value) {
    404            iTotal -= getValue(assignment, value, null);
    405        }
    406
    407        /** Update value when assigned
    408         * @param assignment current assignment
    409         * @param value recently assigned value
    410         **/
    411        protected void assigned(Assignment<V, T> assignment, T value) {
    412            iTotal += getValue(assignment, value, null);
    413        }
    414
    415        /** Return value
    416         * @return current value of the criterion
    417         **/
    418        public double getTotal() { return iTotal; }
    419
    420        /** Set value
    421         * @param value current value of the criterion
    422         **/
    423        public void setTotal(double value) { iTotal = value; }
    424
    425        /** Increment value
    426         * @param value increment
    427         **/
    428        public void inc(double value) { iTotal += value; }
    429
    430        /** Return bounds
    431         * @param assignment current assignment
    432         * @return minimum and maximum of this criterion's value
    433         **/
    434        protected double[] getBounds(Assignment<V, T> assignment) {
    435            if (iBounds == null || iCacheId < iLastCacheId) {
    436                iCacheId = iLastCacheId;
    437                iBounds = computeBounds(assignment);
    438            }
    439            return (iBounds == null ? new double[] {0.0, 0.0} : iBounds);
    440        }
    441
    442        /** Set bounds
    443         * @param bounds bounds to cache
    444         **/
    445        protected void setBounds(double[] bounds) {
    446            iBounds = bounds;
    447        }
    448    }
    449
    450    @Override
    451    @Deprecated
    452    public double getWeightedValue() {
    453        return getWeightedValue(getModel().getDefaultAssignment());
    454    }
    455
    456    @Override
    457    @Deprecated
    458    public double[] getBounds() {
    459        return getBounds(getModel().getDefaultAssignment());
    460    }
    461
    462    @Override
    463    @Deprecated
    464    public double getWeightedValue(T value, Set<T> conflicts) {
    465        return getWeightedValue(getModel().getDefaultAssignment(), value, conflicts);
    466    }
    467
    468    @Override
    469    @Deprecated
    470    public double getValue(T value, Set<T> conflicts) {
    471        return getValue(getModel().getDefaultAssignment(), value, conflicts);
    472    }
    473
    474    @Override
    475    @Deprecated
    476    public double getWeightedValue(Collection<V> variables) {
    477        return getWeightedValue(getModel().getDefaultAssignment(), variables);
    478    }
    479
    480    @Override
    481    @Deprecated
    482    public double getValue(Collection<V> variables) {
    483        return getValue(getModel().getDefaultAssignment(), variables);
    484    }
    485
    486    @Override
    487    @Deprecated
    488    public double[] getBounds(Collection<V> variables) {
    489        return getBounds(getModel().getDefaultAssignment(), variables);
    490    }
    491
    492    @Override
    493    @Deprecated
    494    public void inc(double value) {
    495        inc(getModel().getDefaultAssignment(), value);
    496    }
    497
    498    /** Abbreviated name of the criterion for {@link TimetablingCriterion#toString()}.
    499     * @return abbreviated name of the criterion
    500     **/
    501    public String getAbbreviation() {
    502        return getName().replaceAll("[a-z ]","");
    503    }
    504
    505    /**
    506     * Simple text representation of the criterion and its value. E.g., X:x where X is the {@link AbstractCriterion#getAbbreviation()}
    507     * and x is the current value {@link AbstractCriterion#getValue(Assignment)}.
    508     * @param assignment current assignment
    509     * @return short string representation (e.g., PP:95% for period preference)
    510     */
    511    @Override
    512    public String toString(Assignment<V, T> assignment) {
    513        double val = getValue(assignment);
    514        if (Math.abs(getWeightedValue(assignment)) < 0.005) return "";
    515        double[] bounds = getBounds(assignment);
    516        if (bounds[0] <= val && val <= bounds[1] && bounds[0] < bounds[1] && getName().endsWith(" Preferences"))
    517            return getAbbreviation() + ":" + sDoubleFormat.format(getValue(assignment)) + " (" + getPerc(val, bounds[0], bounds[1]) + "%)";
    518        else if (bounds[1] <= val && val <= bounds[0] && bounds[1] < bounds[0] && getName().endsWith(" Preferences"))
    519            return getAbbreviation() + ":" + sDoubleFormat.format(getValue(assignment)) + " (" + getPercRev(val, bounds[1], bounds[0]) + ")%";
    520        else if (bounds[0] != val || val != bounds[1])
    521            return getAbbreviation() + ":" + sDoubleFormat.format(getValue(assignment));
    522        else
    523            return "";
    524    }
    525
    526    public ValueUpdateType getValueUpdateType() {
    527        return iValueUpdateType;
    528    }
    529
    530    public void setValueUpdateType(ValueUpdateType iValueUpdateType) {
    531        this.iValueUpdateType = iValueUpdateType;
    532    }
    533}