s-free sets

Intersection Cuts for Mixed-Integer Nonlinear Programs via Decision-Diagram-Free Sets

Categories (Mixed) Integer Nonlinear Programming, Cutting Plane Approaches, Global Optimization Tags , , , , ,

We introduce a novel decision-diagram-based framework for generating intersection cuts to strengthen polyhedral relaxations of bounded mixed-integer nonlinear programs (MINLPs) with general nonlinear constraints. Building on decision diagrams (DDs) that provide outer approximations of MINLP feasible regions, we propose the concept of DD-free sets, which are convex regions whose interiors do not intersect the sets … Read more

On a generalization of the Chvatal-Gomory closure

Categories Cutting Plane Approaches, Integer Programming Tags , , , , ,

Many practical integer programming problems involve variables with one or two-sided bounds. Dunkel and Schulz (2012) considered a strengthened version of Chvatal-Gomory (CG) inequalities that use 0-1 bounds on variables, and showed that the set of points in a rational polytope that satisfy all these strengthened inequalities is a polytope. Recently, we generalized this result … Read more

Outer-Product-Free Sets for Polynomial Optimization and Oracle-Based Cuts

Categories Constrained Nonlinear Optimization, Cutting Plane Approaches, Global Optimization Theory Tags , ,

Cutting planes are derived from specific problem structures, such as a single linear constraint from an integer program. This paper introduces cuts that involve minimal structural assumptions, enabling the generation of strong polyhedral relaxations for a broad class of problems. We consider valid inequalities for the set $S\cap P$, where $S$ is a closed set, … Read more