no-good cuts

Polyhedral Bounds for Forbidden-Vertices Sets and No-Good Cut Relaxations

Categories (Mixed) Integer Linear Programming, 0-1 Programming, Linear Programming Tags , ,

We study the convex hull obtained after deleting prescribed vertices from the binary cube. The analysis separates three regimes according to the number of deleted vertices. When this number is fixed, both the original-space facet count and the linear extension complexity remain linear in the ambient dimension, up to constants depending only on the number … Read more

Smoothie: Mixing the strongest MIP solvers to solve hard MIP instances on supercomputers – Phase I development

Categories (Mixed) Integer Linear Programming, Parallel Algorithms Tags , , ,

Mixed-Integer Linear Programming (MIP) is applicable to such a wide range of real-world decision problems that the competition for the best code to solve such problems has lead to tremendous progress over the last decades. While current solvers can solve some of the problems that seemed completely out-of-reach just 10 years ago, there are always … Read more