Clique-based facets for the precedence constrained knapsack problem.
Natashia BolandAndreas BleyChristopher FrickeGary FroylandRenata SotirovPublished in: Math. Program. (2012)
Keyphrases
- knapsack problem
- combinatorial optimization problems
- optimal solution
- optimization problems
- dynamic programming
- multidimensional knapsack problem
- test problems
- np hard
- exact algorithms
- linear programming relaxation
- heuristic solution
- greedy algorithm
- bicriteria
- maximum weight
- np hard problems
- maximum profit
- cutting plane
- implicit enumeration
- randomly generated test instances
- decision variables
- upper bound
- lower bound