A Branch-and-Bound Algorithm for the Knapsack Problem with Conflict Graph.
Andrea BettinelliValentina CacchianiEnrico MalagutiPublished in: INFORMS J. Comput. (2017)
Keyphrases
- branch and bound algorithm
- knapsack problem
- optimal solution
- np hard
- branch and bound
- combinatorial optimization problems
- test problems
- lower bound
- combinatorial optimization
- optimization problems
- precedence constraints
- lower bounding
- linear programming
- randomly generated problems
- exact algorithms
- upper bounding
- combinatorial problems
- lagrangian relaxation
- multidimensional knapsack problem
- objective function
- special case
- dynamic programming
- upper bound
- linear program
- approximation algorithms
- np complete
- production planning
- linear programming relaxation
- scheduling problem
- max sat
- mixed integer linear programming
- solution quality
- search space
- cutting plane
- single machine scheduling problem
- finding an optimal solution
- search algorithm
- greedy algorithm
- metaheuristic
- integer programming
- feasible solution
- constraint satisfaction problems
- integer variables
- neural network