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