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]) + "…" + 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]) + "…" + 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]) + "…" + 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]) + "…" + 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]) + "…" + 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]) + "…" + sDoubleFormat.format(bounds[1]) : "") + 318 ")"); 319 } 320 } 321 }