Stay organized with collections
Save and categorize content based on your preferences.
C++ Reference: class KnapsackPropagatorForCuts
Note: This documentation is automatically generated.
----- KnapsackPropagatorForCuts -----
KnapsackPropagatorForCuts is used to enforce a capacity constraint.
It 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.
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 CopyCurrentSolution(). 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."],[[["`KnapsackPropagatorForCuts` enforces knapsack capacity constraints by computing profit bounds and guiding item selection for a 0-1 knapsack problem."],["It prioritizes items with higher profit-per-unit-weight, using a \"break item\" strategy for efficient upper bound calculation."],["The class provides methods to compute profit bounds (`ComputeProfitBounds`), copy the solution state (`CopyCurrentStateToSolution`), and determine the next item for assignment (`GetNextItemId`)."],["For efficiency, the item data is duplicated and sorted, enabling O(1) access during computations and incrementality."],["It also computes a lower profit bound by considering unbound items during the break element search, enhancing the solution process."]]],["`KnapsackPropagatorForCuts` enforces a capacity constraint for a 0-1 knapsack problem, computing profit bounds and selecting items. It iterates on items in decreasing profit-per-unit-weight order, identifying a \"break item\" where capacity is exceeded. The class computes `profit_lower_bound_` and `profit_upper_bound_` via `ComputeProfitBounds`. It selects the next item to assign using `GetNextItemId` and updates the data structure via `Update`. The current state is copied to a solution vector with `CopyCurrentStateToSolution`. Items are initialized with `Init` and the propagator is initialized with `InitPropagator`.\n"]]
