C++ Reference: class KnapsackPropagatorForCuts

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_'.
Method
ComputeProfitBounds

Return type: void

ComputeProfitBounds should set 'profit_lower_bound_' and 'profit_upper_bound_' which are constraint specific.

CopyCurrentStateToSolution

Return type: void

Arguments: std::vector<bool>* solution

Copies the current state into 'solution'. All unbound items are set to false (i.e. not in the knapsack).

current_profit

Return type: double

GetNextItemId

Return type: int

Returns the id of next item to assign. Returns kNoSelection when all items are bound.

Init

Return type: void

Arguments: const std::vector<double>& profits, const std::vector<double>& weights, double capacity

Initializes the data structure and then calls InitPropagator.

InitPropagator

Return type: void

Initializes the propagator. This method is called by Init() after filling the fields defined in this class.

items

Return type: const std::vector<KnapsackItemForCutsPtr>&

KnapsackPropagatorForCuts

Return type: explicit

Arguments: const KnapsackStateForCuts* state

~KnapsackPropagatorForCuts

KnapsackPropagatorForCuts

Arguments: const KnapsackPropagatorForCuts&) = delete; KnapsackPropagatorForCuts& operator=(const KnapsackPropagatorForCuts&) = delete; // Initializes the data structure and then calls InitPropagator. void Init(const std::vector<double>& profits, const std::vector<double>& weights, double capacity

profit_lower_bound

Return type: double

profit_upper_bound

Return type: double

set_profit_lower_bound

Return type: void

Arguments: double profit

set_profit_upper_bound

Return type: void

Arguments: double profit

state

Return type: const KnapsackStateForCuts&

Update

Return type: bool

Arguments: bool revert, const KnapsackAssignmentForCuts& assignment

Updates data structure. Returns false on failure.