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