Mohit Tawarmalani

Piecewise Polyhedral Relaxations of Multilinear Optimization

  • Jongeun Kim
  • Jean-Philippe P. Richard
  • Mohit Tawarmalani
    • Categories (Mixed) Integer Nonlinear Programming, Global Optimization Tags , , ,

    In this paper, we consider piecewise polyhedral relaxations (PPRs) of multilinear optimization problems over axis-parallel hyper-rectangular partitions of their domain. We improve formulations for PPRs by linking components that are commonly modeled independently in the literature. Numerical experiments with ALPINE, an open-source software for global optimization that relies on piecewise approximations of functions, show that … Read more

    A Reciprocity Between Tree Ensemble Optimization and Multilinear Optimization

  • Jongeun Kim
  • Jean-Philippe P. Richard
  • Mohit Tawarmalani
    • Categories (Mixed) Integer Nonlinear Programming Tags , , ,

    In this paper, we establish a polynomial equivalence between tree ensemble optimization and optimization of multilinear functions over the Cartesian product of simplices. We use this insight to derive new formulations for tree ensemble optimization problems and to obtain new convex hull results for multilinear polytopes. A computational experiment on multi-commodity transportation problems with costs … Read more

    Simultaneous convexification of bilinear functions over polytopes with application to network interdiction

  • Danial Davarnia
  • Jean-Philippe P. Richard
  • Mohit Tawarmalani
    • Categories (Mixed) Integer Nonlinear Programming, Global Optimization Theory, Network Optimization

    We study the simultaneous convexification of graphs of bilinear functions that contain bilinear products between variables x and y, where x belongs to a general polytope and y belongs to a simplex. We propose a constructive procedure to obtain a linear description of the convex hull of the resulting set. This procedure can be applied … Read more

    Deriving the convex hull of a polynomial partitioning set through lifting and projection

  • Trang T. Nguyen
  • Jean-Philippe P. Richard
  • Mohit Tawarmalani
    • Categories (Mixed) Integer Nonlinear Programming, Global Optimization Theory Tags , ,

    Relaxations of the bilinear term, $x_1x_2=x_3$, play a central role in constructing relaxations of factorable functions. This is because they can be used directly to relax products of functions with known relaxations. In this paper, we provide a compact, closed-form description of the convex hull of this and other more general bivariate monomial terms (which … Read more

    Lifted Inequalities for 0−1 Mixed-Integer Bilinear Covering Sets

  • Kwanghun Chung
  • Jean-Philippe P. Richard
  • Mohit Tawarmalani
    • Categories (Mixed) Integer Nonlinear Programming, Cutting Plane Approaches, Global Optimization Theory Tags , ,

    In this paper, we study 0-1 mixed-integer bilinear covering sets. We derive several families of facet-defining inequalities via sequence-independent lifting techniques. We then show that these sets have polyhedral structures that are similar to those of certain fixed-charge single-node flow sets. As a result, we obtain new facet-defining inequalities for these sets that generalize well-known … Read more

    Inclusion Certificates and Simultaneous Convexification of Functions

  • Mohit Tawarmalani
    • Categories (Mixed) Integer Nonlinear Programming, 0-1 Programming, Global Optimization Theory Tags , , ,

    We define the inclusion certificate as a measure that expresses each point in the domain of a collection of functions as a convex combination of other points in the domain. Using inclusion certificates, we extend the convex extensions theory to enable simultaneous convexification of functions. We discuss conditions under which the domain of the functions … Read more

    Explicit Convex and Concave Envelopes through Polyhedral Subdivisions

  • Jean-Philippe P. Richard
  • Mohit Tawarmalani
  • Chuanhui Xiong
    • Categories (Mixed) Integer Nonlinear Programming, Global Optimization Theory, Polyhedra Tags , ,

    In this paper, we derive explicit characterizations of convex and concave envelopes of several nonlinear functions over various subsets of a hyper-rectangle. These envelopes are obtained by identifying polyhedral subdivisions of the hyper-rectangle over which the envelopes can be constructed easily. In particular, we use these techniques to derive, in closed-form, the concave envelopes of … Read more

    Strong Valid Inequalities for Orthogonal Disjunctions and Bilinear Covering Sets

  • Kwanghun Chung
  • Jean-Philippe P. Richard
  • Mohit Tawarmalani
    • Categories (Mixed) Integer Nonlinear Programming, Cutting Plane Approaches, Global Optimization Theory Tags , , , ,

    In this paper, we develop a convexification tool that enables the construction of convex hulls for orthogonal disjunctive sets using convex extensions and disjunctive programming techniques. A distinguishing feature of our technique is that, unlike most applications of disjunctive programming, it does not require the introduction of new variables in the relaxation. We develop and … Read more

    Lifting Inequalities: A framework for generating strong cuts in nonlinear programs

  • Jean-Philippe P. Richard
  • Mohit Tawarmalani
    • Categories Global Optimization, Integer Programming, Nonlinear Optimization Tags , , , , ,

    In this paper, we propose lifting techniques for generating strong cuts for nonlinear programs that are globally-valid. The theory is geometric and provides intuition into lifting-based cut generation procedures. As a special case, we find short proofs of earlier results on lifting techniques for mixed-integer programs. Using convex extensions, we obtain conditions that allow sequence-independent … Read more