0-1 Programming

On Solving Two-Stage Distributionally Robust Disjunctive Programs with a General Ambiguity Set

  • Manish Bansal
  • Sanjay Mehrotra
    • Categories 0-1 Programming, Stochastic Programming

    We introduce two-stage distributionally robust disjunctive programs (TSDR-DPs) with disjunctive constraints in both stages and a general ambiguity set for the probability distributions. The TSDR-DPs subsume various classes of two-stage distributionally robust programs where the second stage problems are non-convex programs (such as mixed binary programs, semi-continuous program, nonconvex quadratic programs, separable non-linear programs, etc.). … Read more

    Mixed-Integer Programming Techniques for the Connected Max-k-Cut Problem

  • Christopher Hojny
  • Imke Joormann
  • Martin Schmidt
  • Hendrik Lüthen
    • Categories (Mixed) Integer Linear Programming, 0-1 Programming, Branch and Cut Algorithms Tags , , ,

    We consider an extended version of the classical Max-k-Cut problem in which we additionally require that the parts of the graph partition are connected. For this problem we study two alternative mixed-integer linear formulations and review existing as well as develop new branch-and-cut techniques like cuts, branching rules, propagation, primal heuristics, and symmetry breaking. The … Read more

    Decentralized Algorithms for Distributed Integer Programming Problems with a Coupling Cardinality Constraint

  • Shabbir Ahmed
  • George L. Nemhauser
  • Ezgi Karabulut
    • Categories 0-1 Programming, Parallel Algorithms Tags , ,

    We consider a multi-player optimization where each player has her own optimization problem and the individual problems are connected by a cardinality constraint on their shared resources. We give distributed algorithms that allow each player to solve their own optimization problem and still achieve a global optimization solution for problems that possess a concavity property. … Read more

    A Lagrange decomposition based Branch and Bound algorithm for the Optimal Mapping of Cloud Virtual Machines

  • Walid Ben-Ameur
  • Adam Ouorou
  • Guanglei Wang
    • Categories 0-1 Programming, Applications - OR and Management Sciences, Branch and Cut Algorithms Tags , , ,

    One of the challenges of cloud computing is to optimally and efficiently assign virtual machines to physical machines. The aim of telecommunication operators is to mini- mize the mapping cost while respecting constraints regarding location, assignment and capacity. In this paper we first propose an exact formulation leading to a 0-1 bilinear constrained problem. Then … 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

    Distributionally Robust Linear and Discrete Optimization with Marginals

  • Louis Chen
  • Karthik Natarajan
  • David Simchi-Levi
  • Will Ma
  • Zhenzhen Yan
    • Categories 0-1 Programming, Applications - OR and Management Sciences, Polyhedra Tags , ,

    In this paper, we study the class of linear and discrete optimization problems in which the objective coefficients are chosen randomly from a distribution, and the goal is to evaluate robust bounds on the expected optimal value as well as the marginal distribution of the optimal solution. The set of joint distributions is assumed to … Read more

    On the Consistent Path Problem

  • David Bergman
  • Leonardo Lozano
  • Cole Smith
    • Categories 0-1 Programming, Combinatorial Optimization, Cutting Plane Approaches

    The application of decision diagrams in combinatorial optimization has proliferated in the last decade. In recent years, authors have begun to investigate how to utilize not one, but a set of diagrams, to model constraints and objective function terms. Optimizing over a collection of decision diagrams, the problem we refer to as the consistent path … Read more

    Network Models for Multiobjective Discrete Optimization

  • David Bergman
  • Merve Bodur
  • Carlos Cardonha
  • Andre Augusto Cire
    • Categories 0-1 Programming, Dynamic Programming, Multi-Criteria Optimization

    This paper provides a novel framework for solving multiobjective discrete optimization problems with an arbitrary number of objectives. Our framework formulates these problems as network models, in that enumerating the Pareto frontier amounts to solving a multicriteria shortest path problem in an auxiliary network. We design tools and techniques for exploiting the network model in … Read more

    Binary Extended Formulations of Polyhedral Mixed-integer Sets

  • Sanjeeb Dash
  • Oktay Gunluk
  • Robert Hildebrand
    • Categories 0-1 Programming, Cutting Plane Approaches, Integer Programming Tags , , ,

    We analyze different ways of constructing binary extended formulations of polyhedral mixed-integer sets with bounded integer variables and compare their relative strength with respect to split cuts. We show that among all binary extended formulations where each bounded integer variable is represented by a distinct collection of binary variables, what we call “unimodular” extended formulations … Read more