Lower Bounds on the Complexity of Mixed-Integer Programs for Stable Set and Knapsack.
Jamico SchadeMakrand SinhaStefan WeltgePublished in: CoRR (2023)
Keyphrases
- stable set
- lower bound
- upper bound
- feasible solution
- mixed integer program
- lagrangian relaxation
- worst case
- cutting plane
- objective function
- knapsack problem
- optimal solution
- linear programming relaxation
- lower and upper bounds
- computational complexity
- branch and bound algorithm
- mixed integer
- linear programming
- dynamic programming
- branch and bound
- randomly generated
- traveling salesman problem
- linear program
- valid inequalities