Alberto Del Pia

On the impact of running intersection inequalities for globally solving polynomial optimization problems

  • Alberto Del Pia
  • Aida Khajavirad
  • Nikolaos Sahinidis
    • Categories (Mixed) Integer Nonlinear Programming, Cutting Plane Approaches, Global Optimization Theory

    We consider global optimization of nonconvex problems whose factorable reformulations contain a collection of multilinear equations. Important special cases include multilinear and polynomial optimization problems. The multilinear polytope is the convex hull of a set of binary points satisfying a number of multilinear equations. Running intersection inequalities are a family of facet-defining inequalities for the … Read more

    On decomposability of the multilinear polytope and its implications in mixed-integer nonlinear optimization

  • Alberto Del Pia
  • Aida Khajavirad
    • Categories (Mixed) Integer Nonlinear Programming, 0-1 Programming, Global Optimization Theory Tags , , ,

    In this article, we provide an overview of some of our recent results on the facial structure of the multilinear polytope with a special focus on its decomposability properties. Namely, we demonstrate that, in the context of mixed-integer nonlinear optimization, the decomposability of the multilinear polytope plays a key role from both theoretical and algorithmic … Read more

    The running intersection relaxation of the multilinear polytope

  • Alberto Del Pia
  • Aida Khajavirad
    • Categories 0-1 Programming, Global Optimization Theory, Polyhedra

    The multilinear polytope MP_G of a hypergraph G is the convex hull of a set of binary points satisfying a collection of multilinear equations. We introduce the running-intersection inequalities, a new class of facet-defining inequalities for the multilinear polytope. Accordingly, we define a new polyhedral relaxation of MP_G referred to as the running-intersection relaxation and … Read more

    Subdeterminants and Concave Integer Quadratic Programming

  • Alberto Del Pia
    • Categories (Mixed) Integer Nonlinear Programming, Global Optimization Theory Tags , , , , ,

    We consider the NP-hard problem of minimizing a separable concave quadratic function over the integral points in a polyhedron, and we denote by D the largest absolute value of the subdeterminants of the constraint matrix. In this paper we give an algorithm that finds an epsilon-approximate solution for this problem by solving a number of … Read more

    Lower bounds on the lattice-free rank for packing and covering integer programs

  • Merve Bodur
  • Alberto Del Pia
  • Santanu S. Dey
  • Marco Molinaro
    • Categories Cutting Plane Approaches, Integer Programming Tags , , , , ,

    In this paper, we present lower bounds on the rank of the split closure, the multi-branch closure and the lattice-free closure for packing sets as a function of the integrality gap. We also provide a similar lower bound on the split rank of covering polyhedra. These results indicate that whenever the integrality gap is high, … Read more

    Characterizations of Mixed Binary Convex Quadratic Representable Sets

  • Alberto Del Pia
  • Jeffrey Poskin
    • Categories (Mixed) Integer Nonlinear Programming, Global Optimization Theory

    Representability results play a fundamental role in optimization since they provide characterizations of the feasible sets that arise from optimization problems. In this paper we study the sets that appear in the feasibility version of mixed binary convex quadratic optimization problems. We provide a complete characterization of the sets that can be obtained as the … Read more

    The Multilinear polytope for acyclic hypergraphs

  • Alberto Del Pia
  • Aida Khajavirad
    • Categories (Mixed) Integer Linear Programming, (Mixed) Integer Nonlinear Programming, Global Optimization Theory Tags , , , ,

    We consider the Multilinear polytope defined as the convex hull of the set of binary points satisfying a collection of multilinear equations. Such sets are of fundamental importance in many types of mixed-integer nonlinear optimization problems, such as binary polynomial optimization. Utilizing an equivalent hypergraph representation, we study the facial structure of the Multilinear polytope … Read more

    Aggregation-based cutting-planes for packing and covering integer programs

  • Merve Bodur
  • Alberto Del Pia
  • Santanu S. Dey
  • Sebastian Pokutta
  • Marco Molinaro
    • Categories Cutting Plane Approaches, Integer Programming Tags , , , ,

    In this paper, we study the strength of Chvatal-Gomory (CG) cuts and more generally aggregation cuts for packing and covering integer programs (IPs). Aggregation cuts are obtained as follows: Given an IP formulation, we first generate a single implied inequality using aggregation of the original constraints, then obtain the integer hull of the set defined … Read more

    Ellipsoidal Mixed-Integer Representability

  • Alberto Del Pia
  • Jeffrey Poskin
    • Categories (Mixed) Integer Nonlinear Programming, Global Optimization Theory

    Representability results for mixed-integer linear systems play a fundamental role in optimization since they give geometric characterizations of the feasible sets that can be formulated by mixed-integer linear programming. We consider a natural extension of mixed-integer linear systems obtained by adding just one ellipsoidal inequality. The set of points that can be described, possibly using … Read more

    On Decomposability of Multilinear Sets

  • Alberto Del Pia
  • Aida Khajavirad
    • Categories (Mixed) Integer Nonlinear Programming, Global Optimization Theory, Polyhedra

    In this paper, we consider the Multilinear set defined as the set of binary points satisfying a collection of multilinear equations. Such sets appear in factorable reformulations of many types of nonconvex optimization problems, including binary polynomial optimization. A great simplification in studying the facial structure of the convex hull of the Multilinear set is … Read more