001    package net.sf.cpsolver.ifs.criteria;
002    
003    import java.util.ArrayList;
004    import java.util.Collection;
005    import java.util.Locale;
006    import java.util.Map;
007    import java.util.Set;
008    
009    import net.sf.cpsolver.ifs.model.Constraint;
010    import net.sf.cpsolver.ifs.model.Model;
011    import net.sf.cpsolver.ifs.model.Value;
012    import net.sf.cpsolver.ifs.model.Variable;
013    import net.sf.cpsolver.ifs.solver.Solver;
014    import 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 Tomas Muller<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     */
044    public 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    }