001package org.cpsolver.ifs.model; 002 003import java.util.ArrayList; 004import java.util.Collection; 005import java.util.Collections; 006import java.util.Comparator; 007import java.util.HashSet; 008import java.util.HashMap; 009import java.util.List; 010import java.util.Locale; 011import java.util.Map; 012import java.util.Set; 013import java.util.TreeSet; 014import java.util.concurrent.locks.ReentrantReadWriteLock; 015 016import org.cpsolver.coursett.criteria.TimetablingCriterion; 017import org.cpsolver.ifs.assignment.Assignment; 018import org.cpsolver.ifs.assignment.DefaultInheritedAssignment; 019import org.cpsolver.ifs.assignment.DefaultSingleAssignment; 020import org.cpsolver.ifs.assignment.EmptyAssignment; 021import org.cpsolver.ifs.assignment.InheritedAssignment; 022import org.cpsolver.ifs.assignment.context.AssignmentContext; 023import org.cpsolver.ifs.assignment.context.AssignmentContextReference; 024import org.cpsolver.ifs.assignment.context.HasAssignmentContext; 025import org.cpsolver.ifs.criteria.Criterion; 026import org.cpsolver.ifs.solution.Solution; 027import org.cpsolver.ifs.solver.Solver; 028import org.cpsolver.ifs.util.ToolBox; 029 030 031/** 032 * Generic model (definition of a problem). <br> 033 * <br> 034 * It consists of variables and constraints. It has also capability of 035 * memorizing the current and the best ever found assignment. <br> 036 * <br> 037 * Example usage:<br> 038 * <pre> 039 * <code> 040 * MyModel model = new MyModel(); 041 * Variable a = new MyVariable("A"); 042 * model.addVariable(a); 043 * Variable b = new MyVariable("B"); 044 * model.addVariable(b); 045 * Variable c = new MyVariable("C"); 046 * model.addVariable(c); 047 * Constraint constr = MyConstraint("all-different"); 048 * model.addConstraint(constr); 049 * constr.addVariable(a); 050 * constr.addVariable(b); 051 * constr.addVariable(c); 052 * solver.setInitialSolution(model); 053 * </code> 054 * </pre> 055 * 056 * @see Variable 057 * @see Constraint 058 * @see org.cpsolver.ifs.solution.Solution 059 * @see org.cpsolver.ifs.solver.Solver 060 * 061 * @version IFS 1.3 (Iterative Forward Search)<br> 062 * Copyright (C) 2006 - 2014 Tomáš Müller<br> 063 * <a href="mailto:muller@unitime.org">muller@unitime.org</a><br> 064 * <a href="http://muller.unitime.org">http://muller.unitime.org</a><br> 065 * <br> 066 * This library is free software; you can redistribute it and/or modify 067 * it under the terms of the GNU Lesser General Public License as 068 * published by the Free Software Foundation; either version 3 of the 069 * License, or (at your option) any later version. <br> 070 * <br> 071 * This library is distributed in the hope that it will be useful, but 072 * WITHOUT ANY WARRANTY; without even the implied warranty of 073 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 074 * Lesser General Public License for more details. <br> 075 * <br> 076 * You should have received a copy of the GNU Lesser General Public 077 * License along with this library; if not see 078 * <a href='http://www.gnu.org/licenses/'>http://www.gnu.org/licenses/</a>. 079 * 080 * @param <V> Variable 081 * @param <T> Value 082 */ 083public class Model<V extends Variable<V, T>, T extends Value<V, T>> { 084 private static org.apache.logging.log4j.Logger sLogger = org.apache.logging.log4j.LogManager.getLogger(Model.class); 085 protected static java.text.DecimalFormat sTimeFormat = new java.text.DecimalFormat("0.00", 086 new java.text.DecimalFormatSymbols(Locale.US)); 087 protected static java.text.DecimalFormat sDoubleFormat = new java.text.DecimalFormat("0.00", 088 new java.text.DecimalFormatSymbols(Locale.US)); 089 protected static java.text.DecimalFormat sPercentageFormat = new java.text.DecimalFormat("0.00", 090 new java.text.DecimalFormatSymbols(Locale.US)); 091 092 private List<V> iVariables = new ArrayList<V>(); 093 private List<Constraint<V, T>> iConstraints = new ArrayList<Constraint<V, T>>(); 094 private List<GlobalConstraint<V, T>> iGlobalConstraints = new ArrayList<GlobalConstraint<V, T>>(); 095 private Collection<V> iVariablesWithInitialValueCache = null; 096 private final ReentrantReadWriteLock iVariablesWithInitialValueLock = new ReentrantReadWriteLock(); 097 098 private List<ModelListener<V, T>> iModelListeners = new ArrayList<ModelListener<V, T>>(); 099 private List<InfoProvider<V, T>> iInfoProviders = new ArrayList<InfoProvider<V, T>>(); 100 private HashMap<String, Criterion<V, T>> iCriteria = new HashMap<String, Criterion<V,T>>(); 101 102 private int iBestUnassignedVariables = -1; 103 private int iBestPerturbations = 0; 104 private double iBestValue = 0.0; 105 private int iNextReferenceId = 0; 106 private int iNextVariableIndex = 0; 107 @Deprecated 108 private Assignment<V, T> iAssignment = null; 109 private Assignment<V, T> iEmptyAssignment = null; 110 private Map<Integer, AssignmentContextReference<V, T, ? extends AssignmentContext>> iAssignmentContextReferences = new HashMap<Integer, AssignmentContextReference<V, T, ? extends AssignmentContext>>(); 111 112 /** Constructor */ 113 public Model() { 114 } 115 116 /** The list of variables in the model 117 * @return list of variables in the model 118 **/ 119 public List<V> variables() { 120 return iVariables; 121 } 122 123 /** The number of variables in the model 124 * @return number of variables in the model 125 **/ 126 public int countVariables() { 127 return iVariables.size(); 128 } 129 130 /** Adds a variable to the model 131 * @param variable a variable 132 **/ 133 @SuppressWarnings("unchecked") 134 public void addVariable(V variable) { 135 variable.setModel(this); 136 variable.setIndex(iNextVariableIndex++); 137 iVariables.add(variable); 138 if (variable instanceof InfoProvider<?, ?>) 139 iInfoProviders.add((InfoProvider<V, T>) variable); 140 for (ModelListener<V, T> listener : iModelListeners) 141 listener.variableAdded(variable); 142 invalidateVariablesWithInitialValueCache(); 143 } 144 145 /** Removes a variable from the model 146 * @param variable a variable 147 **/ 148 @SuppressWarnings("unchecked") 149 public void removeVariable(V variable) { 150 variable.setModel(null); 151 iVariables.remove(variable); 152 if (variable instanceof InfoProvider<?, ?>) 153 iInfoProviders.remove(variable); 154 for (ModelListener<V, T> listener : iModelListeners) 155 listener.variableRemoved(variable); 156 invalidateVariablesWithInitialValueCache(); 157 if (variable instanceof HasAssignmentContext) 158 removeReference((HasAssignmentContext<V, T, ?>)variable); 159 } 160 161 /** The list of constraints in the model 162 * @return list of constraints in the model 163 **/ 164 public List<Constraint<V, T>> constraints() { 165 return iConstraints; 166 } 167 168 /** The number of constraints in the model 169 * @return number of constraints in the model 170 **/ 171 public int countConstraints() { 172 return iConstraints.size(); 173 } 174 175 /** Adds a constraint to the model 176 * @param constraint a constraint 177 **/ 178 @SuppressWarnings("unchecked") 179 public void addConstraint(Constraint<V, T> constraint) { 180 constraint.setModel(this); 181 iConstraints.add(constraint); 182 if (constraint instanceof InfoProvider<?, ?>) 183 iInfoProviders.add((InfoProvider<V, T>) constraint); 184 for (ModelListener<V, T> listener : iModelListeners) 185 listener.constraintAdded(constraint); 186 } 187 188 /** Removes a constraint from the model 189 * @param constraint a constraint 190 **/ 191 @SuppressWarnings("unchecked") 192 public void removeConstraint(Constraint<V, T> constraint) { 193 constraint.setModel(null); 194 iConstraints.remove(constraint); 195 if (constraint instanceof InfoProvider<?, ?>) 196 iInfoProviders.remove(constraint); 197 for (ModelListener<V, T> listener : iModelListeners) 198 listener.constraintRemoved(constraint); 199 if (constraint instanceof HasAssignmentContext) 200 removeReference((HasAssignmentContext<V, T, ?>)constraint); 201 } 202 203 /** The list of global constraints in the model 204 * @return list of global constraints in the model 205 **/ 206 public List<GlobalConstraint<V, T>> globalConstraints() { 207 return iGlobalConstraints; 208 } 209 210 /** The number of global constraints in the model 211 * @return number of global constraints in the model 212 **/ 213 public int countGlobalConstraints() { 214 return iGlobalConstraints.size(); 215 } 216 217 /** Adds a global constraint to the model 218 * @param constraint a global constraint 219 **/ 220 @SuppressWarnings("unchecked") 221 public void addGlobalConstraint(GlobalConstraint<V, T> constraint) { 222 constraint.setModel(this); 223 iGlobalConstraints.add(constraint); 224 if (constraint instanceof InfoProvider<?, ?>) 225 iInfoProviders.add((InfoProvider<V, T>) constraint); 226 for (ModelListener<V, T> listener : iModelListeners) 227 listener.constraintAdded(constraint); 228 if (constraint instanceof ModelListener<?, ?>) 229 iModelListeners.add((ModelListener<V, T>) constraint); 230 } 231 232 /** Removes a global constraint from the model 233 * @param constraint a global constraint 234 **/ 235 @SuppressWarnings("unchecked") 236 public void removeGlobalConstraint(GlobalConstraint<V, T> constraint) { 237 constraint.setModel(null); 238 iGlobalConstraints.remove(constraint); 239 if (constraint instanceof InfoProvider<?, ?>) 240 iInfoProviders.remove((InfoProvider<?, ?>) constraint); 241 if (constraint instanceof ModelListener<?, ?>) 242 iModelListeners.remove((ModelListener<V, T>) constraint); 243 for (ModelListener<V, T> listener : iModelListeners) 244 listener.constraintRemoved(constraint); 245 if (constraint instanceof HasAssignmentContext) 246 removeReference((HasAssignmentContext<V, T, ?>)constraint); 247 } 248 249 /** 250 * The list of unassigned variables in the model. 251 * Use {@link Model#unassignedVariables(Assignment)} or {@link Assignment#unassignedVariables(Model)} instead. 252 * @return list of unassigned variables in the model 253 **/ 254 @Deprecated 255 public Collection<V> unassignedVariables() { 256 return unassignedVariables(getDefaultAssignment()); 257 } 258 259 /** The list of unassigned variables in the model 260 * @param assignment current assignment 261 * @return list of unassigned variables in the model 262 **/ 263 public Collection<V> unassignedVariables(Assignment<V, T> assignment) { 264 return assignment.unassignedVariables(this); 265 } 266 267 /** 268 * Number of unassigned variables. 269 * Use {@link Model#nrUnassignedVariables(Assignment)} or {@link Assignment#nrUnassignedVariables(Model)} instead. 270 * @return number of unassigned variables in the model 271 **/ 272 @Deprecated 273 public int nrUnassignedVariables() { 274 return nrUnassignedVariables(getDefaultAssignment()); 275 } 276 277 /** Number of unassigned variables 278 * @param assignment current assignment 279 * @return number of unassigned variables in the model 280 **/ 281 public int nrUnassignedVariables(Assignment<V, T> assignment) { 282 return assignment.nrUnassignedVariables(this); 283 } 284 285 /** 286 * The list of assigned variables in the model. 287 * Use {@link Model#assignedVariables(Assignment)} or {@link Assignment#assignedVariables()} instead. 288 * @return list of assigned variables in the model 289 **/ 290 @Deprecated 291 public Collection<V> assignedVariables() { 292 return assignedVariables(getDefaultAssignment()); 293 } 294 295 /** The list of assigned variables in the model 296 * @param assignment current assignment 297 * @return list of assigned variables in the model 298 **/ 299 public Collection<V> assignedVariables(Assignment<V, T> assignment) { 300 return assignment.assignedVariables(); 301 } 302 303 /** 304 * Number of assigned variables. 305 * Use {@link Model#nrAssignedVariables(Assignment)} or {@link Assignment#nrAssignedVariables()} instead. 306 * @return number of assigned variables in the model 307 **/ 308 @Deprecated 309 public int nrAssignedVariables() { 310 return nrAssignedVariables(getDefaultAssignment()); 311 } 312 313 /** Number of assigned variables 314 * @param assignment current assignment 315 * @return number of assigned variables in the model 316 **/ 317 public int nrAssignedVariables(Assignment<V, T> assignment) { 318 return assignment.nrAssignedVariables(); 319 } 320 321 /** 322 * The list of perturbation variables in the model, i.e., the variables 323 * which has an initial value but which are not assigned with this value. 324 * Use {@link Model#perturbVariables(Assignment)} instead. 325 * @return list of perturbation variables in the model 326 */ 327 @Deprecated 328 public Collection<V> perturbVariables() { 329 return perturbVariables(getDefaultAssignment(), variablesWithInitialValue()); 330 } 331 332 /** 333 * The list of perturbation variables in the model, i.e., the variables 334 * which has an initial value but which are not assigned with this value. 335 * @param assignment current assignment 336 * @return list of perturbation variables in the model 337 */ 338 public Collection<V> perturbVariables(Assignment<V, T> assignment) { 339 return perturbVariables(assignment, variablesWithInitialValue()); 340 } 341 342 /** 343 * The list of perturbation variables in the model, i.e., the variables 344 * which has an initial value but which are not assigned with this value. 345 * Only variables from the given set are considered. 346 * Use {@link Model#perturbVariables(Assignment, Collection)} instead. 347 * @param variables sub-problem 348 * @return list of perturbation variables in the sub-problem 349 */ 350 @Deprecated 351 public List<V> perturbVariables(Collection<V> variables) { 352 return perturbVariables(getDefaultAssignment(), variables); 353 } 354 355 /** 356 * The list of perturbation variables in the model, i.e., the variables 357 * which has an initial value but which are not assigned with this value. 358 * Only variables from the given set are considered. 359 * @param assignment current assignment 360 * @param variables sub-problem 361 * @return list of perturbation variables in the sub-problem 362 */ 363 public List<V> perturbVariables(Assignment<V, T> assignment, Collection<V> variables) { 364 List<V> perturbances = new ArrayList<V>(); 365 for (V variable : variables) { 366 if (variable.getInitialAssignment() == null) 367 continue; 368 T value = assignment.getValue(variable); 369 if (value != null) { 370 if (!variable.getInitialAssignment().equals(value)) 371 perturbances.add(variable); 372 } else { 373 boolean hasPerturbance = false; 374 for (Constraint<V, T> constraint : variable.hardConstraints()) { 375 if (constraint.inConflict(assignment, variable.getInitialAssignment())) { 376 hasPerturbance = true; 377 break; 378 } 379 } 380 if (!hasPerturbance) 381 for (GlobalConstraint<V, T> constraint : globalConstraints()) { 382 if (constraint.inConflict(assignment, variable.getInitialAssignment())) { 383 hasPerturbance = true; 384 break; 385 } 386 } 387 if (hasPerturbance) 388 perturbances.add(variable); 389 } 390 } 391 return perturbances; 392 } 393 394 /** 395 * Returns the set of conflicting variables with this value, if it is 396 * assigned to its variable 397 * Use {@link Model#conflictValues(Assignment, Value)} instead. 398 * @param value a value to be assigned 399 * @return a set of conflicting values, i.e., values that would have to be unassigned if the given value is assigned to its variable 400 */ 401 @Deprecated 402 public Set<T> conflictValues(T value) { 403 return conflictValues(getDefaultAssignment(), value); 404 } 405 406 /** 407 * Returns the set of conflicting variables with this value, if it is 408 * assigned to its variable 409 * @param assignment current assignment 410 * @param value a value to be assigned 411 * @return a set of conflicting values, i.e., values that would have to be unassigned if the given value is assigned to its variable 412 */ 413 public Set<T> conflictValues(Assignment<V, T> assignment, T value) { 414 Set<T> conflictValues = new HashSet<T>(); 415 for (Constraint<V, T> constraint : value.variable().hardConstraints()) 416 constraint.computeConflicts(assignment, value, conflictValues); 417 for (GlobalConstraint<V, T> constraint : globalConstraints()) 418 constraint.computeConflicts(assignment, value, conflictValues); 419 return conflictValues; 420 } 421 422 /** 423 * Return true if the given value is in conflict with a hard constraint 424 * Use {@link Model#inConflict(Assignment, Value)} instead. 425 * @param value a value in question 426 * @return true if there is a conflict, i.e., there is at least one value that would have to be unassigned if the given value is assigned to its variable 427 **/ 428 @Deprecated 429 public boolean inConflict(T value) { 430 return inConflict(getDefaultAssignment(), value); 431 } 432 433 /** Return true if the given value is in conflict with a hard constraint 434 * @param assignment current assignment 435 * @param value a value in question 436 * @return true if there is a conflict, i.e., there is at least one value that would have to be unassigned if the given value is assigned to its variable 437 **/ 438 public boolean inConflict(Assignment<V, T> assignment, T value) { 439 for (Constraint<V, T> constraint : value.variable().hardConstraints()) 440 if (constraint.inConflict(assignment, value)) 441 return true; 442 for (GlobalConstraint<V, T> constraint : globalConstraints()) 443 if (constraint.inConflict(assignment, value)) 444 return true; 445 return false; 446 } 447 448 /** The list of variables with an initial value (i.e., variables with {@link Variable#getInitialAssignment()} not null) 449 * @return list of variables with an initial value 450 **/ 451 public Collection<V> variablesWithInitialValue() { 452 iVariablesWithInitialValueLock.readLock().lock(); 453 try { 454 if (iVariablesWithInitialValueCache != null) 455 return iVariablesWithInitialValueCache; 456 } finally { 457 iVariablesWithInitialValueLock.readLock().unlock(); 458 } 459 iVariablesWithInitialValueLock.writeLock().lock(); 460 try { 461 if (iVariablesWithInitialValueCache != null) 462 return iVariablesWithInitialValueCache; 463 iVariablesWithInitialValueCache = new ArrayList<V>(); 464 for (V variable : iVariables) { 465 if (variable.getInitialAssignment() != null) 466 iVariablesWithInitialValueCache.add(variable); 467 } 468 return iVariablesWithInitialValueCache; 469 } finally { 470 iVariablesWithInitialValueLock.writeLock().unlock(); 471 } 472 } 473 474 /** Invalidates cache containing all variables that possess an initial value */ 475 protected void invalidateVariablesWithInitialValueCache() { 476 iVariablesWithInitialValueLock.writeLock().lock(); 477 iVariablesWithInitialValueCache = null; 478 iVariablesWithInitialValueLock.writeLock().unlock(); 479 } 480 481 /** Called before a value is assigned to its variable 482 * @param iteration current iteration 483 * @param value a value to be assigned 484 **/ 485 @Deprecated 486 public void beforeAssigned(long iteration, T value) { 487 } 488 489 /** Called before a value is assigned to its variable 490 * @param assignment current assignment 491 * @param iteration current iteration 492 * @param value a value to be assigned 493 **/ 494 public void beforeAssigned(Assignment<V, T> assignment, long iteration, T value) { 495 beforeAssigned(iteration, value); 496 for (ModelListener<V, T> listener : iModelListeners) 497 listener.beforeAssigned(assignment, iteration, value); 498 } 499 500 /** Called before a value is unassigned from its variable 501 * @param iteration current iteration 502 * @param value a value to be unassigned 503 **/ 504 @Deprecated 505 public void beforeUnassigned(long iteration, T value) { 506 } 507 508 /** Called before a value is unassigned from its variable 509 * @param assignment current assignment 510 * @param iteration current iteration 511 * @param value a value to be unassigned 512 **/ 513 public void beforeUnassigned(Assignment<V, T> assignment, long iteration, T value) { 514 beforeUnassigned(iteration, value); 515 for (ModelListener<V, T> listener : iModelListeners) 516 listener.beforeUnassigned(assignment, iteration, value); 517 } 518 519 /** Called after a value is assigned to its variable 520 * @param iteration current iteration 521 * @param value a value that was assigned 522 **/ 523 @Deprecated 524 public void afterAssigned(long iteration, T value) { 525 } 526 527 /** Called after a value is assigned to its variable 528 * @param assignment current assignment 529 * @param iteration current iteration 530 * @param value a value that was assigned 531 **/ 532 public void afterAssigned(Assignment<V, T> assignment, long iteration, T value) { 533 afterAssigned(iteration, value); 534 for (ModelListener<V, T> listener : iModelListeners) 535 listener.afterAssigned(assignment, iteration, value); 536 } 537 538 /** Called after a value is unassigned from its variable 539 * @param iteration current iteration 540 * @param value a value that was unassigned 541 **/ 542 @Deprecated 543 public void afterUnassigned(long iteration, T value) { 544 } 545 546 /** Called after a value is unassigned from its variable 547 * @param assignment current assignment 548 * @param iteration current iteration 549 * @param value a value that was unassigned 550 **/ 551 public void afterUnassigned(Assignment<V, T> assignment, long iteration, T value) { 552 afterUnassigned(iteration, value); 553 for (ModelListener<V, T> listener : iModelListeners) 554 listener.afterUnassigned(assignment, iteration, value); 555 } 556 557 @Override 558 public String toString() { 559 return "Model{\n variables=" + ToolBox.col2string(variables(), 2) + ",\n constraints=" + ToolBox.col2string(constraints(), 2) + ",\n }"; 560 } 561 562 /** 563 * String representation -- returns a list of values of objective criteria 564 * @param assignment current assignment 565 * @return comma separated string of {@link TimetablingCriterion#toString(Assignment)} 566 */ 567 public String toString(Assignment<V, T> assignment) { 568 List<Criterion<V, T>> criteria = new ArrayList<Criterion<V,T>>(getCriteria()); 569 Collections.sort(criteria, new Comparator<Criterion<V, T>>() { 570 @Override 571 public int compare(Criterion<V, T> c1, Criterion<V, T> c2) { 572 int cmp = -Double.compare(c1.getWeight(), c2.getWeight()); 573 if (cmp != 0) return cmp; 574 return c1.getName().compareTo(c2.getName()); 575 } 576 }); 577 String ret = ""; 578 for (Criterion<V, T> criterion: criteria) { 579 String val = criterion.toString(assignment); 580 if (val != null && !val.isEmpty()) 581 ret += ", " + val; 582 } 583 return (nrUnassignedVariables(assignment) == 0 ? "" : "V:" + nrAssignedVariables(assignment) + "/" + variables().size() + ", ") + "T:" + sDoubleFormat.format(getTotalValue(assignment)) + ret; 584 } 585 586 protected String getPerc(double value, double min, double max) { 587 if (max == min) 588 return sPercentageFormat.format(100.0); 589 return sPercentageFormat.format(100.0 - 100.0 * (value - min) / (max - min)); 590 } 591 592 protected String getPercRev(double value, double min, double max) { 593 if (max == min) 594 return sPercentageFormat.format(0.0); 595 return sPercentageFormat.format(100.0 * (value - min) / (max - min)); 596 } 597 598 /** 599 * Returns information about the current solution. Information from all 600 * model listeners and constraints is also included. 601 * Use {@link Model#getInfo(Assignment)} instead. 602 * @return info table 603 */ 604 @Deprecated 605 public Map<String, String> getInfo() { 606 return getInfo(getDefaultAssignment()); 607 } 608 609 /** 610 * Returns information about the current solution. Information from all 611 * model listeners and constraints is also included. 612 * @param assignment current assignment 613 * @return info table 614 */ 615 public Map<String, String> getInfo(Assignment<V, T> assignment) { 616 Map<String, String> ret = new HashMap<String, String>(); 617 ret.put("Assigned variables", getPercRev(assignment.nrAssignedVariables(), 0, variables().size()) + "% (" + assignment.nrAssignedVariables() + "/" + variables().size() + ")"); 618 int nrVarsWithInitialValue = variablesWithInitialValue().size(); 619 if (nrVarsWithInitialValue > 0) { 620 Collection<V> pv = perturbVariables(assignment); 621 ret.put("Perturbation variables", getPercRev(pv.size(), 0, nrVarsWithInitialValue) + "% (" + pv.size() + " + " + (variables().size() - nrVarsWithInitialValue) + ")"); 622 } 623 ret.put("Overall solution value", sDoubleFormat.format(getTotalValue(assignment))); 624 for (InfoProvider<V, T> provider : iInfoProviders) 625 provider.getInfo(assignment, ret); 626 return ret; 627 } 628 629 /** 630 * Extended information about current solution. Similar to 631 * {@link Model#getInfo(Assignment)}, but some more information (that is more 632 * expensive to compute) might be added. 633 * Use {@link Model#getExtendedInfo(Assignment)} instead. 634 * @return extended info table 635 */ 636 @Deprecated 637 public Map<String, String> getExtendedInfo() { 638 return getExtendedInfo(getDefaultAssignment()); 639 } 640 641 /** 642 * Extended information about current solution. Similar to 643 * {@link Model#getInfo(Assignment)}, but some more information (that is more 644 * expensive to compute) might be added. 645 * @param assignment current assignment 646 * @return extended info table 647 */ 648 public Map<String, String> getExtendedInfo(Assignment<V, T> assignment) { 649 Map<String, String> ret = getInfo(assignment); 650 for (InfoProvider<V, T> provider : iInfoProviders) 651 if (provider instanceof ExtendedInfoProvider) 652 ((ExtendedInfoProvider<V, T>)provider).getExtendedInfo(assignment, ret); 653 return ret; 654 } 655 656 /** 657 * Returns information about the current solution. Information from all 658 * model listeners and constraints is also included. Only variables from the 659 * given set are considered. 660 * Use {@link Model#getInfo(Assignment, Collection)} instead. 661 * @param variables sub-problem 662 * @return info table 663 **/ 664 @Deprecated 665 public Map<String, String> getInfo(Collection<V> variables) { 666 return getInfo(getDefaultAssignment(), variables); 667 } 668 669 /** 670 * Returns information about the current solution. Information from all 671 * model listeners and constraints is also included. Only variables from the 672 * given set are considered. 673 * @param assignment current assignment 674 * @param variables sub-problem 675 * @return info table 676 */ 677 public Map<String, String> getInfo(Assignment<V, T> assignment, Collection<V> variables) { 678 Map<String, String> ret = new HashMap<String, String>(); 679 int assigned = 0, perturb = 0, nrVarsWithInitialValue = 0; 680 for (V variable : variables) { 681 T value = assignment.getValue(variable); 682 if (value != null) 683 assigned++; 684 if (variable.getInitialAssignment() != null) { 685 nrVarsWithInitialValue++; 686 if (value != null) { 687 if (!variable.getInitialAssignment().equals(value)) 688 perturb++; 689 } else { 690 boolean hasPerturbance = false; 691 for (Constraint<V, T> constraint : variable.hardConstraints()) { 692 if (constraint.inConflict(assignment, variable.getInitialAssignment())) { 693 hasPerturbance = true; 694 break; 695 } 696 } 697 if (!hasPerturbance) 698 for (GlobalConstraint<V, T> constraint : globalConstraints()) { 699 if (constraint.inConflict(assignment, variable.getInitialAssignment())) { 700 hasPerturbance = true; 701 break; 702 } 703 } 704 if (hasPerturbance) 705 perturb++; 706 } 707 } 708 } 709 ret.put("Assigned variables", getPercRev(assigned, 0, variables.size()) + "% (" + assigned + "/" + variables.size() + ")"); 710 if (nrVarsWithInitialValue > 0) { 711 ret.put("Perturbation variables", getPercRev(perturb, 0, nrVarsWithInitialValue) + "% (" + perturb + " + " + (variables.size() - nrVarsWithInitialValue) + ")"); 712 } 713 ret.put("Overall solution value", sDoubleFormat.format(getTotalValue(assignment, variables))); 714 for (InfoProvider<V, T> provider : iInfoProviders) 715 provider.getInfo(assignment, ret, variables); 716 return ret; 717 } 718 719 /** 720 * Returns the number of unassigned variables in the best ever found 721 * solution 722 * @return number of unassigned variables in the best solution 723 */ 724 public int getBestUnassignedVariables() { 725 return iBestUnassignedVariables; 726 } 727 728 /** 729 * Returns the number of perturbation variables in the best ever found 730 * solution 731 * @return number of perturbation variables in the best solution 732 */ 733 public int getBestPerturbations() { 734 return iBestPerturbations; 735 } 736 737 /** 738 * Total value of the best ever found solution -- sum of all assigned values 739 * (see {@link Value#toDouble(Assignment)}). 740 * @return value of the best solution 741 */ 742 public double getBestValue() { 743 return iBestValue; 744 } 745 746 /** Set total value of the best ever found solution 747 * @param bestValue value of the best solution 748 **/ 749 public void setBestValue(double bestValue) { 750 iBestValue = bestValue; 751 } 752 753 /** 754 * Save the current assignment as the best ever found assignment 755 * Use {@link Model#saveBest(Assignment)} instead. 756 **/ 757 @Deprecated 758 public void saveBest() { 759 saveBest(getDefaultAssignment()); 760 } 761 762 /** Save the current assignment as the best ever found assignment 763 * @param assignment current assignment 764 **/ 765 public void saveBest(Assignment<V, T> assignment) { 766 iBestUnassignedVariables = iVariables.size() - assignment.nrAssignedVariables(); 767 iBestPerturbations = perturbVariables(assignment).size(); 768 iBestValue = getTotalValue(assignment); 769 for (V variable : iVariables) { 770 variable.setBestAssignment(assignment.getValue(variable), assignment.getIteration(variable)); 771 } 772 for (Criterion<V, T> criterion: getCriteria()) { 773 criterion.bestSaved(assignment); 774 } 775 } 776 777 /** Clear the best ever found assignment */ 778 public void clearBest() { 779 iBestUnassignedVariables = -1; 780 iBestPerturbations = 0; 781 iBestValue = 0; 782 for (V variable : iVariables) { 783 variable.setBestAssignment(null, 0); 784 } 785 } 786 787 /** 788 * Restore the best ever found assignment into the current assignment 789 * Use {@link Model#restoreBest(Assignment)} instead. 790 **/ 791 @Deprecated 792 protected void restoreBest() { 793 restoreBest(getDefaultAssignment()); 794 } 795 796 /** Restore the best ever found assignment into the current assignment 797 * @param assignment current assignment 798 * @param assignmentOrder assignment order of the variables 799 **/ 800 @SuppressWarnings("unchecked") 801 protected void restoreBest(Assignment<V, T> assignment, Comparator<V> assignmentOrder) { 802 TreeSet<V> sortedVariables = new TreeSet<V>(assignmentOrder); 803 for (V variable : iVariables) { 804 T value = assignment.getValue(variable); 805 if (value == null) { 806 if (variable.getBestAssignment() != null) 807 sortedVariables.add(variable); 808 } else if (!value.equals(variable.getBestAssignment())) { 809 assignment.unassign(0, variable); 810 if (variable.getBestAssignment() != null) 811 sortedVariables.add(variable); 812 } 813 } 814 Set<T> problems = new HashSet<T>(); 815 for (V variable : sortedVariables) { 816 Set<T> confs = conflictValues(assignment, variable.getBestAssignment()); 817 if (!confs.isEmpty()) { 818 sLogger.error("restore best problem: assignment " + variable.getName() + " = " + variable.getBestAssignment().getName()); 819 boolean weakened = false; 820 for (Constraint<V, T> c : variable.hardConstraints()) { 821 Set<T> x = new HashSet<T>(); 822 c.computeConflicts(assignment, variable.getBestAssignment(), x); 823 if (!x.isEmpty()) { 824 if (c instanceof WeakeningConstraint) { 825 ((WeakeningConstraint<V, T>)c).weaken(assignment, variable.getBestAssignment()); 826 sLogger.info(" constraint " + c.getClass().getSimpleName() + " " + c.getName() + " had to be weakened"); 827 weakened = true; 828 } else { 829 sLogger.error(" constraint " + c.getClass().getSimpleName() + " " + c.getName() + " causes the following conflicts " + x); 830 } 831 } 832 } 833 for (GlobalConstraint<V, T> c : globalConstraints()) { 834 Set<T> x = new HashSet<T>(); 835 c.computeConflicts(assignment, variable.getBestAssignment(), x); 836 if (!x.isEmpty()) { 837 if (c instanceof WeakeningConstraint) { 838 ((WeakeningConstraint<V, T>)c).weaken(assignment, variable.getBestAssignment()); 839 sLogger.info(" constraint " + c.getClass().getSimpleName() + " " + c.getName() + " had to be weakened"); 840 weakened = true; 841 } else { 842 sLogger.error(" global constraint " + c.getClass().getSimpleName() + " " + c.getName() + " causes the following conflicts " + x); 843 } 844 } 845 } 846 if (weakened && conflictValues(assignment, variable.getBestAssignment()).isEmpty()) 847 assignment.assign(0, variable.getBestAssignment()); 848 else 849 problems.add(variable.getBestAssignment()); 850 } else 851 assignment.assign(0, variable.getBestAssignment()); 852 } 853 int attempt = 0, maxAttempts = 3 * problems.size(); 854 while (!problems.isEmpty() && attempt <= maxAttempts) { 855 attempt++; 856 T value = ToolBox.random(problems); 857 problems.remove(value); 858 V variable = value.variable(); 859 Set<T> confs = conflictValues(assignment, value); 860 if (!confs.isEmpty()) { 861 sLogger.error("restore best problem (again, att=" + attempt + "): assignment " + variable.getName() + " = " + value.getName()); 862 for (Constraint<V, T> c : variable.hardConstraints()) { 863 Set<T> x = new HashSet<T>(); 864 c.computeConflicts(assignment, value, x); 865 if (!x.isEmpty()) 866 sLogger.error(" constraint " + c.getClass().getSimpleName() + " " + c.getName() + " causes the following conflicts " + x); 867 } 868 for (GlobalConstraint<V, T> c : globalConstraints()) { 869 Set<T> x = new HashSet<T>(); 870 c.computeConflicts(assignment, value, x); 871 if (!x.isEmpty()) 872 sLogger.error(" constraint " + c.getClass().getSimpleName() + " " + c.getName() + " causes the following conflicts " + x); 873 } 874 for (T conf : confs) 875 assignment.unassign(0, conf.variable()); 876 problems.addAll(confs); 877 } 878 assignment.assign(0, value); 879 } 880 for (Criterion<V, T> criterion: getCriteria()) { 881 criterion.bestRestored(assignment); 882 } 883 } 884 885 /** Restore the best ever found assignment into the current assignment 886 * @param assignment current assignment 887 **/ 888 public void restoreBest(Assignment<V, T> assignment) { 889 restoreBest(assignment, new Comparator<V>() { 890 @Override 891 public int compare(V v1, V v2) { 892 if (v1.getBestAssignmentIteration() < v2.getBestAssignmentIteration()) return -1; 893 if (v1.getBestAssignmentIteration() > v2.getBestAssignmentIteration()) return 1; 894 return v1.compareTo(v2); 895 } 896 }); 897 } 898 899 /** 900 * The list of unassigned variables in the best ever found solution. 901 * Use {@link Model#bestUnassignedVariables(Assignment)} instead. 902 * @return variables list of unassigned variables in the best solution 903 **/ 904 @Deprecated 905 public Collection<V> bestUnassignedVariables() { 906 return bestUnassignedVariables(getDefaultAssignment()); 907 } 908 909 /** The list of unassigned variables in the best ever found solution 910 * @param assignment current assignment 911 * @return variables list of unassigned variables in the best solution 912 **/ 913 public Collection<V> bestUnassignedVariables(Assignment<V, T> assignment) { 914 Collection<V> ret = new ArrayList<V>(variables().size()); 915 if (iBestUnassignedVariables < 0) { 916 for (V variable : variables()) { 917 if (assignment.getValue(variable) == null) 918 ret.add(variable); 919 } 920 } else { 921 for (V variable : variables()) { 922 if (variable.getBestAssignment() == null) 923 ret.add(variable); 924 } 925 } 926 return ret; 927 } 928 929 /** 930 * Value of the current solution. It is the sum of all assigned values, 931 * i.e., {@link Value#toDouble(Assignment)}. 932 * Use {@link Model#getTotalValue(Assignment)} instead. 933 * @return solution value 934 */ 935 @Deprecated 936 public double getTotalValue() { 937 return getTotalValue(getDefaultAssignment()); 938 } 939 940 /** 941 * Value of the current solution. It is the sum of all assigned values, 942 * i.e., {@link Value#toDouble(Assignment)}. 943 * @param assignment current assignment 944 * @return solution value 945 */ 946 public double getTotalValue(Assignment<V, T> assignment) { 947 double ret = 0.0; 948 if (getCriteria().isEmpty()) 949 for (T t: assignment.assignedValues()) 950 ret += t.toDouble(assignment); 951 else 952 for (Criterion<V, T> c: getCriteria()) 953 ret += c.getWeightedValue(assignment); 954 return ret; 955 } 956 957 /** 958 * Value of the current solution. It is the sum of all assigned values, 959 * i.e., {@link Value#toDouble(Assignment)}. Only variables from the given set are 960 * considered. 961 * Use {@link Model#getTotalValue(Assignment, Collection)} instead. 962 * @param variables sub-problem 963 * @return solution value 964 **/ 965 @Deprecated 966 public double getTotalValue(Collection<V> variables) { 967 return getTotalValue(getDefaultAssignment(), variables); 968 } 969 970 /** 971 * Value of the current solution. It is the sum of all assigned values, 972 * i.e., {@link Value#toDouble(Assignment)}. Only variables from the given set are 973 * considered. 974 * @param assignment current assignment 975 * @param variables sub-problem 976 * @return solution value 977 **/ 978 public double getTotalValue(Assignment<V, T> assignment, Collection<V> variables) { 979 double ret = 0.0; 980 for (V v: variables) { 981 T t = assignment.getValue(v); 982 if (t != null) 983 ret += t.toDouble(assignment); 984 } 985 return ret; 986 } 987 988 /** Adds a model listener 989 * @param listener a model listener 990 **/ 991 @SuppressWarnings("unchecked") 992 public void addModelListener(ModelListener<V, T> listener) { 993 iModelListeners.add(listener); 994 if (listener instanceof InfoProvider<?, ?>) 995 iInfoProviders.add((InfoProvider<V, T>) listener); 996 for (Constraint<V, T> constraint : iConstraints) 997 listener.constraintAdded(constraint); 998 for (Constraint<V, T> constraint : iGlobalConstraints) 999 listener.constraintAdded(constraint); 1000 for (V variable : iVariables) 1001 listener.variableAdded(variable); 1002 } 1003 1004 /** Removes a model listener 1005 * @param listener a model listener 1006 **/ 1007 public void removeModelListener(ModelListener<V, T> listener) { 1008 if (listener instanceof InfoProvider<?, ?>) 1009 iInfoProviders.remove(listener); 1010 for (V variable : iVariables) 1011 listener.variableRemoved(variable); 1012 for (Constraint<V, T> constraint : iConstraints) 1013 listener.constraintRemoved(constraint); 1014 for (Constraint<V, T> constraint : iGlobalConstraints) 1015 listener.constraintRemoved(constraint); 1016 iModelListeners.remove(listener); 1017 } 1018 1019 /** Model initialization 1020 * @param solver current solver 1021 * @return true if successfully initialized 1022 **/ 1023 public boolean init(Solver<V, T> solver) { 1024 for (ModelListener<V, T> listener : new ArrayList<ModelListener<V, T>>(iModelListeners)) { 1025 if (!listener.init(solver)) 1026 return false; 1027 } 1028 return true; 1029 } 1030 1031 /** The list of model listeners 1032 * @return list of model listeners 1033 **/ 1034 public List<ModelListener<V, T>> getModelListeners() { 1035 return iModelListeners; 1036 } 1037 1038 /** The list of model listeners that are of the given class 1039 * @param type model listener type 1040 * @return list of model listeners that are of the given class 1041 **/ 1042 public ModelListener<V, T> modelListenerOfType(Class<ModelListener<V, T>> type) { 1043 for (ModelListener<V, T> listener : iModelListeners) { 1044 if (listener.getClass() == type) 1045 return listener; 1046 } 1047 return null; 1048 } 1049 1050 /** 1051 * The list of constraints which are in a conflict with the given value if 1052 * it is assigned to its variable. This means the constraints, which adds a 1053 * value into the set of conflicting values in 1054 * {@link Constraint#computeConflicts(Assignment, Value, Set)}. 1055 * @param assignment current assignment 1056 * @param value given value 1057 * @return hard constraints and their conflicts that are conflicting with the given value 1058 */ 1059 public Map<Constraint<V, T>, Set<T>> conflictConstraints(Assignment<V, T> assignment, T value) { 1060 Map<Constraint<V, T>, Set<T>> conflictConstraints = new HashMap<Constraint<V, T>, Set<T>>(); 1061 for (Constraint<V, T> constraint : value.variable().hardConstraints()) { 1062 Set<T> conflicts = new HashSet<T>(); 1063 constraint.computeConflicts(assignment, value, conflicts); 1064 if (!conflicts.isEmpty()) { 1065 conflictConstraints.put(constraint, conflicts); 1066 } 1067 } 1068 for (GlobalConstraint<V, T> constraint : globalConstraints()) { 1069 Set<T> conflicts = new HashSet<T>(); 1070 constraint.computeConflicts(assignment, value, conflicts); 1071 if (!conflicts.isEmpty()) { 1072 conflictConstraints.put(constraint, conflicts); 1073 } 1074 } 1075 return conflictConstraints; 1076 } 1077 1078 /** 1079 * The list of hard constraints which contain at least one variable that is 1080 * not assigned. 1081 * @param assignment current assignment 1082 * @return list of hard constraints which contain at least one variable that is not assigned 1083 */ 1084 public List<Constraint<V, T>> unassignedHardConstraints(Assignment<V, T> assignment) { 1085 List<Constraint<V, T>> ret = new ArrayList<Constraint<V, T>>(); 1086 constraints: for (Constraint<V, T> constraint : constraints()) { 1087 if (!constraint.isHard()) 1088 continue; 1089 for (V v : constraint.variables()) { 1090 if (assignment.getValue(v) == null) { 1091 ret.add(constraint); 1092 continue constraints; 1093 } 1094 } 1095 } 1096 if (iVariables.size() > assignment.nrAssignedVariables()) 1097 ret.addAll(globalConstraints()); 1098 return ret; 1099 } 1100 1101 /** Registered info providers (see {@link InfoProvider}) 1102 * @return list of registered info providers 1103 **/ 1104 protected List<InfoProvider<V, T>> getInfoProviders() { 1105 return iInfoProviders; 1106 } 1107 1108 /** Register a new criterion 1109 * @param criterion a criterion 1110 **/ 1111 public void addCriterion(Criterion<V,T> criterion) { 1112 iCriteria.put(criterion.getClass().getName(), criterion); 1113 criterion.setModel(this); 1114 addModelListener(criterion); 1115 } 1116 1117 /** Unregister an existing criterion 1118 * @param criterion a criterion 1119 **/ 1120 public void removeCriterion(Criterion<V,T> criterion) { 1121 iCriteria.remove(criterion.getClass().getName()); 1122 criterion.setModel(null); 1123 removeModelListener(criterion); 1124 } 1125 1126 /** Unregister an existing criterion 1127 * @param criterion a criterion 1128 **/ 1129 public void removeCriterion(Class<? extends Criterion<V, T>> criterion) { 1130 Criterion<V,T> c = iCriteria.remove(criterion.getName()); 1131 if (c != null) 1132 removeModelListener(c); 1133 } 1134 1135 /** Return a registered criterion of the given type. 1136 * @param criterion criterion type 1137 * @return registered criterion of the given type 1138 **/ 1139 public Criterion<V, T> getCriterion(Class<? extends Criterion<V, T>> criterion) { 1140 return iCriteria.get(criterion.getName()); 1141 } 1142 1143 /** List all registered criteria 1144 * @return list all registered criteria 1145 **/ 1146 public Collection<Criterion<V, T>> getCriteria() { 1147 return iCriteria.values(); 1148 } 1149 1150 /** 1151 * Weaken all weakening constraint so that the given value can be assigned without 1152 * them creating a conflict using {@link WeakeningConstraint#weaken(Assignment, Value)}. 1153 * This method is handy for instance when an existing solution is being loaded 1154 * into the solver. 1155 * @param assignment current assignment 1156 * @param value given value 1157 */ 1158 @SuppressWarnings("unchecked") 1159 public void weaken(Assignment<V, T> assignment, T value) { 1160 for (Constraint<V, T> constraint : value.variable().hardConstraints()) { 1161 if (constraint instanceof WeakeningConstraint) 1162 ((WeakeningConstraint<V,T>)constraint).weaken(assignment, value); 1163 } 1164 for (GlobalConstraint<V, T> constraint : globalConstraints()) { 1165 if (constraint instanceof WeakeningConstraint) 1166 ((WeakeningConstraint<V,T>)constraint).weaken(assignment, value); 1167 } 1168 } 1169 1170 /** 1171 * Create a reference to an assignment context for a class that is in a need of one. Through this 1172 * reference an assignment context (see {@link AssignmentContext}) can be accessed using 1173 * {@link Assignment#getAssignmentContext(AssignmentContextReference)}. 1174 * @param parent class needing an assignment context 1175 * @param <C> assignment context type 1176 * @return reference to an assignment context 1177 */ 1178 public synchronized <C extends AssignmentContext> AssignmentContextReference<V,T,C> createReference(HasAssignmentContext<V, T, C> parent) { 1179 AssignmentContextReference<V, T, C> ref = new AssignmentContextReference<V, T, C>(parent, iNextReferenceId); 1180 iAssignmentContextReferences.put(iNextReferenceId, ref); 1181 iNextReferenceId++; 1182 return ref; 1183 } 1184 1185 /** 1186 * Clear all assignment contexts for the given assignment 1187 * @param assignment given {@link Assignment} 1188 */ 1189 public synchronized void clearAssignmentContexts(Assignment<V, T> assignment) { 1190 for (AssignmentContextReference<V,T,? extends AssignmentContext> ref: iAssignmentContextReferences.values()) 1191 assignment.clearContext(ref); 1192 } 1193 1194 /** 1195 * Remove a reference to an assignment context for the model 1196 * @param parent class with an assignment context 1197 * @param <C> assignment context type 1198 * @return reference to an assignment context that was removed from the model (if any) 1199 */ 1200 @SuppressWarnings("unchecked") 1201 public synchronized <C extends AssignmentContext> AssignmentContextReference<V,T,C> removeReference(HasAssignmentContext<V, T, C> parent) { 1202 AssignmentContextReference<V,T,C> reference = parent.getAssignmentContextReference(); 1203 if (reference != null) 1204 return (AssignmentContextReference<V,T,C>) iAssignmentContextReferences.remove(reference.getIndex()); 1205 return null; 1206 } 1207 1208 /** 1209 * Create all assignment contexts for the given assignment 1210 * @param assignment given {@link Assignment} 1211 * @param clear if true {@link Assignment#clearContext(AssignmentContextReference)} is called first 1212 */ 1213 public synchronized void createAssignmentContexts(Assignment<V, T> assignment, boolean clear) { 1214 for (AssignmentContextReference<V,T,? extends AssignmentContext> ref: iAssignmentContextReferences.values()) { 1215 if (clear) assignment.clearContext(ref); 1216 assignment.getAssignmentContext(ref); 1217 } 1218 } 1219 1220 /** 1221 * Return default assignment that is using the old {@link Variable#getAssignment()} assignments. 1222 * @return as instance of {@link DefaultSingleAssignment} 1223 */ 1224 @Deprecated 1225 public Assignment<V, T> getDefaultAssignment() { 1226 if (iAssignment == null) 1227 iAssignment = new DefaultSingleAssignment<V, T>(); 1228 return iAssignment; 1229 } 1230 1231 /** 1232 * Set default assignment 1233 * @param assignment current assignment to become default 1234 */ 1235 @Deprecated 1236 public void setDefaultAssignment(Assignment<V, T> assignment) { 1237 iAssignment = assignment; 1238 } 1239 1240 /** 1241 * Returns an instance of an empty assignment (using {@link EmptyAssignment}) 1242 * @return an empty assignment 1243 */ 1244 public Assignment<V, T> getEmptyAssignment() { 1245 if (iEmptyAssignment == null) 1246 iEmptyAssignment = new EmptyAssignment<V, T>(); 1247 return iEmptyAssignment; 1248 } 1249 1250 1251 /** 1252 * Create a new inherited assignment from the given solution 1253 * @param solution a solution that is using this model 1254 * @param index thread index of the new assignment 1255 * @return a new inherited assignment 1256 */ 1257 public InheritedAssignment<V, T> createInheritedAssignment(Solution<V, T> solution, int index) { 1258 return new DefaultInheritedAssignment<V, T>(solution, index); 1259 } 1260}