The precedence constrained knapsack problem: Separating maximally violated inequalities.
Daniel G. EspinozaMarcos GoycooleaEduardo MorenoPublished in: Discret. Appl. Math. (2015)
Keyphrases
- knapsack problem
- binary variables
- integer variables
- combinatorial optimization problems
- optimization problems
- optimal solution
- multidimensional knapsack problem
- np hard
- test problems
- dynamic programming
- sufficient conditions
- lp relaxation
- continuous relaxation
- exact algorithms
- greedy algorithm
- np hard problems
- production planning
- bicriteria
- cutting plane
- linear programming relaxation
- greedy heuristic
- mixed integer
- randomly generated test instances
- heuristic solution
- decision variables
- valid inequalities
- approximation algorithms
- special case
- maximum profit
- evolutionary algorithm