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]) + "…" + 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}