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."],[[["\u003cp\u003e\u003ccode\u003eKnapsackPropagatorForCuts\u003c/code\u003e enforces knapsack capacity constraints by computing profit bounds and guiding item selection for a 0-1 knapsack problem.\u003c/p\u003e\n"],["\u003cp\u003eIt prioritizes items with higher profit-per-unit-weight, using a "break item" strategy for efficient upper bound calculation.\u003c/p\u003e\n"],["\u003cp\u003eThe class provides methods to compute profit bounds (\u003ccode\u003eComputeProfitBounds\u003c/code\u003e), copy the solution state (\u003ccode\u003eCopyCurrentStateToSolution\u003c/code\u003e), and determine the next item for assignment (\u003ccode\u003eGetNextItemId\u003c/code\u003e).\u003c/p\u003e\n"],["\u003cp\u003eFor efficiency, the item data is duplicated and sorted, enabling O(1) access during computations and incrementality.\u003c/p\u003e\n"],["\u003cp\u003eIt also computes a lower profit bound by considering unbound items during the break element search, enhancing the solution process.\u003c/p\u003e\n"]]],["`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"],null,["# KnapsackPropagatorForCuts\n\nC++ Reference: class KnapsackPropagatorForCuts\n==============================================\n\n\nNote: This documentation is automatically generated.\n\n----- KnapsackPropagatorForCuts ----- \nKnapsackPropagatorForCuts 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). \n\nThis is exactly what is implemented in this class. \n\nIt 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_'.\n\n| Method ||\n|---------------------------------------------------------------------------------------------------------------------------------|----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------|\n| [`ComputeProfitBounds`](https://github.com/google/or-tools/blob/v9.4/ortools/algorithms/knapsack_solver_for_cuts.h#L249) | Return type: `void ` ComputeProfitBounds should set 'profit_lower_bound_' and 'profit_upper_bound_' which are constraint specific. |\n| [`CopyCurrentStateToSolution`](https://github.com/google/or-tools/blob/v9.4/ortools/algorithms/knapsack_solver_for_cuts.h#L260) | Return type: `void ` Arguments: `std::vector\u003cbool\u003e* solution` Copies the current state into 'solution'. All unbound items are set to false (i.e. not in the knapsack). |\n| [`current_profit`](https://github.com/google/or-tools/blob/v9.4/ortools/algorithms/knapsack_solver_for_cuts.h#L254) | Return type: `double ` \u003cbr /\u003e |\n| [`GetNextItemId`](https://github.com/google/or-tools/blob/v9.4/ortools/algorithms/knapsack_solver_for_cuts.h#L252) | Return type: `int ` Returns the id of next item to assign. Returns kNoSelection when all items are bound. |\n| [`Init`](https://github.com/google/or-tools/blob/v9.4/ortools/algorithms/knapsack_solver_for_cuts.h#L242) | Return type: `void ` Arguments: `const std::vector\u003cdouble\u003e& profits, const std::vector\u003cdouble\u003e& weights, double capacity` Initializes the data structure and then calls InitPropagator. |\n| [`InitPropagator`](https://github.com/google/or-tools/blob/v9.4/ortools/algorithms/knapsack_solver_for_cuts.h#L264) | Return type: `void ` Initializes the propagator. This method is called by Init() after filling the fields defined in this class. |\n| [`items`](https://github.com/google/or-tools/blob/v9.4/ortools/algorithms/knapsack_solver_for_cuts.h#L267) | Return type: `const std::vector\u003cKnapsackItemForCutsPtr\u003e& ` \u003cbr /\u003e |\n| [`KnapsackPropagatorForCuts`](https://github.com/google/or-tools/blob/v9.4/ortools/algorithms/knapsack_solver_for_cuts.h#L234) | Return type: `explicit ` Arguments: `const KnapsackStateForCuts* state` \u003cbr /\u003e |\n| [`~KnapsackPropagatorForCuts`](https://github.com/google/or-tools/blob/v9.4/ortools/algorithms/knapsack_solver_for_cuts.h#L235) | \u003cbr /\u003e |\n| [`KnapsackPropagatorForCuts`](https://github.com/google/or-tools/blob/v9.4/ortools/algorithms/knapsack_solver_for_cuts.h#L237) | \u003cbr /\u003e Arguments: `const KnapsackPropagatorForCuts&) = delete; KnapsackPropagatorForCuts& operator=(const KnapsackPropagatorForCuts&) = delete; // Initializes the data structure and then calls InitPropagator. void Init(const std::vector\u003cdouble\u003e& profits, const std::vector\u003cdouble\u003e& weights, double capacity` \u003cbr /\u003e |\n| [`profit_lower_bound`](https://github.com/google/or-tools/blob/v9.4/ortools/algorithms/knapsack_solver_for_cuts.h#L255) | Return type: `double ` \u003cbr /\u003e |\n| [`profit_upper_bound`](https://github.com/google/or-tools/blob/v9.4/ortools/algorithms/knapsack_solver_for_cuts.h#L256) | Return type: `double ` \u003cbr /\u003e |\n| [`set_profit_lower_bound`](https://github.com/google/or-tools/blob/v9.4/ortools/algorithms/knapsack_solver_for_cuts.h#L269) | Return type: `void ` Arguments: `double profit` \u003cbr /\u003e |\n| [`set_profit_upper_bound`](https://github.com/google/or-tools/blob/v9.4/ortools/algorithms/knapsack_solver_for_cuts.h#L270) | Return type: `void ` Arguments: `double profit` \u003cbr /\u003e |\n| [`state`](https://github.com/google/or-tools/blob/v9.4/ortools/algorithms/knapsack_solver_for_cuts.h#L266) | Return type: `const KnapsackStateForCuts& ` \u003cbr /\u003e |\n| [`Update`](https://github.com/google/or-tools/blob/v9.4/ortools/algorithms/knapsack_solver_for_cuts.h#L246) | Return type: `bool ` Arguments: `bool revert, const KnapsackAssignmentForCuts& assignment` Updates data structure. Returns false on failure. |"]]
