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 Tomas Muller<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.log4j.Logger sLogger = org.apache.log4j.Logger.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 } 229 230 /** Removes a global constraint from the model 231 * @param constraint a global constraint 232 **/ 233 @SuppressWarnings("unchecked") 234 public void removeGlobalConstraint(GlobalConstraint<V, T> constraint) { 235 constraint.setModel(null); 236 iGlobalConstraints.remove(constraint); 237 if (constraint instanceof InfoProvider<?, ?>) 238 iInfoProviders.remove(constraint); 239 for (ModelListener<V, T> listener : iModelListeners) 240 listener.constraintRemoved(constraint); 241 if (constraint instanceof HasAssignmentContext) 242 removeReference((HasAssignmentContext<V, T, ?>)constraint); 243 } 244 245 /** 246 * The list of unassigned variables in the model. 247 * Use {@link Model#unassignedVariables(Assignment)} or {@link Assignment#unassignedVariables(Model)} instead. 248 * @return list of unassigned variables in the model 249 **/ 250 @Deprecated 251 public Collection<V> unassignedVariables() { 252 return unassignedVariables(getDefaultAssignment()); 253 } 254 255 /** The list of unassigned variables in the model 256 * @param assignment current assignment 257 * @return list of unassigned variables in the model 258 **/ 259 public Collection<V> unassignedVariables(Assignment<V, T> assignment) { 260 return assignment.unassignedVariables(this); 261 } 262 263 /** 264 * Number of unassigned variables. 265 * Use {@link Model#nrUnassignedVariables(Assignment)} or {@link Assignment#nrUnassignedVariables(Model)} instead. 266 * @return number of unassigned variables in the model 267 **/ 268 @Deprecated 269 public int nrUnassignedVariables() { 270 return nrUnassignedVariables(getDefaultAssignment()); 271 } 272 273 /** Number of unassigned variables 274 * @param assignment current assignment 275 * @return number of unassigned variables in the model 276 **/ 277 public int nrUnassignedVariables(Assignment<V, T> assignment) { 278 return assignment.nrUnassignedVariables(this); 279 } 280 281 /** 282 * The list of assigned variables in the model. 283 * Use {@link Model#assignedVariables(Assignment)} or {@link Assignment#assignedVariables()} instead. 284 * @return list of assigned variables in the model 285 **/ 286 @Deprecated 287 public Collection<V> assignedVariables() { 288 return assignedVariables(getDefaultAssignment()); 289 } 290 291 /** The list of assigned variables in the model 292 * @param assignment current assignment 293 * @return list of assigned variables in the model 294 **/ 295 public Collection<V> assignedVariables(Assignment<V, T> assignment) { 296 return assignment.assignedVariables(); 297 } 298 299 /** 300 * Number of assigned variables. 301 * Use {@link Model#nrAssignedVariables(Assignment)} or {@link Assignment#nrAssignedVariables()} instead. 302 * @return number of assigned variables in the model 303 **/ 304 @Deprecated 305 public int nrAssignedVariables() { 306 return nrAssignedVariables(getDefaultAssignment()); 307 } 308 309 /** Number of assigned variables 310 * @param assignment current assignment 311 * @return number of assigned variables in the model 312 **/ 313 public int nrAssignedVariables(Assignment<V, T> assignment) { 314 return assignment.nrAssignedVariables(); 315 } 316 317 /** 318 * The list of perturbation variables in the model, i.e., the variables 319 * which has an initial value but which are not assigned with this value. 320 * Use {@link Model#perturbVariables(Assignment)} instead. 321 * @return list of perturbation variables in the model 322 */ 323 @Deprecated 324 public Collection<V> perturbVariables() { 325 return perturbVariables(getDefaultAssignment(), variablesWithInitialValue()); 326 } 327 328 /** 329 * The list of perturbation variables in the model, i.e., the variables 330 * which has an initial value but which are not assigned with this value. 331 * @param assignment current assignment 332 * @return list of perturbation variables in the model 333 */ 334 public Collection<V> perturbVariables(Assignment<V, T> assignment) { 335 return perturbVariables(assignment, variablesWithInitialValue()); 336 } 337 338 /** 339 * The list of perturbation variables in the model, i.e., the variables 340 * which has an initial value but which are not assigned with this value. 341 * Only variables from the given set are considered. 342 * Use {@link Model#perturbVariables(Assignment, Collection)} instead. 343 * @param variables sub-problem 344 * @return list of perturbation variables in the sub-problem 345 */ 346 @Deprecated 347 public List<V> perturbVariables(Collection<V> variables) { 348 return perturbVariables(getDefaultAssignment(), variables); 349 } 350 351 /** 352 * The list of perturbation variables in the model, i.e., the variables 353 * which has an initial value but which are not assigned with this value. 354 * Only variables from the given set are considered. 355 * @param assignment current assignment 356 * @param variables sub-problem 357 * @return list of perturbation variables in the sub-problem 358 */ 359 public List<V> perturbVariables(Assignment<V, T> assignment, Collection<V> variables) { 360 List<V> perturbances = new ArrayList<V>(); 361 for (V variable : variables) { 362 if (variable.getInitialAssignment() == null) 363 continue; 364 T value = assignment.getValue(variable); 365 if (value != null) { 366 if (!variable.getInitialAssignment().equals(value)) 367 perturbances.add(variable); 368 } else { 369 boolean hasPerturbance = false; 370 for (Constraint<V, T> constraint : variable.hardConstraints()) { 371 if (constraint.inConflict(assignment, variable.getInitialAssignment())) { 372 hasPerturbance = true; 373 break; 374 } 375 } 376 if (!hasPerturbance) 377 for (GlobalConstraint<V, T> constraint : globalConstraints()) { 378 if (constraint.inConflict(assignment, variable.getInitialAssignment())) { 379 hasPerturbance = true; 380 break; 381 } 382 } 383 if (hasPerturbance) 384 perturbances.add(variable); 385 } 386 } 387 return perturbances; 388 } 389 390 /** 391 * Returns the set of conflicting variables with this value, if it is 392 * assigned to its variable 393 * Use {@link Model#conflictValues(Assignment, Value)} instead. 394 * @param value a value to be assigned 395 * @return a set of conflicting values, i.e., values that would have to be unassigned if the given value is assigned to its variable 396 */ 397 @Deprecated 398 public Set<T> conflictValues(T value) { 399 return conflictValues(getDefaultAssignment(), value); 400 } 401 402 /** 403 * Returns the set of conflicting variables with this value, if it is 404 * assigned to its variable 405 * @param assignment current assignment 406 * @param value a value to be assigned 407 * @return a set of conflicting values, i.e., values that would have to be unassigned if the given value is assigned to its variable 408 */ 409 public Set<T> conflictValues(Assignment<V, T> assignment, T value) { 410 Set<T> conflictValues = new HashSet<T>(); 411 for (Constraint<V, T> constraint : value.variable().hardConstraints()) 412 constraint.computeConflicts(assignment, value, conflictValues); 413 for (GlobalConstraint<V, T> constraint : globalConstraints()) 414 constraint.computeConflicts(assignment, value, conflictValues); 415 return conflictValues; 416 } 417 418 /** 419 * Return true if the given value is in conflict with a hard constraint 420 * Use {@link Model#inConflict(Assignment, Value)} instead. 421 * @param value a value in question 422 * @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 423 **/ 424 @Deprecated 425 public boolean inConflict(T value) { 426 return inConflict(getDefaultAssignment(), value); 427 } 428 429 /** Return true if the given value is in conflict with a hard constraint 430 * @param assignment current assignment 431 * @param value a value in question 432 * @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 433 **/ 434 public boolean inConflict(Assignment<V, T> assignment, T value) { 435 for (Constraint<V, T> constraint : value.variable().hardConstraints()) 436 if (constraint.inConflict(assignment, value)) 437 return true; 438 for (GlobalConstraint<V, T> constraint : globalConstraints()) 439 if (constraint.inConflict(assignment, value)) 440 return true; 441 return false; 442 } 443 444 /** The list of variables with an initial value (i.e., variables with {@link Variable#getInitialAssignment()} not null) 445 * @return list of variables with an initial value 446 **/ 447 public Collection<V> variablesWithInitialValue() { 448 iVariablesWithInitialValueLock.readLock().lock(); 449 try { 450 if (iVariablesWithInitialValueCache != null) 451 return iVariablesWithInitialValueCache; 452 } finally { 453 iVariablesWithInitialValueLock.readLock().unlock(); 454 } 455 iVariablesWithInitialValueLock.writeLock().lock(); 456 try { 457 if (iVariablesWithInitialValueCache != null) 458 return iVariablesWithInitialValueCache; 459 iVariablesWithInitialValueCache = new ArrayList<V>(); 460 for (V variable : iVariables) { 461 if (variable.getInitialAssignment() != null) 462 iVariablesWithInitialValueCache.add(variable); 463 } 464 return iVariablesWithInitialValueCache; 465 } finally { 466 iVariablesWithInitialValueLock.writeLock().unlock(); 467 } 468 } 469 470 /** Invalidates cache containing all variables that possess an initial value */ 471 protected void invalidateVariablesWithInitialValueCache() { 472 iVariablesWithInitialValueLock.writeLock().lock(); 473 iVariablesWithInitialValueCache = null; 474 iVariablesWithInitialValueLock.writeLock().unlock(); 475 } 476 477 /** Called before a value is assigned to its variable 478 * @param iteration current iteration 479 * @param value a value to be assigned 480 **/ 481 @Deprecated 482 public void beforeAssigned(long iteration, T value) { 483 } 484 485 /** Called before a value is assigned to its variable 486 * @param assignment current assignment 487 * @param iteration current iteration 488 * @param value a value to be assigned 489 **/ 490 public void beforeAssigned(Assignment<V, T> assignment, long iteration, T value) { 491 beforeAssigned(iteration, value); 492 for (ModelListener<V, T> listener : iModelListeners) 493 listener.beforeAssigned(assignment, iteration, value); 494 } 495 496 /** Called before a value is unassigned from its variable 497 * @param iteration current iteration 498 * @param value a value to be unassigned 499 **/ 500 @Deprecated 501 public void beforeUnassigned(long iteration, T value) { 502 } 503 504 /** Called before a value is unassigned from its variable 505 * @param assignment current assignment 506 * @param iteration current iteration 507 * @param value a value to be unassigned 508 **/ 509 public void beforeUnassigned(Assignment<V, T> assignment, long iteration, T value) { 510 beforeUnassigned(iteration, value); 511 for (ModelListener<V, T> listener : iModelListeners) 512 listener.beforeUnassigned(assignment, iteration, value); 513 } 514 515 /** Called after a value is assigned to its variable 516 * @param iteration current iteration 517 * @param value a value that was assigned 518 **/ 519 @Deprecated 520 public void afterAssigned(long iteration, T value) { 521 } 522 523 /** Called after a value is assigned to its variable 524 * @param assignment current assignment 525 * @param iteration current iteration 526 * @param value a value that was assigned 527 **/ 528 public void afterAssigned(Assignment<V, T> assignment, long iteration, T value) { 529 afterAssigned(iteration, value); 530 for (ModelListener<V, T> listener : iModelListeners) 531 listener.afterAssigned(assignment, iteration, value); 532 } 533 534 /** Called after a value is unassigned from its variable 535 * @param iteration current iteration 536 * @param value a value that was unassigned 537 **/ 538 @Deprecated 539 public void afterUnassigned(long iteration, T value) { 540 } 541 542 /** Called after a value is unassigned from its variable 543 * @param assignment current assignment 544 * @param iteration current iteration 545 * @param value a value that was unassigned 546 **/ 547 public void afterUnassigned(Assignment<V, T> assignment, long iteration, T value) { 548 afterUnassigned(iteration, value); 549 for (ModelListener<V, T> listener : iModelListeners) 550 listener.afterUnassigned(assignment, iteration, value); 551 } 552 553 @Override 554 public String toString() { 555 return "Model{\n variables=" + ToolBox.col2string(variables(), 2) + ",\n constraints=" + ToolBox.col2string(constraints(), 2) + ",\n }"; 556 } 557 558 /** 559 * String representation -- returns a list of values of objective criteria 560 * @param assignment current assignment 561 * @return comma separated string of {@link TimetablingCriterion#toString(Assignment)} 562 */ 563 public String toString(Assignment<V, T> assignment) { 564 List<Criterion<V, T>> criteria = new ArrayList<Criterion<V,T>>(getCriteria()); 565 Collections.sort(criteria, new Comparator<Criterion<V, T>>() { 566 @Override 567 public int compare(Criterion<V, T> c1, Criterion<V, T> c2) { 568 int cmp = -Double.compare(c1.getWeight(), c2.getWeight()); 569 if (cmp != 0) return cmp; 570 return c1.getName().compareTo(c2.getName()); 571 } 572 }); 573 String ret = ""; 574 for (Criterion<V, T> criterion: criteria) { 575 String val = criterion.toString(assignment); 576 if (val != null && !val.isEmpty()) 577 ret += ", " + val; 578 } 579 return (nrUnassignedVariables(assignment) == 0 ? "" : "V:" + nrAssignedVariables(assignment) + "/" + variables().size() + ", ") + "T:" + sDoubleFormat.format(getTotalValue(assignment)) + ret; 580 } 581 582 protected String getPerc(double value, double min, double max) { 583 if (max == min) 584 return sPercentageFormat.format(100.0); 585 return sPercentageFormat.format(100.0 - 100.0 * (value - min) / (max - min)); 586 } 587 588 protected String getPercRev(double value, double min, double max) { 589 if (max == min) 590 return sPercentageFormat.format(0.0); 591 return sPercentageFormat.format(100.0 * (value - min) / (max - min)); 592 } 593 594 /** 595 * Returns information about the current solution. Information from all 596 * model listeners and constraints is also included. 597 * Use {@link Model#getInfo(Assignment)} instead. 598 * @return info table 599 */ 600 @Deprecated 601 public Map<String, String> getInfo() { 602 return getInfo(getDefaultAssignment()); 603 } 604 605 /** 606 * Returns information about the current solution. Information from all 607 * model listeners and constraints is also included. 608 * @param assignment current assignment 609 * @return info table 610 */ 611 public Map<String, String> getInfo(Assignment<V, T> assignment) { 612 Map<String, String> ret = new HashMap<String, String>(); 613 ret.put("Assigned variables", getPercRev(assignment.nrAssignedVariables(), 0, variables().size()) + "% (" + assignment.nrAssignedVariables() + "/" + variables().size() + ")"); 614 int nrVarsWithInitialValue = variablesWithInitialValue().size(); 615 if (nrVarsWithInitialValue > 0) { 616 Collection<V> pv = perturbVariables(assignment); 617 ret.put("Perturbation variables", getPercRev(pv.size(), 0, nrVarsWithInitialValue) + "% (" + pv.size() + " + " + (variables().size() - nrVarsWithInitialValue) + ")"); 618 } 619 ret.put("Overall solution value", sDoubleFormat.format(getTotalValue(assignment))); 620 for (InfoProvider<V, T> provider : iInfoProviders) 621 provider.getInfo(assignment, ret); 622 return ret; 623 } 624 625 /** 626 * Extended information about current solution. Similar to 627 * {@link Model#getInfo(Assignment)}, but some more information (that is more 628 * expensive to compute) might be added. 629 * Use {@link Model#getExtendedInfo(Assignment)} instead. 630 * @return extended info table 631 */ 632 @Deprecated 633 public Map<String, String> getExtendedInfo() { 634 return getExtendedInfo(getDefaultAssignment()); 635 } 636 637 /** 638 * Extended information about current solution. Similar to 639 * {@link Model#getInfo(Assignment)}, but some more information (that is more 640 * expensive to compute) might be added. 641 * @param assignment current assignment 642 * @return extended info table 643 */ 644 public Map<String, String> getExtendedInfo(Assignment<V, T> assignment) { 645 Map<String, String> ret = getInfo(assignment); 646 for (InfoProvider<V, T> provider : iInfoProviders) 647 if (provider instanceof ExtendedInfoProvider) 648 ((ExtendedInfoProvider<V, T>)provider).getExtendedInfo(assignment, ret); 649 return ret; 650 } 651 652 /** 653 * Returns information about the current solution. Information from all 654 * model listeners and constraints is also included. Only variables from the 655 * given set are considered. 656 * Use {@link Model#getInfo(Assignment, Collection)} instead. 657 * @param variables sub-problem 658 * @return info table 659 **/ 660 @Deprecated 661 public Map<String, String> getInfo(Collection<V> variables) { 662 return getInfo(getDefaultAssignment(), variables); 663 } 664 665 /** 666 * Returns information about the current solution. Information from all 667 * model listeners and constraints is also included. Only variables from the 668 * given set are considered. 669 * @param assignment current assignment 670 * @param variables sub-problem 671 * @return info table 672 */ 673 public Map<String, String> getInfo(Assignment<V, T> assignment, Collection<V> variables) { 674 Map<String, String> ret = new HashMap<String, String>(); 675 int assigned = 0, perturb = 0, nrVarsWithInitialValue = 0; 676 for (V variable : variables) { 677 T value = assignment.getValue(variable); 678 if (value != null) 679 assigned++; 680 if (variable.getInitialAssignment() != null) { 681 nrVarsWithInitialValue++; 682 if (value != null) { 683 if (!variable.getInitialAssignment().equals(value)) 684 perturb++; 685 } else { 686 boolean hasPerturbance = false; 687 for (Constraint<V, T> constraint : variable.hardConstraints()) { 688 if (constraint.inConflict(assignment, variable.getInitialAssignment())) { 689 hasPerturbance = true; 690 break; 691 } 692 } 693 if (!hasPerturbance) 694 for (GlobalConstraint<V, T> constraint : globalConstraints()) { 695 if (constraint.inConflict(assignment, variable.getInitialAssignment())) { 696 hasPerturbance = true; 697 break; 698 } 699 } 700 if (hasPerturbance) 701 perturb++; 702 } 703 } 704 } 705 ret.put("Assigned variables", getPercRev(assigned, 0, variables.size()) + "% (" + assigned + "/" + variables.size() + ")"); 706 if (nrVarsWithInitialValue > 0) { 707 ret.put("Perturbation variables", getPercRev(perturb, 0, nrVarsWithInitialValue) + "% (" + perturb + " + " + (variables.size() - nrVarsWithInitialValue) + ")"); 708 } 709 ret.put("Overall solution value", sDoubleFormat.format(getTotalValue(assignment, variables))); 710 for (InfoProvider<V, T> provider : iInfoProviders) 711 provider.getInfo(assignment, ret, variables); 712 return ret; 713 } 714 715 /** 716 * Returns the number of unassigned variables in the best ever found 717 * solution 718 * @return number of unassigned variables in the best solution 719 */ 720 public int getBestUnassignedVariables() { 721 return iBestUnassignedVariables; 722 } 723 724 /** 725 * Returns the number of perturbation variables in the best ever found 726 * solution 727 * @return number of perturbation variables in the best solution 728 */ 729 public int getBestPerturbations() { 730 return iBestPerturbations; 731 } 732 733 /** 734 * Total value of the best ever found solution -- sum of all assigned values 735 * (see {@link Value#toDouble(Assignment)}). 736 * @return value of the best solution 737 */ 738 public double getBestValue() { 739 return iBestValue; 740 } 741 742 /** Set total value of the best ever found solution 743 * @param bestValue value of the best solution 744 **/ 745 public void setBestValue(double bestValue) { 746 iBestValue = bestValue; 747 } 748 749 /** 750 * Save the current assignment as the best ever found assignment 751 * Use {@link Model#saveBest(Assignment)} instead. 752 **/ 753 @Deprecated 754 public void saveBest() { 755 saveBest(getDefaultAssignment()); 756 } 757 758 /** Save the current assignment as the best ever found assignment 759 * @param assignment current assignment 760 **/ 761 public void saveBest(Assignment<V, T> assignment) { 762 iBestUnassignedVariables = iVariables.size() - assignment.nrAssignedVariables(); 763 iBestPerturbations = perturbVariables(assignment).size(); 764 iBestValue = getTotalValue(assignment); 765 for (V variable : iVariables) { 766 variable.setBestAssignment(assignment.getValue(variable), assignment.getIteration(variable)); 767 } 768 for (Criterion<V, T> criterion: getCriteria()) { 769 criterion.bestSaved(assignment); 770 } 771 } 772 773 /** Clear the best ever found assignment */ 774 public void clearBest() { 775 iBestUnassignedVariables = -1; 776 iBestPerturbations = 0; 777 iBestValue = 0; 778 for (V variable : iVariables) { 779 variable.setBestAssignment(null, 0); 780 } 781 } 782 783 /** 784 * Restore the best ever found assignment into the current assignment 785 * Use {@link Model#restoreBest(Assignment)} instead. 786 **/ 787 @Deprecated 788 protected void restoreBest() { 789 restoreBest(getDefaultAssignment()); 790 } 791 792 /** Restore the best ever found assignment into the current assignment 793 * @param assignment current assignment 794 * @param assignmentOrder assignment order of the variables 795 **/ 796 @SuppressWarnings("unchecked") 797 protected void restoreBest(Assignment<V, T> assignment, Comparator<V> assignmentOrder) { 798 TreeSet<V> sortedVariables = new TreeSet<V>(assignmentOrder); 799 for (V variable : iVariables) { 800 T value = assignment.getValue(variable); 801 if (value == null) { 802 if (variable.getBestAssignment() != null) 803 sortedVariables.add(variable); 804 } else if (!value.equals(variable.getBestAssignment())) { 805 assignment.unassign(0, variable); 806 if (variable.getBestAssignment() != null) 807 sortedVariables.add(variable); 808 } 809 } 810 Set<T> problems = new HashSet<T>(); 811 for (V variable : sortedVariables) { 812 Set<T> confs = conflictValues(assignment, variable.getBestAssignment()); 813 if (!confs.isEmpty()) { 814 sLogger.error("restore best problem: assignment " + variable.getName() + " = " + variable.getBestAssignment().getName()); 815 boolean weakened = false; 816 for (Constraint<V, T> c : variable.hardConstraints()) { 817 Set<T> x = new HashSet<T>(); 818 c.computeConflicts(assignment, variable.getBestAssignment(), x); 819 if (!x.isEmpty()) { 820 if (c instanceof WeakeningConstraint) { 821 ((WeakeningConstraint<V, T>)c).weaken(assignment, variable.getBestAssignment()); 822 sLogger.info(" constraint " + c.getClass().getSimpleName() + " " + c.getName() + " had to be weakened"); 823 weakened = true; 824 } else { 825 sLogger.error(" constraint " + c.getClass().getSimpleName() + " " + c.getName() + " causes the following conflicts " + x); 826 } 827 } 828 } 829 for (GlobalConstraint<V, T> c : globalConstraints()) { 830 Set<T> x = new HashSet<T>(); 831 c.computeConflicts(assignment, variable.getBestAssignment(), x); 832 if (!x.isEmpty()) { 833 if (c instanceof WeakeningConstraint) { 834 ((WeakeningConstraint<V, T>)c).weaken(assignment, variable.getBestAssignment()); 835 sLogger.info(" constraint " + c.getClass().getSimpleName() + " " + c.getName() + " had to be weakened"); 836 weakened = true; 837 } else { 838 sLogger.error(" global constraint " + c.getClass().getSimpleName() + " " + c.getName() + " causes the following conflicts " + x); 839 } 840 } 841 } 842 if (weakened && conflictValues(assignment, variable.getBestAssignment()).isEmpty()) 843 assignment.assign(0, variable.getBestAssignment()); 844 else 845 problems.add(variable.getBestAssignment()); 846 } else 847 assignment.assign(0, variable.getBestAssignment()); 848 } 849 int attempt = 0, maxAttempts = 3 * problems.size(); 850 while (!problems.isEmpty() && attempt <= maxAttempts) { 851 attempt++; 852 T value = ToolBox.random(problems); 853 problems.remove(value); 854 V variable = value.variable(); 855 Set<T> confs = conflictValues(assignment, value); 856 if (!confs.isEmpty()) { 857 sLogger.error("restore best problem (again, att=" + attempt + "): assignment " + variable.getName() + " = " + value.getName()); 858 for (Constraint<V, T> c : variable.hardConstraints()) { 859 Set<T> x = new HashSet<T>(); 860 c.computeConflicts(assignment, value, x); 861 if (!x.isEmpty()) 862 sLogger.error(" constraint " + c.getClass().getSimpleName() + " " + c.getName() + " causes the following conflicts " + x); 863 } 864 for (GlobalConstraint<V, T> c : globalConstraints()) { 865 Set<T> x = new HashSet<T>(); 866 c.computeConflicts(assignment, value, x); 867 if (!x.isEmpty()) 868 sLogger.error(" constraint " + c.getClass().getSimpleName() + " " + c.getName() + " causes the following conflicts " + x); 869 } 870 for (T conf : confs) 871 assignment.unassign(0, conf.variable()); 872 problems.addAll(confs); 873 } 874 assignment.assign(0, value); 875 } 876 for (Criterion<V, T> criterion: getCriteria()) { 877 criterion.bestRestored(assignment); 878 } 879 } 880 881 /** Restore the best ever found assignment into the current assignment 882 * @param assignment current assignment 883 **/ 884 public void restoreBest(Assignment<V, T> assignment) { 885 restoreBest(assignment, new Comparator<V>() { 886 @Override 887 public int compare(V v1, V v2) { 888 if (v1.getBestAssignmentIteration() < v2.getBestAssignmentIteration()) return -1; 889 if (v1.getBestAssignmentIteration() > v2.getBestAssignmentIteration()) return 1; 890 return v1.compareTo(v2); 891 } 892 }); 893 } 894 895 /** 896 * The list of unassigned variables in the best ever found solution. 897 * Use {@link Model#bestUnassignedVariables(Assignment)} instead. 898 * @return variables list of unassigned variables in the best solution 899 **/ 900 @Deprecated 901 public Collection<V> bestUnassignedVariables() { 902 return bestUnassignedVariables(getDefaultAssignment()); 903 } 904 905 /** The list of unassigned variables in the best ever found solution 906 * @param assignment current assignment 907 * @return variables list of unassigned variables in the best solution 908 **/ 909 public Collection<V> bestUnassignedVariables(Assignment<V, T> assignment) { 910 Collection<V> ret = new ArrayList<V>(variables().size()); 911 if (iBestUnassignedVariables < 0) { 912 for (V variable : variables()) { 913 if (assignment.getValue(variable) == null) 914 ret.add(variable); 915 } 916 } else { 917 for (V variable : variables()) { 918 if (variable.getBestAssignment() == null) 919 ret.add(variable); 920 } 921 } 922 return ret; 923 } 924 925 /** 926 * Value of the current solution. It is the sum of all assigned values, 927 * i.e., {@link Value#toDouble(Assignment)}. 928 * Use {@link Model#getTotalValue(Assignment)} instead. 929 * @return solution value 930 */ 931 @Deprecated 932 public double getTotalValue() { 933 return getTotalValue(getDefaultAssignment()); 934 } 935 936 /** 937 * Value of the current solution. It is the sum of all assigned values, 938 * i.e., {@link Value#toDouble(Assignment)}. 939 * @param assignment current assignment 940 * @return solution value 941 */ 942 public double getTotalValue(Assignment<V, T> assignment) { 943 double ret = 0.0; 944 for (T t: assignment.assignedValues()) 945 ret += t.toDouble(assignment); 946 return ret; 947 } 948 949 /** 950 * Value of the current solution. It is the sum of all assigned values, 951 * i.e., {@link Value#toDouble(Assignment)}. Only variables from the given set are 952 * considered. 953 * Use {@link Model#getTotalValue(Assignment, Collection)} instead. 954 * @param variables sub-problem 955 * @return solution value 956 **/ 957 @Deprecated 958 public double getTotalValue(Collection<V> variables) { 959 return getTotalValue(getDefaultAssignment(), variables); 960 } 961 962 /** 963 * Value of the current solution. It is the sum of all assigned values, 964 * i.e., {@link Value#toDouble(Assignment)}. Only variables from the given set are 965 * considered. 966 * @param assignment current assignment 967 * @param variables sub-problem 968 * @return solution value 969 **/ 970 public double getTotalValue(Assignment<V, T> assignment, Collection<V> variables) { 971 double ret = 0.0; 972 for (V v: variables) { 973 T t = assignment.getValue(v); 974 if (t != null) 975 ret += t.toDouble(assignment); 976 } 977 return ret; 978 } 979 980 /** Adds a model listener 981 * @param listener a model listener 982 **/ 983 @SuppressWarnings("unchecked") 984 public void addModelListener(ModelListener<V, T> listener) { 985 iModelListeners.add(listener); 986 if (listener instanceof InfoProvider<?, ?>) 987 iInfoProviders.add((InfoProvider<V, T>) listener); 988 for (Constraint<V, T> constraint : iConstraints) 989 listener.constraintAdded(constraint); 990 for (V variable : iVariables) 991 listener.variableAdded(variable); 992 } 993 994 /** Removes a model listener 995 * @param listener a model listener 996 **/ 997 public void removeModelListener(ModelListener<V, T> listener) { 998 if (listener instanceof InfoProvider<?, ?>) 999 iInfoProviders.remove(listener); 1000 for (V variable : iVariables) 1001 listener.variableRemoved(variable); 1002 for (Constraint<V, T> constraint : iConstraints) 1003 listener.constraintRemoved(constraint); 1004 iModelListeners.remove(listener); 1005 } 1006 1007 /** Model initialization 1008 * @param solver current solver 1009 * @return true if successfully initialized 1010 **/ 1011 public boolean init(Solver<V, T> solver) { 1012 for (ModelListener<V, T> listener : new ArrayList<ModelListener<V, T>>(iModelListeners)) { 1013 if (!listener.init(solver)) 1014 return false; 1015 } 1016 return true; 1017 } 1018 1019 /** The list of model listeners 1020 * @return list of model listeners 1021 **/ 1022 public List<ModelListener<V, T>> getModelListeners() { 1023 return iModelListeners; 1024 } 1025 1026 /** The list of model listeners that are of the given class 1027 * @param type model listener type 1028 * @return list of model listeners that are of the given class 1029 **/ 1030 public ModelListener<V, T> modelListenerOfType(Class<ModelListener<V, T>> type) { 1031 for (ModelListener<V, T> listener : iModelListeners) { 1032 if (listener.getClass() == type) 1033 return listener; 1034 } 1035 return null; 1036 } 1037 1038 /** 1039 * The list of constraints which are in a conflict with the given value if 1040 * it is assigned to its variable. This means the constraints, which adds a 1041 * value into the set of conflicting values in 1042 * {@link Constraint#computeConflicts(Assignment, Value, Set)}. 1043 * @param assignment current assignment 1044 * @param value given value 1045 * @return hard constraints and their conflicts that are conflicting with the given value 1046 */ 1047 public Map<Constraint<V, T>, Set<T>> conflictConstraints(Assignment<V, T> assignment, T value) { 1048 Map<Constraint<V, T>, Set<T>> conflictConstraints = new HashMap<Constraint<V, T>, Set<T>>(); 1049 for (Constraint<V, T> constraint : value.variable().hardConstraints()) { 1050 Set<T> conflicts = new HashSet<T>(); 1051 constraint.computeConflicts(assignment, value, conflicts); 1052 if (!conflicts.isEmpty()) { 1053 conflictConstraints.put(constraint, conflicts); 1054 } 1055 } 1056 for (GlobalConstraint<V, T> constraint : globalConstraints()) { 1057 Set<T> conflicts = new HashSet<T>(); 1058 constraint.computeConflicts(assignment, value, conflicts); 1059 if (!conflicts.isEmpty()) { 1060 conflictConstraints.put(constraint, conflicts); 1061 } 1062 } 1063 return conflictConstraints; 1064 } 1065 1066 /** 1067 * The list of hard constraints which contain at least one variable that is 1068 * not assigned. 1069 * @param assignment current assignment 1070 * @return list of hard constraints which contain at least one variable that is not assigned 1071 */ 1072 public List<Constraint<V, T>> unassignedHardConstraints(Assignment<V, T> assignment) { 1073 List<Constraint<V, T>> ret = new ArrayList<Constraint<V, T>>(); 1074 constraints: for (Constraint<V, T> constraint : constraints()) { 1075 if (!constraint.isHard()) 1076 continue; 1077 for (V v : constraint.variables()) { 1078 if (assignment.getValue(v) == null) { 1079 ret.add(constraint); 1080 continue constraints; 1081 } 1082 } 1083 } 1084 if (iVariables.size() > assignment.nrAssignedVariables()) 1085 ret.addAll(globalConstraints()); 1086 return ret; 1087 } 1088 1089 /** Registered info providers (see {@link InfoProvider}) 1090 * @return list of registered info providers 1091 **/ 1092 protected List<InfoProvider<V, T>> getInfoProviders() { 1093 return iInfoProviders; 1094 } 1095 1096 /** Register a new criterion 1097 * @param criterion a criterion 1098 **/ 1099 public void addCriterion(Criterion<V,T> criterion) { 1100 iCriteria.put(criterion.getClass().getName(), criterion); 1101 criterion.setModel(this); 1102 addModelListener(criterion); 1103 } 1104 1105 /** Unregister an existing criterion 1106 * @param criterion a criterion 1107 **/ 1108 public void removeCriterion(Criterion<V,T> criterion) { 1109 iCriteria.remove(criterion.getClass().getName()); 1110 criterion.setModel(null); 1111 removeModelListener(criterion); 1112 } 1113 1114 /** Unregister an existing criterion 1115 * @param criterion a criterion 1116 **/ 1117 public void removeCriterion(Class<? extends Criterion<V, T>> criterion) { 1118 Criterion<V,T> c = iCriteria.remove(criterion.getName()); 1119 if (c != null) 1120 removeModelListener(c); 1121 } 1122 1123 /** Return a registered criterion of the given type. 1124 * @param criterion criterion type 1125 * @return registered criterion of the given type 1126 **/ 1127 public Criterion<V, T> getCriterion(Class<? extends Criterion<V, T>> criterion) { 1128 return iCriteria.get(criterion.getName()); 1129 } 1130 1131 /** List all registered criteria 1132 * @return list all registered criteria 1133 **/ 1134 public Collection<Criterion<V, T>> getCriteria() { 1135 return iCriteria.values(); 1136 } 1137 1138 /** 1139 * Weaken all weakening constraint so that the given value can be assigned without 1140 * them creating a conflict using {@link WeakeningConstraint#weaken(Assignment, Value)}. 1141 * This method is handy for instance when an existing solution is being loaded 1142 * into the solver. 1143 * @param assignment current assignment 1144 * @param value given value 1145 */ 1146 @SuppressWarnings("unchecked") 1147 public void weaken(Assignment<V, T> assignment, T value) { 1148 for (Constraint<V, T> constraint : value.variable().hardConstraints()) { 1149 if (constraint instanceof WeakeningConstraint) 1150 ((WeakeningConstraint<V,T>)constraint).weaken(assignment, value); 1151 } 1152 for (GlobalConstraint<V, T> constraint : globalConstraints()) { 1153 if (constraint instanceof WeakeningConstraint) 1154 ((WeakeningConstraint<V,T>)constraint).weaken(assignment, value); 1155 } 1156 } 1157 1158 /** 1159 * Create a reference to an assignment context for a class that is in a need of one. Through this 1160 * reference an assignment context (see {@link AssignmentContext}) can be accessed using 1161 * {@link Assignment#getAssignmentContext(AssignmentContextReference)}. 1162 * @param parent class needing an assignment context 1163 * @param <C> assignment context type 1164 * @return reference to an assignment context 1165 */ 1166 public synchronized <C extends AssignmentContext> AssignmentContextReference<V,T,C> createReference(HasAssignmentContext<V, T, C> parent) { 1167 AssignmentContextReference<V, T, C> ref = new AssignmentContextReference<V, T, C>(parent, iNextReferenceId); 1168 iAssignmentContextReferences.put(iNextReferenceId, ref); 1169 iNextReferenceId++; 1170 return ref; 1171 } 1172 1173 /** 1174 * Clear all assignment contexts for the given assignment 1175 * @param assignment given {@link Assignment} 1176 */ 1177 public synchronized void clearAssignmentContexts(Assignment<V, T> assignment) { 1178 for (AssignmentContextReference<V,T,? extends AssignmentContext> ref: iAssignmentContextReferences.values()) 1179 assignment.clearContext(ref); 1180 } 1181 1182 /** 1183 * Remove a reference to an assignment context for the model 1184 * @param parent class with an assignment context 1185 * @param <C> assignment context type 1186 * @return reference to an assignment context that was removed from the model (if any) 1187 */ 1188 @SuppressWarnings("unchecked") 1189 public synchronized <C extends AssignmentContext> AssignmentContextReference<V,T,C> removeReference(HasAssignmentContext<V, T, C> parent) { 1190 AssignmentContextReference<V,T,C> reference = parent.getAssignmentContextReference(); 1191 if (reference != null) 1192 return (AssignmentContextReference<V,T,C>) iAssignmentContextReferences.remove(reference.getIndex()); 1193 return null; 1194 } 1195 1196 /** 1197 * Create all assignment contexts for the given assignment 1198 * @param assignment given {@link Assignment} 1199 * @param clear if true {@link Assignment#clearContext(AssignmentContextReference)} is called first 1200 */ 1201 public synchronized void createAssignmentContexts(Assignment<V, T> assignment, boolean clear) { 1202 for (AssignmentContextReference<V,T,? extends AssignmentContext> ref: iAssignmentContextReferences.values()) { 1203 if (clear) assignment.clearContext(ref); 1204 assignment.getAssignmentContext(ref); 1205 } 1206 } 1207 1208 /** 1209 * Return default assignment that is using the old {@link Variable#getAssignment()} assignments. 1210 * @return as instance of {@link DefaultSingleAssignment} 1211 */ 1212 @Deprecated 1213 public Assignment<V, T> getDefaultAssignment() { 1214 if (iAssignment == null) 1215 iAssignment = new DefaultSingleAssignment<V, T>(); 1216 return iAssignment; 1217 } 1218 1219 /** 1220 * Set default assignment 1221 * @param assignment current assignment to become default 1222 */ 1223 @Deprecated 1224 public void setDefaultAssignment(Assignment<V, T> assignment) { 1225 iAssignment = assignment; 1226 } 1227 1228 /** 1229 * Returns an instance of an empty assignment (using {@link EmptyAssignment}) 1230 * @return an empty assignment 1231 */ 1232 public Assignment<V, T> getEmptyAssignment() { 1233 if (iEmptyAssignment == null) 1234 iEmptyAssignment = new EmptyAssignment<V, T>(); 1235 return iEmptyAssignment; 1236 } 1237 1238 1239 /** 1240 * Create a new inherited assignment from the given solution 1241 * @param solution a solution that is using this model 1242 * @param index thread index of the new assignment 1243 * @return a new inherited assignment 1244 */ 1245 public InheritedAssignment<V, T> createInheritedAssignment(Solution<V, T> solution, int index) { 1246 return new DefaultInheritedAssignment<V, T>(solution, index); 1247 } 1248}