Automating cutting planes is NP-hard.
Mika GöösSajin KorothIan MertzToniann PitassiPublished in: STOC (2020)
Keyphrases
- cutting plane
- np hard
- integer programming
- lower bound
- knapsack problem
- cutting plane algorithm
- optimal solution
- column generation
- integer programming problems
- linear programming
- integer program
- special case
- multistage stochastic
- branch and bound algorithm
- approximation algorithms
- lagrangian relaxation
- upper bound
- linear program
- scheduling problem
- computational complexity
- mixed integer
- minimum cost
- dantzig wolfe decomposition
- valid inequalities
- np complete
- linear programming relaxation
- branch and bound
- data points
- lower and upper bounds