C++ Reference: class KnapsackCapacityPropagator
Note: This documentation is automatically generated.
----- KnapsackCapacityPropagator -----
KnapsackCapacityPropagator is a KnapsackPropagator used to enforce a capacity constraint. As a KnapsackPropagator is supposed to compute profit lower and upper bounds, and get the next item to select, it can be seen as a 0-1 Knapsack solver. The most efficient way to compute the upper bound is to iterate on items in profit-per-unit-weight decreasing order. The break item is commonly defined as the first item for which there is not enough remaining capacity. Selecting this break item as the next-item-to-assign usually gives the best results (see Greenberg & Hegerich).
This is exactly what is implemented in this class.
When there is only one propagator, it is possible to compute a better profit lower bound almost for free. During the scan to find the break element all unbound items are added just as if they were part of the current solution. This is used in both ComputeProfitBounds and CopyCurrentSolutionPropagator. For incrementality reasons, the ith item should be accessible in O(1). That's the reason why the item vector has to be duplicated 'sorted_items_'.
| Method | |
|---|---|
ComputeProfitBounds | Return type: |
GetNextItemId | Return type: |
KnapsackCapacityPropagator | Arguments: |
~KnapsackCapacityPropagator | |