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]) + "…" + 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]) + "…" + 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]) + "…" + 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]) + "…" + 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]) + "…" + 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]) + "…" + sDoubleFormat.format(bounds[1]) : "") +
306 ")");
307 }
308 }
309 }