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 boolean init(Solver<V, T> solver) { 111 iWeight = solver.getProperties().getPropertyDouble(getWeightName(), getWeightDefault(solver.getProperties())); 112 iDebug = solver.getProperties().getPropertyBoolean( 113 "Debug." + getClass().getName().substring(1 + getClass().getName().lastIndexOf('.')), 114 solver.getProperties().getPropertyBoolean("Debug.Criterion", false)); 115 return true; 116 } 117 118 /** 119 * Returns current model 120 * @return problem model 121 **/ 122 public Model<V, T> getModel() { return iModel; } 123 124 /** 125 * Returns an assignment context associated with this criterion. If there is no 126 * assignment context associated with this criterion yet, one is created using the 127 * {@link ConstraintWithContext#createAssignmentContext(Assignment)} method. From that time on, 128 * this context is kept with the assignment and automatically updated by calling the 129 * {@link AssignmentConstraintContext#assigned(Assignment, Value)} and {@link AssignmentConstraintContext#unassigned(Assignment, Value)} 130 * whenever a variable is changed as given by the {@link ValueUpdateType}. 131 * @param assignment given assignment 132 * @return assignment context associated with this constraint and the given assignment 133 */ 134 @Override 135 public ValueContext getContext(Assignment<V, T> assignment) { 136 return AssignmentContextHelper.getContext(this, assignment); 137 } 138 139 @Override 140 public ValueContext createAssignmentContext(Assignment<V,T> assignment) { 141 return new ValueContext(assignment); 142 } 143 144 @Override 145 public AssignmentContextReference<V, T, ValueContext> getAssignmentContextReference() { return iContextReference; } 146 147 @Override 148 public void setAssignmentContextReference(AssignmentContextReference<V, T, ValueContext> reference) { iContextReference = reference; } 149 150 @Override 151 public AssignmentContext[] getContext() { 152 return iContext; 153 } 154 155 @Override 156 public double getValue(Assignment<V, T> assignment) { 157 return getContext(assignment).getTotal(); 158 } 159 160 @Override 161 public double getBest() { 162 return iBest; 163 } 164 165 @Override 166 public double getValue(Assignment<V, T> assignment, Collection<V> variables) { 167 double ret = 0; 168 for (V v: variables) { 169 T t = assignment.getValue(v); 170 if (t != null) ret += getValue(assignment, t, null); 171 } 172 return ret; 173 } 174 175 176 @Override 177 public double getWeight() { 178 return iWeight; 179 } 180 181 @Override 182 public double getWeightedBest() { 183 return getWeight() == 0.0 ? 0.0 : getWeight() * getBest(); 184 } 185 186 @Override 187 public double getWeightedValue(Assignment<V, T> assignment) { 188 return (getWeight() == 0.0 ? 0.0 : getWeight() * getValue(assignment)); 189 } 190 191 @Override 192 public double getWeightedValue(Assignment<V, T> assignment, T value, Set<T> conflicts) { 193 return (getWeight() == 0.0 ? 0.0 : getWeight() * getValue(assignment, value, conflicts)); 194 } 195 196 @Override 197 public double getWeightedValue(Assignment<V, T> assignment, Collection<V> variables) { 198 return (getWeight() == 0.0 ? 0.0 : getWeight() * getValue(assignment, variables)); 199 } 200 201 /** Compute bounds (bounds are being cached by default). 202 * @param assignment current assignment 203 * @return minimum and maximum of this criterion's value 204 **/ 205 protected double[] computeBounds(Assignment<V, T> assignment) { 206 return getBounds(assignment, new ArrayList<V>(getModel().variables())); 207 } 208 209 @Override 210 public double[] getBounds(Assignment<V, T> assignment) { 211 return getContext(assignment).getBounds(assignment); 212 } 213 214 @Override 215 public double[] getBounds(Assignment<V, T> assignment, Collection<V> variables) { 216 double[] bounds = new double[] { 0.0, 0.0 }; 217 for (V v: variables) { 218 Double min = null, max = null; 219 for (T t: v.values(assignment)) { 220 double value = getValue(assignment, t, null); 221 if (min == null) { min = value; max = value; continue; } 222 min = Math.min(min, value); 223 max = Math.max(max, value); 224 } 225 if (min != null) { 226 bounds[0] += min; 227 bounds[1] += max; 228 } 229 } 230 return bounds; 231 } 232 233 @Override 234 public void beforeAssigned(Assignment<V, T> assignment, long iteration, T value) { 235 switch (getValueUpdateType()) { 236 case AfterUnassignedBeforeAssigned: 237 case BeforeUnassignedBeforeAssigned: 238 getContext(assignment).assigned(assignment, value); 239 } 240 } 241 242 @Override 243 public void afterAssigned(Assignment<V, T> assignment, long iteration, T value) { 244 switch (getValueUpdateType()) { 245 case AfterUnassignedAfterAssigned: 246 case BeforeUnassignedAfterAssigned: 247 getContext(assignment).assigned(assignment, value); 248 } 249 } 250 251 @Override 252 public void beforeUnassigned(Assignment<V, T> assignment, long iteration, T value) { 253 switch (getValueUpdateType()) { 254 case BeforeUnassignedAfterAssigned: 255 case BeforeUnassignedBeforeAssigned: 256 getContext(assignment).unassigned(assignment, value); 257 } 258 } 259 260 @Override 261 public void afterUnassigned(Assignment<V, T> assignment, long iteration, T value) { 262 switch (getValueUpdateType()) { 263 case AfterUnassignedAfterAssigned: 264 case AfterUnassignedBeforeAssigned: 265 getContext(assignment).unassigned(assignment, value); 266 } 267 } 268 269 @Override 270 public void bestSaved(Assignment<V, T> assignment) { 271 iBest = getContext(assignment).getTotal(); 272 } 273 274 @Override 275 public void bestRestored(Assignment<V, T> assignment) { 276 getContext(assignment).setTotal(iBest); 277 } 278 279 @Override 280 public void inc(Assignment<V, T> assignment, double value) { 281 getContext(assignment).inc(value); 282 } 283 284 @Override 285 public String getName() { 286 return getClass().getName().substring(1 + getClass().getName().lastIndexOf('.')).replaceAll("(?<=[^A-Z])([A-Z])"," $1"); 287 } 288 289 /** Clear bounds cache */ 290 protected void clearCache() { 291 iLastCacheId++; 292 } 293 294 @Override 295 public void variableAdded(V variable) { 296 clearCache(); 297 } 298 299 @Override 300 public void variableRemoved(V variable) { 301 clearCache(); 302 } 303 304 @Override 305 public void constraintAdded(Constraint<V, T> constraint) { 306 clearCache(); 307 } 308 309 @Override 310 public void constraintRemoved(Constraint<V, T> constraint) { 311 clearCache(); 312 } 313 314 protected String getPerc(double value, double min, double max) { 315 if (max == min) 316 return sPercentFormat.format(100.0); 317 return sPercentFormat.format(100.0 - 100.0 * (value - min) / (max - min)); 318 } 319 320 protected String getPercRev(double value, double min, double max) { 321 if (max == min) 322 return sPercentFormat.format(0.0); 323 return sPercentFormat.format(100.0 * (value - min) / (max - min)); 324 } 325 326 @Override 327 public void getInfo(Assignment<V, T> assignment, Map<String, String> info) { 328 } 329 330 @Override 331 public void getInfo(Assignment<V, T> assignment, Map<String, String> info, Collection<V> variables) { 332 } 333 334 @Override 335 public void getExtendedInfo(Assignment<V, T> assignment, Map<String, String> info) { 336 if (iDebug) { 337 double val = getValue(assignment), w = getWeightedValue(assignment), prec = getValue(assignment, getModel().variables()); 338 double[] bounds = getBounds(assignment); 339 if (bounds[0] <= val && val <= bounds[1] && bounds[0] < bounds[1]) 340 info.put("[C] " + getName(), 341 getPerc(val, bounds[0], bounds[1]) + "% (value: " + sDoubleFormat.format(val) + 342 (Math.abs(prec - val) > 0.0001 ? ", precise:" + sDoubleFormat.format(prec) : "") + 343 ", weighted:" + sDoubleFormat.format(w) + 344 ", bounds: " + sDoubleFormat.format(bounds[0]) + ".." + sDoubleFormat.format(bounds[1]) + ")"); 345 else if (bounds[1] <= val && val <= bounds[0] && bounds[1] < bounds[0]) 346 info.put("[C] " + getName(), 347 getPercRev(val, bounds[1], bounds[0]) + "% (value: " + sDoubleFormat.format(val) + 348 (Math.abs(prec - val) > 0.0001 ? ", precise:" + sDoubleFormat.format(prec) : "") + 349 ", weighted:" + sDoubleFormat.format(w) + 350 ", bounds: " + sDoubleFormat.format(bounds[1]) + ".." + sDoubleFormat.format(bounds[0]) + ")"); 351 else if (bounds[0] != val || val != bounds[1]) 352 info.put("[C] " + getName(), 353 sDoubleFormat.format(val) + " (" + 354 (Math.abs(prec - val) > 0.0001 ? "precise:" + sDoubleFormat.format(prec) + ", ": "") + 355 "weighted:" + sDoubleFormat.format(w) + 356 (bounds[0] != bounds[1] ? ", bounds: " + sDoubleFormat.format(bounds[0]) + ".." + sDoubleFormat.format(bounds[1]) : "") + 357 ")"); 358 } 359 } 360 361 /** 362 * Assignment context holding current value and the cached bounds. 363 */ 364 public class ValueContext implements AssignmentContext { 365 protected double iTotal = 0.0; 366 private double[] iBounds = null; 367 private int iCacheId = -1; 368 369 /** Create from an assignment 370 * @param assignment current assignment 371 **/ 372 protected ValueContext(Assignment<V, T> assignment) { 373 if (getValueUpdateType() != ValueUpdateType.NoUpdate) 374 iTotal = AbstractCriterion.this.getValue(assignment, getModel().variables()); 375 } 376 377 protected ValueContext() {} 378 379 /** Update value when unassigned 380 * @param assignment current assignment 381 * @param value recently unassigned value 382 **/ 383 protected void unassigned(Assignment<V, T> assignment, T value) { 384 iTotal -= getValue(assignment, value, null); 385 } 386 387 /** Update value when assigned 388 * @param assignment current assignment 389 * @param value recently assigned value 390 **/ 391 protected void assigned(Assignment<V, T> assignment, T value) { 392 iTotal += getValue(assignment, value, null); 393 } 394 395 /** Return value 396 * @return current value of the criterion 397 **/ 398 public double getTotal() { return iTotal; } 399 400 /** Set value 401 * @param value current value of the criterion 402 **/ 403 public void setTotal(double value) { iTotal = value; } 404 405 /** Increment value 406 * @param value increment 407 **/ 408 public void inc(double value) { iTotal += value; } 409 410 /** Return bounds 411 * @param assignment current assignment 412 * @return minimum and maximum of this criterion's value 413 **/ 414 protected double[] getBounds(Assignment<V, T> assignment) { 415 if (iBounds == null || iCacheId < iLastCacheId) { 416 iCacheId = iLastCacheId; 417 iBounds = computeBounds(assignment); 418 } 419 return (iBounds == null ? new double[] {0.0, 0.0} : iBounds); 420 } 421 422 /** Set bounds 423 * @param bounds bounds to cache 424 **/ 425 protected void setBounds(double[] bounds) { 426 iBounds = bounds; 427 } 428 } 429 430 @Override 431 @Deprecated 432 public double getWeightedValue() { 433 return getWeightedValue(getModel().getDefaultAssignment()); 434 } 435 436 @Override 437 @Deprecated 438 public double[] getBounds() { 439 return getBounds(getModel().getDefaultAssignment()); 440 } 441 442 @Override 443 @Deprecated 444 public double getWeightedValue(T value, Set<T> conflicts) { 445 return getWeightedValue(getModel().getDefaultAssignment(), value, conflicts); 446 } 447 448 @Override 449 @Deprecated 450 public double getValue(T value, Set<T> conflicts) { 451 return getValue(getModel().getDefaultAssignment(), value, conflicts); 452 } 453 454 @Override 455 @Deprecated 456 public double getWeightedValue(Collection<V> variables) { 457 return getWeightedValue(getModel().getDefaultAssignment(), variables); 458 } 459 460 @Override 461 @Deprecated 462 public double getValue(Collection<V> variables) { 463 return getValue(getModel().getDefaultAssignment(), variables); 464 } 465 466 @Override 467 @Deprecated 468 public double[] getBounds(Collection<V> variables) { 469 return getBounds(getModel().getDefaultAssignment(), variables); 470 } 471 472 @Override 473 @Deprecated 474 public void inc(double value) { 475 inc(getModel().getDefaultAssignment(), value); 476 } 477 478 /** Abbreviated name of the criterion for {@link TimetablingCriterion#toString()}. 479 * @return abbreviated name of the criterion 480 **/ 481 public String getAbbreviation() { 482 return getName().replaceAll("[a-z ]",""); 483 } 484 485 /** 486 * Simple text representation of the criterion and its value. E.g., X:x where X is the {@link AbstractCriterion#getAbbreviation()} 487 * and x is the current value {@link AbstractCriterion#getValue(Assignment)}. 488 * @param assignment current assignment 489 * @return short string representation (e.g., PP:95% for period preference) 490 */ 491 @Override 492 public String toString(Assignment<V, T> assignment) { 493 double val = getValue(assignment); 494 if (Math.abs(getWeightedValue(assignment)) < 0.005) return ""; 495 double[] bounds = getBounds(assignment); 496 if (bounds[0] <= val && val <= bounds[1] && bounds[0] < bounds[1] && getName().endsWith(" Preferences")) 497 return getAbbreviation() + ":" + getPerc(val, bounds[0], bounds[1]) + "%"; 498 else if (bounds[1] <= val && val <= bounds[0] && bounds[1] < bounds[0] && getName().endsWith(" Preferences")) 499 return getAbbreviation() + ":" + getPercRev(val, bounds[1], bounds[0]) + "%"; 500 else if (bounds[0] != val || val != bounds[1]) 501 return getAbbreviation() + ":" + sDoubleFormat.format(getValue(assignment)); 502 else 503 return ""; 504 } 505 506 public ValueUpdateType getValueUpdateType() { 507 return iValueUpdateType; 508 } 509 510 public void setValueUpdateType(ValueUpdateType iValueUpdateType) { 511 this.iValueUpdateType = iValueUpdateType; 512 } 513}