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

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.