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