Stay organized with collections
Save and categorize content based on your preferences.
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_'.
[[["Easy to understand","easyToUnderstand","thumb-up"],["Solved my problem","solvedMyProblem","thumb-up"],["Other","otherUp","thumb-up"]],[["Missing the information I need","missingTheInformationINeed","thumb-down"],["Too complicated / too many steps","tooComplicatedTooManySteps","thumb-down"],["Out of date","outOfDate","thumb-down"],["Samples / code issue","samplesCodeIssue","thumb-down"],["Other","otherDown","thumb-down"]],["Last updated 2024-08-06 UTC."],[[["KnapsackCapacityPropagator enforces knapsack capacity constraints by acting as a 0-1 Knapsack solver to compute profit bounds and guide item selection."],["It efficiently determines the profit upper bound by iterating through items sorted by profit-per-unit-weight, identifying a \"break item\" exceeding capacity."],["For single propagator scenarios, the class provides an improved profit lower bound calculation during the break item search."],["Items are stored in a duplicated, sorted manner (`sorted_items_`) for efficient O(1) access during incremental operations."]]],["`KnapsackCapacityPropagator` enforces capacity constraints as a 0-1 Knapsack solver. It iterates on items in decreasing profit-per-unit-weight order to compute upper bounds. The break item, where remaining capacity is insufficient, is selected as the next item. Unbound items are added during the break element scan to enhance profit lower bounds. Key methods include `ComputeProfitBounds`, `GetNextItemId`, and the constructor/destructor. A sorted, duplicated item vector ensures O(1) item access.\n"]]
