Juan Pablo Vielma

Small and Strong Formulations for Unions of Convex Sets from the Cayley Embedding

  • Juan Pablo Vielma
    • Categories (Mixed) Integer Nonlinear Programming, 0-1 Programming

    There is often a significant trade-off between formulation strength and size in mixed integer programming (MIP). When modeling convex disjunctive constraints (e.g. unions of convex sets), adding auxiliary continuous variables can sometimes help resolve this trade-off. However, standard formulations that use such auxiliary continuous variables can have a worse-than-expected computational effectiveness, which is often attributed … Read more

    A combinatorial approach for small and strong formulations of disjunctive constraints

  • Joey Huchette
  • Juan Pablo Vielma
    • Categories (Mixed) Integer Linear Programming Tags , ,

    We present a framework for constructing small, strong mixed-integer formulations for disjunctive constraints. Our approach is a generalization of the logarithmically-sized formulations of Vielma and Nemhauser for SOS2 constraints, and we offer a complete characterization of its expressive power. We apply the framework to a variety of disjunctive constraints, producing novel, small, and strong formulations … Read more

    Two-sided linear chance constraints and extensions

  • Daniel Bienstock
  • Miles Lubin
  • Juan Pablo Vielma
    • Categories Convex Optimization, Second-Order Cone Programming, Stochastic Programming

    We examine the convexity and tractability of the two-sided linear chance constraint model under Gaussian uncertainty. We show that these constraints can be applied directly to model a larger class of nonlinear chance constraints as well as provide a reasonable approximation for a challenging class of quadratic chance constraints of direct interest for applications in … Read more

    Beating the SDP bound for the floor layout problem: A simple combinatorial idea

  • Santanu S. Dey
  • Joey Huchette
  • Juan Pablo Vielma
    • Categories Facility Planning and Design, Integer Programming Tags ,

    For many Mixed-Integer Programming (MIP) problems, high-quality dual bounds can obtained either through advanced formulation techniques coupled with a state-of-the-art MIP solver, or through Semidefinite Programming (SDP) relaxation hierarchies. In this paper, we introduce an alternative bounding approach that exploits the “combinatorial implosion” effect by solving portions of the original problem and aggregating this information … Read more

    Strong mixed-integer formulations for the floor layout problem

  • Santanu S. Dey
  • Joey Huchette
  • Juan Pablo Vielma
    • Categories (Mixed) Integer Linear Programming, Facility Planning and Design Tags ,

    The floor layout problem (FLP) tasks a designer with positioning a collection of rectangular boxes on a fixed floor in such a way that minimizes total communication costs between the components. While several mixed integer programming (MIP) formulations for this problem have been developed, it remains extremely challenging from a computational perspective. This work takes … Read more

    Embedding Formulations and Complexity for Unions of Polyhedra

  • Juan Pablo Vielma
    • Categories (Mixed) Integer Linear Programming

    It is well known that selecting a good Mixed Integer Programming (MIP) formulation is crucial for an effective solution with state-of-the art solvers. While best practices and guidelines for constructing good formulations abound, there is rarely a systematic construction leading to the best possible formulation. We introduce embedding formulations and complexity as a new MIP … Read more

    Extended Formulations in Mixed Integer Conic Quadratic Programming

  • Iain Dunning
  • Joey Huchette
  • Juan Pablo Vielma
  • Miles Lubin
    • Categories (Mixed) Integer Nonlinear Programming

    In this paper we consider the use of extended formulations in LP-based algorithms for mixed integer conic quadratic programming (MICQP). Extended formulations have been used by Vielma, Ahmed and Nemhauser (2008) and Hijazi, Bonami and Ouorou (2013) to construct algorithms for MICQP that can provide a significant computational advantage. The first approach is based on … Read more

    Convex hull of two quadratic or a conic quadratic and a quadratic inequality

  • Sina Modaresi
  • Juan Pablo Vielma
    • Categories (Mixed) Integer Nonlinear Programming, Global Optimization Theory, Second-Order Cone Programming Tags , ,

    In this paper we consider an aggregation technique introduced by Yildiran, 2009 to study the convex hull of regions defined by two quadratic or by a conic quadratic and a quadratic inequality. Yildiran shows how to characterize the convex hull of open sets defined by two strict quadratic inequalities using Linear Matrix Inequalities (LMI). We … Read more

    On Blocking and Anti-Blocking Polyhedra in Infinite Dimensions

  • Luis Rademacher
  • Alejandro Toriello
  • Juan Pablo Vielma
    • Categories Graphs and Matroids, Infinite Dimensional Optimization, Polyhedra Tags , , ,

    We consider the natural generalizations of blocking and anti-blocking polyhedra in infinite dimensions, and study issues related to duality and integrality of extreme points for these sets. Using appropriate finite truncations, we give conditions under which complementary slackness holds for primal-dual pairs of the infi nite linear programming problems associated with infi nite blocking and anti-blocking polyhedra. … Read more

    Incremental and Encoding Formulations for Mixed Integer Programming

  • Juan Pablo Vielma
  • Sercan Yildiz
    • Categories (Mixed) Integer Linear Programming

    The standard way to represent a choice between n alternatives in Mixed Integer Programming is through n binary variables that add up to one. Unfortunately, this approach commonly leads to unbalanced branch-and-bound trees and diminished solver performance. In this paper, we present an encoding formulation framework that encompasses and expands existing approaches to mitigate this … Read more