|
| Generated on: Thu Mar 29 07:46:58 PDT 2012 for custom file set | ||
|
||
| // doxy/ or-tools/ src/ algorithms/ |
#include <knapsack_solver.h>
Public Member Functions | |
| KnapsackCapacityPropagator (const KnapsackState &state, int64 capacity) | |
| KnapsackCapacityPropagator. | |
| virtual | ~KnapsackCapacityPropagator () |
| virtual void | ComputeProfitBounds () |
| virtual int | GetNextItemId () const |
| Returns the id of next item to assign. | |
Protected Member Functions | |
| virtual void | InitPropagator () |
| Initializes KnapsackCapacityPropagator (eg. | |
| virtual bool | UpdatePropagator (bool revert, const KnapsackAssignment &assignment) |
| Updates internal data structure incrementally (ie. | |
| virtual void | CopyCurrentStateToSolutionPropagator (std::vector< bool > *solution) const |
| Copies the current state into 'solution'. | |
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 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 Greenbreg & 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 both in ComputeProfitBounds and CopyCurrentSolutionPropagator. For incrementality reasons, the ith item should be accessible in O(1). That's the reason why item vector has to be duplicated 'sorted_items_'.
Definition at line 429 of file knapsack_solver.h.
| operations_research::KnapsackCapacityPropagator::KnapsackCapacityPropagator | ( | const KnapsackState & | state, | |
| int64 | capacity | |||
| ) |
| operations_research::KnapsackCapacityPropagator::~KnapsackCapacityPropagator | ( | ) | [virtual] |
Definition at line 232 of file knapsack_solver.cc.
| void operations_research::KnapsackCapacityPropagator::ComputeProfitBounds | ( | ) | [virtual] |
Implements operations_research::KnapsackPropagator.
Definition at line 237 of file knapsack_solver.cc.
| virtual int operations_research::KnapsackCapacityPropagator::GetNextItemId | ( | ) | const [inline, virtual] |
Returns the id of next item to assign.
Returns kNoSelection when all items are bound.
Implements operations_research::KnapsackPropagator.
Definition at line 434 of file knapsack_solver.h.
| void operations_research::KnapsackCapacityPropagator::InitPropagator | ( | ) | [protected, virtual] |
Initializes KnapsackCapacityPropagator (eg.
sort items in decreasing order).
Implements operations_research::KnapsackPropagator.
Definition at line 268 of file knapsack_solver.cc.
| bool operations_research::KnapsackCapacityPropagator::UpdatePropagator | ( | bool | revert, | |
| const KnapsackAssignment & | assignment | |||
| ) | [protected, virtual] |
Updates internal data structure incrementally (ie.
Returns false when the propagator fails.
'consumed_capacity_') to avoid a O(number_of_items) scan.
Implements operations_research::KnapsackPropagator.
Definition at line 283 of file knapsack_solver.cc.
| void operations_research::KnapsackCapacityPropagator::CopyCurrentStateToSolutionPropagator | ( | std::vector< bool > * | solution | ) | const [protected, virtual] |
Copies the current state into 'solution'.
Only unbound items have to be copied as CopyCurrentSolution was already called with current state. This method is useful when a propagator is able to find a better solution than the blind instantiation to false of unbound items.
Implements operations_research::KnapsackPropagator.
Definition at line 299 of file knapsack_solver.cc.