Lower Bounds on the Complexity of Mixed-Integer Programs for Stable Set and Knapsack.
Jamico SchadeMakrand SinhaStefan WeltgePublished in: IPCO (2024)
Keyphrases
- stable set
- lower bound
- upper bound
- mixed integer program
- feasible solution
- cutting plane
- worst case
- lagrangian relaxation
- optimal solution
- objective function
- branch and bound
- branch and bound algorithm
- dynamic programming
- computational complexity
- np hard
- mixed integer
- knapsack problem
- lower and upper bounds
- randomly generated
- lot sizing
- optimization problems
- integer programming
- decision problems
- special case
- valid inequalities
- linear programming
- graphical models