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