1 /* 2 * Knapsack.java 3 * This file is part of JaCoP. 4 * <p> 5 * JaCoP is a Java Constraint Programming solver. 6 * <p> 7 * Copyright (C) 2000-2008 Radoslaw Szymanek and Wadeck Follonier 8 * <p> 9 * This program is free software: you can redistribute it and/or modify 10 * it under the terms of the GNU Affero General Public License as published by 11 * the Free Software Foundation, either version 3 of the License, or 12 * (at your option) any later version. 13 * <p> 14 * This program is distributed in the hope that it will be useful, 15 * but WITHOUT ANY WARRANTY; without even the implied warranty of 16 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 17 * GNU Affero General Public License for more details. 18 * <p> 19 * Notwithstanding any other provision of this License, the copyright 20 * owners of this work supplement the terms of this License with terms 21 * prohibiting misrepresentation of the origin of this work and requiring 22 * that modified versions of this work be marked in reasonable ways as 23 * different from the original version. This supplement of the license 24 * terms is in accordance with Section 7 of GNU Affero General Public 25 * License version 3. 26 * <p> 27 * You should have received a copy of the GNU Affero General Public License 28 * along with this program. If not, see <http://www.gnu.org/licenses/>. 29 */ 30 31 package org.jacop.constraints.knapsack; 32 33 import org.jacop.api.RemoveLevelLate; 34 import org.jacop.api.SatisfiedPresent; 35 import org.jacop.api.UsesQueueVariable; 36 import org.jacop.constraints.Constraint; 37 import org.jacop.core.*; 38 39 import java.util.*; 40 import java.util.concurrent.atomic.AtomicInteger; 41 import java.util.stream.Stream; 42 43 /** 44 * It specifies a knapsack constraint. This implementation was inspired 45 * by the paper by Irit Katriel, Meinolf Sellmann, Eli Upfal, 46 * Pascal Van Hentenryck: "Propagating Knapsack Constraints in Sublinear Time", 47 * AAAI 2007: pp. 231-236. 48 * <p> 49 * Tha major extensions of that paper are the following. The quantity variables 50 * do not have to be binary. The profit and capacity of the knapsacks do not 51 * have to be integers. In both cases, the constraint accepts any finite 52 * domain variable. 53 * <p> 54 * This implementation is based on the implementation obtained by Wadeck 55 * Follonier during his work on a student semester project. 56 * <p> 57 * We would like to thank Meinolf Sellmann for his appreciation of our work 58 * and useful comments. 59 * 60 * @author Radoslaw Szymanek and Wadeck Follonier 61 * @version 4.8 62 */ 63 64 public class Knapsack extends Constraint implements UsesQueueVariable, SatisfiedPresent, RemoveLevelLate { 65 66 private final static AtomicInteger idNumber = new AtomicInteger(0); 67 68 /** 69 * It specifies if any debugging information should be printed. 70 */ 71 public static final boolean debugAll = false; 72 73 /** 74 * It specifies mapping from variables into the leaf of the knapsack tree. 75 */ 76 private Map<IntVar, TreeLeaf> variableLeafMapping; 77 78 /** 79 * The current position of the critical item in the tree 80 */ 81 private TimeStamp<Integer> positionOfCriticalItem; 82 83 /** 84 * It stores all the leaves of the knapsack tree in one array. The leaves 85 * are sorted from the most efficient to the least efficient. 86 */ 87 private TreeLeaf[] leaves; 88 89 /** 90 * It stores for each level the leaves which have changed at this level. 91 * It is used by removeLevel function. There is a limit at which leaves 92 * will not be added and the whole tree will be updated. 93 */ 94 private Map<Integer, List<TreeLeaf>> hashForUpdate; 95 96 /** 97 * It specifies the limit after which the changed leaves are not 98 * store and the remove level will simply recompute attributes 99 * of all nodes in the knapsack tree. By default it is equal to 100 * n/log(n), where n is the number of the items. 101 */ 102 private int updateLimit; 103 104 /** 105 * It specifies if the constraint has already discovered to be unsatisfied 106 * during the imposition stage. 107 */ 108 109 private boolean impositionFailure = false; 110 111 /** 112 * This is a finite domain variable to specify the knapsack capacity. 113 */ 114 protected IntVar knapsackCapacity; 115 116 /** 117 * This is a finite domain variable to specify the knapsack profit. 118 */ 119 protected IntVar knapsackProfit; 120 121 122 /** 123 * It specifies the current level of the constraint store at which 124 * the consistency function of this constraint is being executed. 125 */ 126 public int currentLevel; 127 128 /** 129 * It specifies the position of the last changed item which has been 130 * already been recomputed. It helps to avoid recomputation of the same 131 * parts of the tree if consistency function of the knapsack constraint 132 * is called multiple times within the same store level. 133 */ 134 135 private int positionOfAlreadyUpdated; 136 137 /** 138 * It specifies if the knapsack tree requires an update. 139 */ 140 private boolean needUpdate = true; 141 142 /** 143 * It specifies if the consistency function should execute. 144 */ 145 private boolean needConsistency = true; 146 147 /** 148 * It specifies if the mandatory part of the consistency algorithm should be 149 * executed. 150 */ 151 private boolean needMandatory = true; 152 153 /** 154 * It specifies if the forbidden part of the consistency algortihm should be 155 * executed. 156 */ 157 private boolean needForbidden = true; 158 159 /** 160 * It specifies if the recomputation of the critical item should take place. 161 */ 162 private boolean needCriticalUpdate = true; 163 164 /** 165 * It specifies if the constraint is executing the consistency function. 166 */ 167 private boolean inConsistency = false; 168 169 /** 170 * The tree for the storing information about the maximalWeight, 171 * sum of weights and sum of profits. 172 */ 173 public Tree tree; 174 175 /** 176 * The array of items present in the knapsack constraint. 177 */ 178 public KnapsackItem[] items; 179 180 181 /** 182 * It counts the number of time the consistency function has been executed. 183 */ 184 private int countConsistency = 0; 185 186 /** 187 * It counts the number of times the queueVariable function has been executed. 188 */ 189 private int countQueueVariable = 0; 190 191 /** 192 * It counts the number of time the removeLevel function has been executed. 193 */ 194 private int countRemoveLevel = 0; 195 196 197 /** 198 * It specifies how many removeLevel functions must be executed before the information 199 * about the constraint is being printed out. 200 */ 201 private int REMOVE_INFO_FROM = 0; 202 203 /** 204 * It specifies how many queueVariable functions must be executed before the information 205 * about the constraint is being printed out. 206 */ 207 208 private int QUEUE_INFO_FROM = 0; 209 210 /** 211 * It specifies how many consistency functions must be executed before the information 212 * about the constraint is being printed out. 213 */ 214 215 private int CONSISTENCY_INFO_FROM = 0; 216 217 218 /** 219 * It constructs an knapsack constraint. 220 * 221 * @param items list of items in knapsack with its weight, profit and quantity variable. 222 * @param knapsackCapacity overall knapsack capacity. 223 * @param knapsackProfit overall profit obtained by the items in the knapsack. 224 */ Knapsack(KnapsackItem[] items, IntVar knapsackCapacity, IntVar knapsackProfit)225 public Knapsack(KnapsackItem[] items, IntVar knapsackCapacity, IntVar knapsackProfit) { 226 227 checkInputForNullness(new String[] {"items", "knapsackCapacity", "knapsackProfit"}, 228 new Object[][] {items, {knapsackCapacity}, {knapsackProfit}}); 229 230 // it handles duplicates. 231 commonInitialization(Arrays.stream(items).mapToInt(KnapsackItem::getProfit).toArray(), 232 Arrays.stream(items).mapToInt(KnapsackItem::getWeight).toArray(), 233 Arrays.stream(items).map(KnapsackItem::getVariable).toArray(IntVar[]::new), knapsackCapacity, knapsackProfit); 234 235 } 236 237 /** 238 * It constructs the knapsack constraint. 239 * 240 * @param profits the list of profits, each for the corresponding item no. 241 * @param weights the list of weights, each for the corresponding item no. 242 * @param quantity finite domain variable specifying allowed values for the vars. 243 * @param knapsackCapacity finite domain variable specifying the capacity limit of the knapsack. 244 * @param knapsackProfit finite domain variable defining the profit 245 */ Knapsack(int[] profits, int[] weights, IntVar[] quantity, IntVar knapsackCapacity, IntVar knapsackProfit)246 public Knapsack(int[] profits, int[] weights, IntVar[] quantity, IntVar knapsackCapacity, IntVar knapsackProfit) { 247 248 checkInputForNullness(new String[] {"profits", "weights", "quantity", "knapsackCapacity", "knapsackProfit"}, 249 new Object[][] {{profits}, {weights}, quantity, {knapsackCapacity}, {knapsackProfit}}); 250 251 if (profits.length != weights.length) 252 throw new IllegalArgumentException("Constraint Knapsack has profits and weights parameters of different length"); 253 254 if (profits.length != quantity.length) 255 throw new IllegalArgumentException("Constraint Knapsack has profits and quantity parameters of different length"); 256 257 commonInitialization(profits, weights, quantity, knapsackCapacity, knapsackProfit); 258 } 259 commonInitialization(int[] profits, int[] weights, IntVar[] quantity, IntVar knapsackCapacity, IntVar knapsackProfit)260 private void commonInitialization(int[] profits, int[] weights, IntVar[] quantity, IntVar knapsackCapacity, IntVar knapsackProfit) { 261 262 numberId = idNumber.incrementAndGet(); 263 queueIndex = 1; 264 265 /* We start to create an array of items */ 266 /* KKU- 2016/01/14, duplicated items are collected into a single item */ 267 LinkedHashMap<IntVar, KnapsackItem> itemPar = new LinkedHashMap<>(); 268 for (int i = 0; i < quantity.length; i++) { 269 if (itemPar.get(quantity[i]) != null) { 270 KnapsackItem ki = itemPar.get(quantity[i]); 271 Integer nw = ki.getWeight() + weights[i]; 272 Integer np = ki.getProfit() + profits[i]; 273 itemPar.put(quantity[i], new KnapsackItem(quantity[i], nw, np)); 274 } else 275 itemPar.put(quantity[i], new KnapsackItem(quantity[i], weights[i], profits[i])); 276 } 277 278 items = itemPar.values().toArray(new KnapsackItem[itemPar.size()]); 279 this.knapsackCapacity = knapsackCapacity; 280 this.knapsackProfit = knapsackProfit; 281 this.updateLimit = (int) (quantity.length / (Math.log(quantity.length) / Math.log(2))); 282 283 setScope(Stream.concat(Arrays.stream(quantity), Stream.of(knapsackCapacity, knapsackProfit))); 284 285 } 286 cleanAfterFailure()287 @Override public void cleanAfterFailure() { 288 inConsistency = false; 289 } 290 removeLevelLate(int level)291 @Override public void removeLevelLate(int level) { 292 293 countRemoveLevel++; 294 295 if (debugAll) { 296 297 if (countRemoveLevel >= REMOVE_INFO_FROM) { 298 299 System.out.println("Removelevel for " + level + " is called."); 300 System.out.println(displayQuantitiesInEfficiencyOrder()); 301 302 } 303 304 } 305 306 List<TreeLeaf> list = hashForUpdate.get(level); 307 /* there was some change in this level */ 308 if (list != null) { 309 /* use the array to update */ 310 if (list.size() > updateLimit) { 311 tree.recompute(); 312 needCriticalUpdate = true; 313 } else { 314 tree.updateFromList(list, 0); 315 needCriticalUpdate = true; 316 } 317 318 /* and then, we delete it */ 319 hashForUpdate.put(level, null); 320 } 321 322 tree.criticalLeaf.positionInTheTree = positionOfCriticalItem.value(); 323 324 } 325 326 /** 327 * It makes sure that no item has a possibility to use more than 328 * available capacity. 329 * <p> 330 * quantity.max() * weight < remainingCapacity. 331 * 332 * @param store the constraint store responsible for stroing the problem. 333 * @param parent the node from which the restriction 334 * of items quantities takes place (usually the root). 335 * @param availableCapacity it specifies how much left there is a knapsack company. 336 */ restrictItemQuantity(Store store, TreeNode parent, int availableCapacity)337 private void restrictItemQuantity(Store store, TreeNode parent, int availableCapacity) { 338 339 if (parent.getWMax() > availableCapacity) { 340 341 // This is abrupt change outside normal mandatory/forbidden algorithm so it may influence 342 // those algorithms. It is treated as outside change. 343 inConsistency = false; 344 345 TreeNode current; 346 347 { /* left part */ 348 current = parent.left; 349 if (!current.isLeaf()) { 350 restrictItemQuantity(store, current, availableCapacity); 351 } else if (current.getWMax() > availableCapacity) { 352 353 IntVar quantity = ((TreeLeaf) current).quantity; 354 355 assert (quantity.min() == ((TreeLeaf) current).slice) : "Quantity.min is not equal slice."; 356 357 quantity.domain.inMax(store.level, quantity, 358 quantity.min() + (int) Math.floor(availableCapacity / (double) ((TreeLeaf) current).weightOfOne)); 359 } 360 } 361 362 { /* right part */ 363 current = parent.right; 364 if (!current.isLeaf()) { 365 restrictItemQuantity(store, current, availableCapacity); 366 } else if (current.getWMax() > availableCapacity) { 367 368 TreeLeaf leaf = (TreeLeaf) current; 369 370 int maxNoOfAllowed = (int) Math.floor(availableCapacity / (double) leaf.getWeightOfOne()); 371 372 IntVar quantity = leaf.quantity; 373 374 assert (quantity.min() == leaf.slice) : "Quantity.min is not equal slice."; 375 376 quantity.domain.inMax(currentLevel, quantity, quantity.min() + maxNoOfAllowed); 377 378 needUpdate = true; 379 } 380 } 381 382 inConsistency = true; 383 384 } 385 386 387 } 388 389 /** 390 * It updates the knapsack tree to reflect all the changes which 391 * has happen since the last execution of the consistency function. 392 * It will in particular update information about already obtained 393 * profit as well as already used capacity. The domain of knapsack profit 394 * or capacity variable may be reduced. 395 */ blockUpdate()396 private void blockUpdate() { 397 398 // It first updates the tree data structure. 399 if (needUpdate) { 400 needUpdate = false; 401 402 List<TreeLeaf> list = hashForUpdate.get(currentLevel); 403 if (list != null) { 404 // there were too many updates to use incremental recomputation 405 if (list.size() > updateLimit) { 406 tree.recompute(); 407 needCriticalUpdate = true; 408 } else { 409 // there were few updates so each change is propagated up to the root. 410 tree.updateFromList(list, positionOfAlreadyUpdated); 411 positionOfAlreadyUpdated = list.size(); 412 needCriticalUpdate = true; 413 } 414 } 415 } 416 417 // It computes based on the minimum required profit a minimum required weight to get that profit. 418 if (knapsackProfit.min() > tree.alreadyObtainedProfit) { 419 int minWeight = tree.computeMinWeight(knapsackProfit.min() - tree.alreadyObtainedProfit); 420 421 if (knapsackCapacity.min() < minWeight) 422 knapsackCapacity.domain.inMin(currentLevel, knapsackCapacity, minWeight); 423 424 } 425 426 // It makes sure that knapsack capacity is within limits of already used capacity and the maximal 427 // remaining capacity which can be used. 428 knapsackCapacity.domain 429 .in(currentLevel, knapsackCapacity, tree.alreadyUsedCapacity, tree.alreadyUsedCapacity + tree.root.getWSum()); 430 431 432 if (debugAll) 433 System.out.println("Capacity after potential update : " + knapsackCapacity); 434 435 436 // It computes based on the minimum required capacity the minimum possible profit obtained if 437 // that capacity is being used. 438 if (knapsackCapacity.min() > tree.alreadyUsedCapacity) { 439 int minProfit = tree.computeMinProfit(knapsackCapacity.min() - tree.alreadyUsedCapacity); 440 441 if (knapsackProfit.min() < minProfit) 442 knapsackProfit.domain.inMin(currentLevel, knapsackProfit, minProfit); 443 } 444 445 446 if (needCriticalUpdate) { 447 // If there was an update which can shift critical item then critical item is recomputed. 448 needCriticalUpdate = false; 449 tree.updateCritical(knapsackCapacity.max() - tree.alreadyUsedCapacity); 450 positionOfCriticalItem.update(tree.criticalLeaf.positionInTheTree); 451 } 452 453 // It computes the range for profit given the fact that we use the remaining weight optimally in non-fractional fashion. 454 knapsackProfit.domain 455 .in(currentLevel, knapsackProfit, tree.alreadyObtainedProfit, tree.alreadyObtainedProfit + (int) Math.ceil(tree.optimalProfit)); 456 457 if (debugAll) 458 System.out.println("Profit after potential update : " + knapsackProfit); 459 460 } 461 consistency(Store store)462 @Override public void consistency(Store store) { 463 464 // it is possible that there changes to variables which have no chance to cause any pruning. 465 // it is already the case that constraint is not even notified of ANY pruning events. 466 if (!needConsistency) 467 return; 468 469 if (impositionFailure) 470 throw Store.failException; 471 472 if (debugAll) 473 System.out.println("Entering consistency " + this); 474 475 currentLevel = store.level; 476 countConsistency++; 477 inConsistency = true; 478 needUpdate = true; 479 480 blockUpdate(); 481 482 if (debugAll) { 483 if (countConsistency >= CONSISTENCY_INFO_FROM) 484 System.out.println(displayQuantitiesInEfficiencyOrder()); 485 } 486 487 assert (sliceInvariant()); 488 489 if (debugAll) 490 System.out.println("Tree root \n" + tree.root); 491 492 // it checks if not too many items exceeding the capacity constraints 493 // have been put in knapsack. 494 495 assert (checkInvariants()); 496 497 //@TODO possibly redundant check, going from the root. 498 restrictItemQuantity(store, tree.root, knapsackCapacity.max() - tree.alreadyUsedCapacity); 499 500 if (needUpdate) { 501 blockUpdate(); 502 assert (sliceInvariant()); 503 } 504 505 if (debugAll) 506 System.out.println("After single item restrictions " + this); 507 508 if (debugAll) 509 System.out.println("Tree root \n" + tree.root); 510 511 assert (checkInvariants()); 512 513 /* compute mandatory items using jump */ 514 if (needMandatory) 515 computeMandatory(); 516 517 blockUpdate(); 518 519 assert (checkInvariants()); 520 assert (sliceInvariant()); 521 522 /* compute forbidden items using jump */ 523 if (needForbidden) 524 computeForbidden(); 525 526 blockUpdate(); 527 assert (checkInvariants()); 528 529 needConsistency = false; 530 needUpdate = false; 531 needCriticalUpdate = false; 532 needMandatory = false; 533 needForbidden = false; 534 535 if (debugAll) { 536 if (countConsistency >= CONSISTENCY_INFO_FROM) 537 System.out.println(displayQuantitiesInEfficiencyOrder()); 538 } 539 540 inConsistency = false; 541 542 } 543 544 /** 545 * It searches through a subset of right items to find the ones which 546 * can not be fully included without violating the profit requirement 547 * in the knapsack constraint. 548 */ computeForbidden()549 private void computeForbidden() { 550 551 tree.initializeComputeForbidden(); 552 553 TreeLeaf leaf = tree.getLast(); 554 555 int criticalLeafPosition = tree.criticalLeaf.positionInTheTree; 556 557 if (leaf.getWMax() == 0) 558 leaf = tree.findPreviousLeafAtLeastOfWeight(leaf, tree.currentWeight); 559 560 if (leaf == null) 561 return; 562 563 // Perform forbidden reasoning only on the right items. 564 if (leaf.positionInTheTree <= criticalLeafPosition) 565 return; 566 567 // double profitSlack = (int) Math.ceil( tree.optimalProfit ) + 568 // tree.alreadyObtainedProfit - knapsackProfit.min(); 569 // @TODO, check that lack of safe rounding (ceil) is not a problem 570 // rounding errors may suggest that there is too little slack for an item. 571 double profitSlack = tree.optimalProfit + tree.alreadyObtainedProfit - knapsackProfit.min(); 572 573 574 while (true) { 575 576 int intrusionWeight = tree.computeIntrusionWeight(leaf.weightOfOne, leaf.max(), leaf.profitOfOne, leaf.efficiency, profitSlack); 577 578 int itemMaxWeight = leaf.max() * leaf.weightOfOne; 579 580 if (intrusionWeight < itemMaxWeight) { 581 582 int forbiddenQuantity = (int) Math.ceil((itemMaxWeight - intrusionWeight) / (double) leaf.weightOfOne); 583 584 IntVar quantity = leaf.getVariable(); 585 quantity.domain.inMax(currentLevel, quantity, quantity.max() - forbiddenQuantity); 586 587 needUpdate = true; 588 } 589 590 if (debugAll) 591 System.out.println("Forbidden check for " + leaf + " finished. Intrusion weight = " + intrusionWeight); 592 593 leaf = tree.findPreviousLeafAtLeastOfWeight(leaf, tree.currentWeight); 594 595 if (leaf == null) 596 break; 597 598 // Perform forbidden reasoning only on the right items. 599 if (leaf.positionInTheTree <= criticalLeafPosition) 600 break; 601 602 } 603 604 } 605 606 /** 607 * It computes the mandatory part of the knapsack pruning. 608 */ computeMandatory()609 private void computeMandatory() { 610 611 tree.initializeComputeMandatory(); 612 613 int criticalLeafPosition = tree.criticalLeaf.positionInTheTree; 614 615 TreeLeaf leaf = tree.getFirst(); 616 617 if (leaf.getWMax() == 0) 618 leaf = tree.findNextLeafAtLeastOfWeight(leaf, tree.currentWeight); 619 620 if (leaf == null) 621 return; 622 623 // Perform mandatory reasoning only on the left items. 624 if (leaf.positionInTheTree >= criticalLeafPosition) 625 return; 626 627 // double profitSlack = (int) Math.ceil( tree.optimalProfit ) + 628 // tree.alreadyObtainedProfit - knapsackProfit.min(); 629 // @todo Test, that there is no rounding errors due to using double for 630 // profitSlack and not safe ceil(profitSlack). 631 double profitSlack = tree.optimalProfit + tree.alreadyObtainedProfit - knapsackProfit.min(); 632 633 while (true) { 634 635 int replacableWeight = 636 tree.computeReplacableWeight(leaf.weightOfOne, leaf.max(), leaf.profitOfOne, leaf.efficiency, profitSlack); 637 638 int itemMaxWeight = leaf.max() * leaf.weightOfOne; 639 640 if (replacableWeight < itemMaxWeight) { 641 642 int mandatoryWeight = itemMaxWeight - replacableWeight; 643 int mandatoryQuantity = (int) Math.ceil(mandatoryWeight / (double) leaf.weightOfOne); 644 645 IntVar quantity = leaf.getVariable(); 646 quantity.domain.inMin(currentLevel, quantity, quantity.min() + mandatoryQuantity); 647 648 needUpdate = true; 649 } 650 651 if (debugAll) 652 System.out.println("Mandatory check for " + leaf + " finished. MaxWeight = " + replacableWeight); 653 654 leaf = tree.findNextLeafAtLeastOfWeight(leaf, tree.currentWeight); 655 656 if (leaf == null) 657 break; 658 659 // Perform mandatory reasoning only on the left items. 660 if (leaf.positionInTheTree >= criticalLeafPosition) 661 break; 662 663 } 664 665 666 } 667 impose(Store store)668 @Override public void impose(Store store) { 669 670 store.registerRemoveLevelLateListener(this); 671 672 hashForUpdate = new HashMap<>(); 673 674 /* We sort it with a sorting method */ 675 Arrays.sort(items); 676 677 /* 678 * We create the tree from the items and initialize the positionsInTree 679 */ 680 681 IntVar zero = new IntVar(store, 0, 0); 682 683 leaves = new TreeLeaf[items.length]; 684 685 variableLeafMapping = Var.createEmptyPositioning(); 686 687 tree = new Tree(items, variableLeafMapping, leaves, zero); 688 689 if (knapsackCapacity.max() >= tree.alreadyUsedCapacity) { 690 tree.updateCritical(knapsackCapacity.max() - tree.alreadyUsedCapacity); 691 positionOfCriticalItem = new TimeStamp<>(store, tree.criticalLeaf.positionInTheTree); 692 } else 693 impositionFailure = true; 694 695 if (tree.root.getPSum() + tree.alreadyObtainedProfit < knapsackProfit.min()) 696 impositionFailure = true; 697 698 if (tree.root.getWSum() + tree.alreadyUsedCapacity < knapsackCapacity.min()) 699 impositionFailure = true; 700 701 if (debugAll) { 702 703 if (!impositionFailure) 704 System.out.println("The impose function is completed. "); 705 else 706 System.out.println("The impose function has already detected inconsistency."); 707 708 System.out.println(this); 709 System.out.println(tree.toString()); 710 } 711 712 super.impose(store); 713 714 } 715 queueVariable(int level, Var v)716 @Override public void queueVariable(int level, Var v) { 717 718 if (impositionFailure) 719 return; 720 721 countQueueVariable++; 722 723 if (debugAll) { 724 if (countQueueVariable >= QUEUE_INFO_FROM) { 725 726 System.out.println("queueVariable is executed for the " + countQueueVariable + "-th time"); 727 System.out.println(displayQuantitiesInEfficiencyOrder()); 728 729 } 730 } 731 732 if (v == knapsackCapacity || v == knapsackProfit) { 733 734 if (inConsistency) 735 return; 736 737 needConsistency = true; 738 needForbidden = true; 739 needMandatory = true; 740 needUpdate = true; 741 needCriticalUpdate = true; 742 743 return; 744 } 745 746 final TreeLeaf leafForV = variableLeafMapping.get(v); 747 748 final boolean maxBoundHasChanged = leafForV.hasMaxChanged(); 749 final boolean minBoundHasChanged = leafForV.hasMinChanged(); 750 751 /* at least one bound has changed */ 752 if (maxBoundHasChanged || minBoundHasChanged) { 753 754 /* we test if a list exist and if it is different from null */ 755 List<TreeLeaf> list; 756 if ((list = hashForUpdate.get(level)) == null) { 757 list = new ArrayList<>(); 758 hashForUpdate.put(level, list); 759 positionOfAlreadyUpdated = 0; 760 } 761 762 if (list.size() > updateLimit) { 763 /* we don't add, we recompute */ 764 } else { 765 list.add(leafForV); 766 } 767 768 needUpdate = true; 769 770 } 771 772 if (inConsistency) 773 return; 774 775 //@TODO What if item changed is critical, make sure the code is correct in that case. 776 777 final boolean rightToCrit = leafForV.positionInTheTree > positionOfCriticalItem.value(); 778 779 final boolean leftToCrit = leafForV.positionInTheTree < positionOfCriticalItem.value(); 780 781 assert (!(leftToCrit && rightToCrit)) : "Error, a leaf cannot be right and left to the critical "; 782 783 /* we look if there is some changed to do */ 784 if (maxBoundHasChanged) { 785 /* for max decreased of mandatory items */ 786 if (leftToCrit) { 787 needConsistency = true; 788 needMandatory = true; 789 needForbidden = true; 790 needCriticalUpdate = true; 791 } 792 /* for max decreased of forbidden items */ 793 else { 794 needConsistency = true; 795 if (leafForV.positionInTheTree <= tree.criticalRightLeaf) 796 needMandatory = true; 797 } 798 } 799 800 if (minBoundHasChanged) { 801 /* for min increased of mandatory items */ 802 if (leftToCrit) { 803 needConsistency = true; 804 if (leafForV.positionInTheTree >= tree.criticalLeftLeaf) 805 needForbidden = true; 806 } 807 /* for min increased of forbidden items */ 808 else { 809 needConsistency = true; 810 needMandatory = true; 811 needForbidden = true; 812 needCriticalUpdate = true; 813 } 814 } 815 816 } 817 818 @Override public int numberArgs() { 819 return items.length + 2; 820 } 821 822 @Override public int getDefaultConsistencyPruningEvent() { 823 return IntDomain.BOUND; 824 } 825 826 @Override public boolean satisfied() { 827 828 if (!knapsackProfit.singleton()) 829 return false; 830 831 if (!knapsackCapacity.singleton()) 832 return false; 833 834 if (tree.root.getWSum() != 0) 835 return false; 836 837 if (tree.alreadyObtainedProfit != knapsackProfit.value()) 838 return false; 839 840 if (tree.alreadyUsedCapacity != knapsackCapacity.value()) 841 return false; 842 843 return true; 844 } 845 846 847 848 @Override public String toString() { 849 850 StringBuilder result = new StringBuilder(); 851 852 result.append(id() + " : Knapsack( ["); 853 for (int i = 0; i < items.length; i++) { 854 result.append(items[i].toString()); 855 if (i < items.length - 1) 856 result.append(", "); 857 } 858 result.append("], Capacity: ").append(knapsackCapacity); 859 result.append(", Profit: ").append(knapsackProfit); 860 result.append("])"); 861 862 return result.toString(); 863 864 } 865 866 867 /** 868 * It checks that the minimal values of items are contributing 869 * correctly towards tree already obtained profit, as well as 870 * already used capacity. 871 * 872 * @return true to specify that invariants are maintained correctly. 873 */ 874 private boolean sliceInvariant() { 875 876 int alreadyObtainedProfit = 0, alreadyUsedCapacity = 0; 877 878 for (TreeLeaf leave : leaves) 879 if (leave.slice > 0) { 880 alreadyObtainedProfit += leave.slice * leave.getProfitOfOne(); 881 alreadyUsedCapacity += leave.slice * leave.getWeightOfOne(); 882 } 883 884 assert (alreadyObtainedProfit == tree.alreadyObtainedProfit) : "Already obtained profit is not correctly maintained."; 885 886 assert (alreadyUsedCapacity == tree.alreadyUsedCapacity) : "Already used capacity is not correctly maintained."; 887 888 return true; 889 890 } 891 892 private String displayQuantitiesInEfficiencyOrder() { 893 894 StringBuilder result = new StringBuilder(); 895 896 result.append("[ "); 897 898 for (KnapsackItem item : items) 899 result.append(item.getVariable().domain).append(" "); 900 901 result.append("]"); 902 903 return result.toString(); 904 905 } 906 907 /** 908 * It verifies that leaves within tree have properly reflected slice variables 909 * within the items. 910 */ 911 private boolean checkInvariants() { 912 913 for (TreeLeaf leaf : leaves) 914 assert (leaf.slice == leaf.quantity.min()) : "Slice variable has not been adjusted to leaf quantity" + leaf.toString(); 915 916 int overallProfit = 0; 917 int overallCapacity = 0; 918 int maxLeafCapacity = 0; 919 920 for (TreeLeaf leaf : leaves) { 921 overallProfit += leaf.getPSum(); 922 overallCapacity += leaf.getWSum(); 923 maxLeafCapacity = Math.max(maxLeafCapacity, leaf.getWMax()); 924 } 925 926 assert (overallProfit == tree.root.getPSum()) : "Sum of profits for the tree does not reflect the quantity variables state"; 927 assert (overallCapacity == tree.root.getWSum()) : "Sum of capacities for the tree does not reflect the quantity variables state"; 928 assert (maxLeafCapacity == tree.root.getWMax()) : "Max of capacities for the tree does not reflect the quantity variables state"; 929 930 return true; 931 } 932 933 } 934