An Out-of-Core Branch and Bound Method for Solving the 0-1 Knapsack Problem on a GPU.
Jingcheng ShenKentaro ShigeokaFumihiko InoKenichi HagiharaPublished in: ICA3PP (2017)
Keyphrases
- knapsack problem
- branch and bound method
- branch and bound
- optimal solution
- randomly generated test instances
- implicit enumeration
- branch and bound algorithm
- combinatorial optimization problems
- combinatorial optimization
- optimization problems
- np hard
- mixed integer programming
- integer variables
- lp relaxation
- dynamic programming
- exact algorithms
- production planning
- lower bound
- feasible solution
- linear programming relaxation
- multidimensional knapsack problem
- greedy algorithm
- optimal configuration
- reduce the search space
- continuous relaxation
- maximum profit
- traveling salesman problem
- mixed integer
- upper bound
- evolutionary algorithm
- search space