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