Source code

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}