001package org.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 org.cpsolver.coursett.criteria.TimetablingCriterion; 010import org.cpsolver.ifs.assignment.Assignment; 011import org.cpsolver.ifs.assignment.context.AssignmentConstraintContext; 012import org.cpsolver.ifs.assignment.context.AssignmentContext; 013import org.cpsolver.ifs.assignment.context.AssignmentContextReference; 014import org.cpsolver.ifs.assignment.context.CanHoldContext; 015import org.cpsolver.ifs.assignment.context.ConstraintWithContext; 016import org.cpsolver.ifs.assignment.context.HasAssignmentContext; 017import org.cpsolver.ifs.model.Constraint; 018import org.cpsolver.ifs.model.Model; 019import org.cpsolver.ifs.model.Value; 020import org.cpsolver.ifs.model.Variable; 021import org.cpsolver.ifs.solver.Solver; 022import org.cpsolver.ifs.util.DataProperties; 023 024 025/** 026 * Abstract Criterion. <br> 027 * <br> 028 * An optimization objective can be split into several (optimization) criteria 029 * and modeled as a weighted sum of these. This makes the implementation of a particular problem 030 * more versatile as it allows for an easier modification of the optimization objective. 031 * <br> 032 * This class implements most of the {@link Criterion} except of the {@link Criterion#getValue(Assignment, Value, Set)}. 033 * 034 * @version IFS 1.3 (Iterative Forward Search)<br> 035 * Copyright (C) 2006 - 2014 Tomas Muller<br> 036 * <a href="mailto:muller@unitime.org">muller@unitime.org</a><br> 037 * <a href="http://muller.unitime.org">http://muller.unitime.org</a><br> 038 * <br> 039 * This library is free software; you can redistribute it and/or modify 040 * it under the terms of the GNU Lesser General Public License as 041 * published by the Free Software Foundation; either version 3 of the 042 * License, or (at your option) any later version. <br> 043 * <br> 044 * This library is distributed in the hope that it will be useful, but 045 * WITHOUT ANY WARRANTY; without even the implied warranty of 046 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 047 * Lesser General Public License for more details. <br> 048 * <br> 049 * You should have received a copy of the GNU Lesser General Public 050 * License along with this library; if not see 051 * <a href='http://www.gnu.org/licenses/'>http://www.gnu.org/licenses/</a>. 052 * @param <V> Variable 053 * @param <T> Value 054 */ 055public abstract class AbstractCriterion<V extends Variable<V, T>, T extends Value<V, T>> implements Criterion<V, T>, HasAssignmentContext<V, T, AbstractCriterion<V,T>.ValueContext>, CanHoldContext { 056 private Model<V, T> iModel; 057 protected double iBest = 0.0, iWeight = 0.0; 058 protected static java.text.DecimalFormat sDoubleFormat = new java.text.DecimalFormat("0.##", 059 new java.text.DecimalFormatSymbols(Locale.US)); 060 protected static java.text.DecimalFormat sPercentFormat = new java.text.DecimalFormat("0.##", 061 new java.text.DecimalFormatSymbols(Locale.US)); 062 protected boolean iDebug = false; 063 064 private AssignmentContextReference<V, T, ValueContext> iContextReference = null; 065 private AssignmentContext[] iContext = null; 066 private int iLastCacheId = 0; 067 068 069 /** 070 * Defines how the overall value of the criterion should be automatically updated (using {@link Criterion#getValue(Value, Set)}). 071 */ 072 protected static enum ValueUpdateType { 073 /** Update is done before an unassignment (decrement) and before an assignment (increment). */ 074 BeforeUnassignedBeforeAssigned, 075 /** Update is done after an unassignment (decrement) and before an assignment (increment). */ 076 AfterUnassignedBeforeAssigned, 077 /** Update is done before an unassignment (decrement) and after an assignment (increment). */ 078 BeforeUnassignedAfterAssigned, 079 /** Update is done after an unassignment (decrement) and after an assignment (increment). This is the default. */ 080 AfterUnassignedAfterAssigned, 081 /** Criterion is to be updated manually (e.g., using {@link Criterion#inc(Assignment, double)}). */ 082 NoUpdate 083 } 084 private ValueUpdateType iValueUpdateType = ValueUpdateType.BeforeUnassignedBeforeAssigned; 085 086 /** Defines weight name (to be used to get the criterion weight from the configuration). 087 * @return name of the weight associated with this criterion 088 **/ 089 public String getWeightName() { 090 return "Weight." + getClass().getName().substring(1 + getClass().getName().lastIndexOf('.')); 091 } 092 093 /** Defines default weight (when {@link AbstractCriterion#getWeightName()} parameter is not present in the criterion). 094 * @param config solver configuration 095 * @return default criterion weight value 096 **/ 097 public double getWeightDefault(DataProperties config) { 098 return 0.0; 099 } 100 101 @Override 102 public void setModel(Model<V,T> model) { 103 iModel = model; 104 if (model != null) 105 iContextReference = model.createReference(this); 106 } 107 108 @Override 109 public boolean init(Solver<V, T> solver) { 110 iWeight = solver.getProperties().getPropertyDouble(getWeightName(), getWeightDefault(solver.getProperties())); 111 iDebug = solver.getProperties().getPropertyBoolean( 112 "Debug." + getClass().getName().substring(1 + getClass().getName().lastIndexOf('.')), 113 solver.getProperties().getPropertyBoolean("Debug.Criterion", false)); 114 return true; 115 } 116 117 /** 118 * Returns current model 119 * @return problem model 120 **/ 121 public Model<V, T> getModel() { return iModel; } 122 123 /** 124 * Returns an assignment context associated with this criterion. If there is no 125 * assignment context associated with this criterion yet, one is created using the 126 * {@link ConstraintWithContext#createAssignmentContext(Assignment)} method. From that time on, 127 * this context is kept with the assignment and automatically updated by calling the 128 * {@link AssignmentConstraintContext#assigned(Assignment, Value)} and {@link AssignmentConstraintContext#unassigned(Assignment, Value)} 129 * whenever a variable is changed as given by the {@link ValueUpdateType}. 130 * @param assignment given assignment 131 * @return assignment context associated with this constraint and the given assignment 132 */ 133 @SuppressWarnings("unchecked") 134 @Override 135 public ValueContext getContext(Assignment<V, T> assignment) { 136 if (iContext != null && assignment.getIndex() >= 0 && assignment.getIndex() < iContext.length) { 137 AssignmentContext c = iContext[assignment.getIndex()]; 138 if (c != null) return (ValueContext) c; 139 } 140 return assignment.getAssignmentContext(getAssignmentContextReference()); 141 } 142 143 @Override 144 public ValueContext createAssignmentContext(Assignment<V,T> assignment) { 145 return new ValueContext(assignment); 146 } 147 148 @Override 149 public AssignmentContextReference<V, T, ValueContext> getAssignmentContextReference() { return iContextReference; } 150 151 @Override 152 public void setAssignmentContextReference(AssignmentContextReference<V, T, ValueContext> reference) { iContextReference = reference; } 153 154 @Override 155 public AssignmentContext[] getContext() { 156 return iContext; 157 } 158 159 @Override 160 public void setContext(AssignmentContext[] context) { 161 iContext = context; 162 } 163 164 @Override 165 public double getValue(Assignment<V, T> assignment) { 166 return getContext(assignment).getTotal(); 167 } 168 169 @Override 170 public double getBest() { 171 return iBest; 172 } 173 174 @Override 175 public double getValue(Assignment<V, T> assignment, Collection<V> variables) { 176 double ret = 0; 177 for (V v: variables) { 178 T t = assignment.getValue(v); 179 if (t != null) ret += getValue(assignment, t, null); 180 } 181 return ret; 182 } 183 184 185 @Override 186 public double getWeight() { 187 return iWeight; 188 } 189 190 @Override 191 public double getWeightedBest() { 192 return getWeight() == 0.0 ? 0.0 : getWeight() * getBest(); 193 } 194 195 @Override 196 public double getWeightedValue(Assignment<V, T> assignment) { 197 return (getWeight() == 0.0 ? 0.0 : getWeight() * getValue(assignment)); 198 } 199 200 @Override 201 public double getWeightedValue(Assignment<V, T> assignment, T value, Set<T> conflicts) { 202 return (getWeight() == 0.0 ? 0.0 : getWeight() * getValue(assignment, value, conflicts)); 203 } 204 205 @Override 206 public double getWeightedValue(Assignment<V, T> assignment, Collection<V> variables) { 207 return (getWeight() == 0.0 ? 0.0 : getWeight() * getValue(assignment, variables)); 208 } 209 210 /** Compute bounds (bounds are being cached by default). 211 * @param assignment current assignment 212 * @return minimum and maximum of this criterion's value 213 **/ 214 protected double[] computeBounds(Assignment<V, T> assignment) { 215 return getBounds(assignment, new ArrayList<V>(getModel().variables())); 216 } 217 218 @Override 219 public double[] getBounds(Assignment<V, T> assignment) { 220 return getContext(assignment).getBounds(assignment); 221 } 222 223 @Override 224 public double[] getBounds(Assignment<V, T> assignment, Collection<V> variables) { 225 double[] bounds = new double[] { 0.0, 0.0 }; 226 for (V v: variables) { 227 Double min = null, max = null; 228 for (T t: v.values(assignment)) { 229 double value = getValue(assignment, t, null); 230 if (min == null) { min = value; max = value; continue; } 231 min = Math.min(min, value); 232 max = Math.max(max, value); 233 } 234 if (min != null) { 235 bounds[0] += min; 236 bounds[1] += max; 237 } 238 } 239 return bounds; 240 } 241 242 @Override 243 public void beforeAssigned(Assignment<V, T> assignment, long iteration, T value) { 244 switch (getValueUpdateType()) { 245 case AfterUnassignedBeforeAssigned: 246 case BeforeUnassignedBeforeAssigned: 247 getContext(assignment).assigned(assignment, value); 248 } 249 } 250 251 @Override 252 public void afterAssigned(Assignment<V, T> assignment, long iteration, T value) { 253 switch (getValueUpdateType()) { 254 case AfterUnassignedAfterAssigned: 255 case BeforeUnassignedAfterAssigned: 256 getContext(assignment).assigned(assignment, value); 257 } 258 } 259 260 @Override 261 public void beforeUnassigned(Assignment<V, T> assignment, long iteration, T value) { 262 switch (getValueUpdateType()) { 263 case BeforeUnassignedAfterAssigned: 264 case BeforeUnassignedBeforeAssigned: 265 getContext(assignment).unassigned(assignment, value); 266 } 267 } 268 269 @Override 270 public void afterUnassigned(Assignment<V, T> assignment, long iteration, T value) { 271 switch (getValueUpdateType()) { 272 case AfterUnassignedAfterAssigned: 273 case AfterUnassignedBeforeAssigned: 274 getContext(assignment).unassigned(assignment, value); 275 } 276 } 277 278 @Override 279 public void bestSaved(Assignment<V, T> assignment) { 280 iBest = getContext(assignment).getTotal(); 281 } 282 283 @Override 284 public void bestRestored(Assignment<V, T> assignment) { 285 getContext(assignment).setTotal(iBest); 286 } 287 288 @Override 289 public void inc(Assignment<V, T> assignment, double value) { 290 getContext(assignment).inc(value); 291 } 292 293 @Override 294 public String getName() { 295 return getClass().getName().substring(1 + getClass().getName().lastIndexOf('.')).replaceAll("(?<=[^A-Z])([A-Z])"," $1"); 296 } 297 298 /** Clear bounds cache */ 299 protected void clearCache() { 300 iLastCacheId++; 301 } 302 303 @Override 304 public void variableAdded(V variable) { 305 clearCache(); 306 } 307 308 @Override 309 public void variableRemoved(V variable) { 310 clearCache(); 311 } 312 313 @Override 314 public void constraintAdded(Constraint<V, T> constraint) { 315 clearCache(); 316 } 317 318 @Override 319 public void constraintRemoved(Constraint<V, T> constraint) { 320 clearCache(); 321 } 322 323 protected String getPerc(double value, double min, double max) { 324 if (max == min) 325 return sPercentFormat.format(100.0); 326 return sPercentFormat.format(100.0 - 100.0 * (value - min) / (max - min)); 327 } 328 329 protected String getPercRev(double value, double min, double max) { 330 if (max == min) 331 return sPercentFormat.format(0.0); 332 return sPercentFormat.format(100.0 * (value - min) / (max - min)); 333 } 334 335 @Override 336 public void getInfo(Assignment<V, T> assignment, Map<String, String> info) { 337 } 338 339 @Override 340 public void getInfo(Assignment<V, T> assignment, Map<String, String> info, Collection<V> variables) { 341 } 342 343 @Override 344 public void getExtendedInfo(Assignment<V, T> assignment, Map<String, String> info) { 345 if (iDebug) { 346 double val = getValue(assignment), w = getWeightedValue(assignment), prec = getValue(assignment, getModel().variables()); 347 double[] bounds = getBounds(assignment); 348 if (bounds[0] <= val && val <= bounds[1] && bounds[0] < bounds[1]) 349 info.put("[C] " + getName(), 350 getPerc(val, bounds[0], bounds[1]) + "% (value: " + sDoubleFormat.format(val) + 351 (Math.abs(prec - val) > 0.0001 ? ", precise:" + sDoubleFormat.format(prec) : "") + 352 ", weighted:" + sDoubleFormat.format(w) + 353 ", bounds: " + sDoubleFormat.format(bounds[0]) + ".." + sDoubleFormat.format(bounds[1]) + ")"); 354 else if (bounds[1] <= val && val <= bounds[0] && bounds[1] < bounds[0]) 355 info.put("[C] " + getName(), 356 getPercRev(val, bounds[1], bounds[0]) + "% (value: " + sDoubleFormat.format(val) + 357 (Math.abs(prec - val) > 0.0001 ? ", precise:" + sDoubleFormat.format(prec) : "") + 358 ", weighted:" + sDoubleFormat.format(w) + 359 ", bounds: " + sDoubleFormat.format(bounds[1]) + ".." + sDoubleFormat.format(bounds[0]) + ")"); 360 else if (bounds[0] != val || val != bounds[1]) 361 info.put("[C] " + getName(), 362 sDoubleFormat.format(val) + " (" + 363 (Math.abs(prec - val) > 0.0001 ? "precise:" + sDoubleFormat.format(prec) + ", ": "") + 364 "weighted:" + sDoubleFormat.format(w) + 365 (bounds[0] != bounds[1] ? ", bounds: " + sDoubleFormat.format(bounds[0]) + ".." + sDoubleFormat.format(bounds[1]) : "") + 366 ")"); 367 } 368 } 369 370 /** 371 * Assignment context holding current value and the cached bounds. 372 */ 373 public class ValueContext implements AssignmentContext { 374 protected double iTotal = 0.0; 375 private double[] iBounds = null; 376 private int iCacheId = -1; 377 378 /** Create from an assignment 379 * @param assignment current assignment 380 **/ 381 protected ValueContext(Assignment<V, T> assignment) { 382 if (getValueUpdateType() != ValueUpdateType.NoUpdate) 383 iTotal = AbstractCriterion.this.getValue(assignment, getModel().variables()); 384 } 385 386 protected ValueContext() {} 387 388 /** Update value when unassigned 389 * @param assignment current assignment 390 * @param value recently unassigned value 391 **/ 392 protected void unassigned(Assignment<V, T> assignment, T value) { 393 iTotal -= getValue(assignment, value, null); 394 } 395 396 /** Update value when assigned 397 * @param assignment current assignment 398 * @param value recently assigned value 399 **/ 400 protected void assigned(Assignment<V, T> assignment, T value) { 401 iTotal += getValue(assignment, value, null); 402 } 403 404 /** Return value 405 * @return current value of the criterion 406 **/ 407 public double getTotal() { return iTotal; } 408 409 /** Set value 410 * @param value current value of the criterion 411 **/ 412 public void setTotal(double value) { iTotal = value; } 413 414 /** Increment value 415 * @param value increment 416 **/ 417 public void inc(double value) { iTotal += value; } 418 419 /** Return bounds 420 * @param assignment current assignment 421 * @return minimum and maximum of this criterion's value 422 **/ 423 protected double[] getBounds(Assignment<V, T> assignment) { 424 if (iBounds == null || iCacheId < iLastCacheId) { 425 iCacheId = iLastCacheId; 426 iBounds = computeBounds(assignment); 427 } 428 return (iBounds == null ? new double[] {0.0, 0.0} : iBounds); 429 } 430 431 /** Set bounds 432 * @param bounds bounds to cache 433 **/ 434 protected void setBounds(double[] bounds) { 435 iBounds = bounds; 436 } 437 } 438 439 @Override 440 @Deprecated 441 public double getWeightedValue() { 442 return getWeightedValue(getModel().getDefaultAssignment()); 443 } 444 445 @Override 446 @Deprecated 447 public double[] getBounds() { 448 return getBounds(getModel().getDefaultAssignment()); 449 } 450 451 @Override 452 @Deprecated 453 public double getWeightedValue(T value, Set<T> conflicts) { 454 return getWeightedValue(getModel().getDefaultAssignment(), value, conflicts); 455 } 456 457 @Override 458 @Deprecated 459 public double getValue(T value, Set<T> conflicts) { 460 return getValue(getModel().getDefaultAssignment(), value, conflicts); 461 } 462 463 @Override 464 @Deprecated 465 public double getWeightedValue(Collection<V> variables) { 466 return getWeightedValue(getModel().getDefaultAssignment(), variables); 467 } 468 469 @Override 470 @Deprecated 471 public double getValue(Collection<V> variables) { 472 return getValue(getModel().getDefaultAssignment(), variables); 473 } 474 475 @Override 476 @Deprecated 477 public double[] getBounds(Collection<V> variables) { 478 return getBounds(getModel().getDefaultAssignment(), variables); 479 } 480 481 @Override 482 @Deprecated 483 public void inc(double value) { 484 inc(getModel().getDefaultAssignment(), value); 485 } 486 487 /** Abbreviated name of the criterion for {@link TimetablingCriterion#toString()}. 488 * @return abbreviated name of the criterion 489 **/ 490 public String getAbbreviation() { 491 return getName().replaceAll("[a-z ]",""); 492 } 493 494 /** 495 * Simple text representation of the criterion and its value. E.g., X:x where X is the {@link AbstractCriterion#getAbbreviation()} 496 * and x is the current value {@link AbstractCriterion#getValue(Assignment)}. 497 * @param assignment current assignment 498 * @return short string representation (e.g., PP:95% for period preference) 499 */ 500 @Override 501 public String toString(Assignment<V, T> assignment) { 502 double val = getValue(assignment); 503 if (Math.abs(getWeightedValue(assignment)) < 0.005) return ""; 504 double[] bounds = getBounds(assignment); 505 if (bounds[0] <= val && val <= bounds[1] && bounds[0] < bounds[1] && getName().endsWith(" Preferences")) 506 return getAbbreviation() + ":" + getPerc(val, bounds[0], bounds[1]) + "%"; 507 else if (bounds[1] <= val && val <= bounds[0] && bounds[1] < bounds[0] && getName().endsWith(" Preferences")) 508 return getAbbreviation() + ":" + getPercRev(val, bounds[1], bounds[0]) + "%"; 509 else if (bounds[0] != val || val != bounds[1]) 510 return getAbbreviation() + ":" + sDoubleFormat.format(getValue(assignment)); 511 else 512 return ""; 513 } 514 515 public ValueUpdateType getValueUpdateType() { 516 return iValueUpdateType; 517 } 518 519 public void setValueUpdateType(ValueUpdateType iValueUpdateType) { 520 this.iValueUpdateType = iValueUpdateType; 521 } 522}