Random Θ(log n)-CNFs Are Hard for Cutting Planes.
Noah FlemingDenis PankratovToniann PitassiRobert RoberePublished in: FOCS (2017)
Keyphrases
- cutting plane
- lower bound
- random instances
- integer programming
- cutting plane algorithm
- integer programming problems
- knapsack problem
- integer program
- upper bound
- column generation
- branch and bound algorithm
- valid inequalities
- mixed integer
- feature space
- np hard
- linear programming
- optimal solution
- constraint satisfaction
- constraint satisfaction problems
- recursive least squares
- dantzig wolfe decomposition