operations_research::KnapsackAssignment Struct Reference
The following code defines needed classes for the
KnapsackGenericSolver class which is the entry point to extend knapsack with new constraints such as conflicts between items.
More...
#include <knapsack_solver.h>
List of all members.
Detailed Description
The following code defines needed classes for the
KnapsackGenericSolver class which is the entry point to extend knapsack with new constraints such as conflicts between items.
Constraints are enforced using KnapsackPropagator objects, in the current code there is one propagator per dimension (KnapsackCapacityPropagator). One of those propagators, named master propagator, is used to guide the search, i.e. decides which item should be assigned next. Roughly speaking the search algorithm is:
- While not optimal
- Select next search node to expand
- Select next item_i to assign (using master propagator)
- Generate a new search node where item_i is in the knapsack
- Check validity of this new partial solution (using propagators)
- If valid, add this new search node to the search
- Generate a new search node where item_i is not in the knapsack
- Check validity of this new partial solution (using propagators)
- If valid, add this new search node to the search
- Todo:
- TODO(user): Add a new propagator class for conflict constraint.
- Todo:
- TODO(user): Add a new propagator class used as a guide when the problem has several dimensions.
KnapsackAssignement KnapsackAssignement is a small struct used to pair an item with its assignment. It is mainly used for search nodes and updates.
Definition at line 191 of file knapsack_solver.h.
Constructor & Destructor Documentation
| operations_research::KnapsackAssignment::KnapsackAssignment |
( |
int |
_item_id, |
|
|
bool |
_is_in | |
|
) |
| | [inline] |
Member Data Documentation
The documentation for this struct was generated from the following file:
