0-1 Programming

An Integer Programming Formulation of the Key Management Problem in Wireless Sensor Networks

  • Maciej Rysz
  • Alexander Semenov
  • Guanglin Xu
    • Categories 0-1 Programming, Multidisciplinary Design Optimization, Telecommunications Tags , , , ,

    With the advent of modern communications systems, much attention has been put on developing methods for securely transferring information between constituents of wireless sensor networks. To this effect, we introduce a mathematical programming formulation for the key management problem, which broadly serves as a mechanism for encrypting communications. In particular, an integer programming model of … Read more

    On Some Polytopes Contained in the 0,1 Hypercube that Have a Small Chvatal Rank

  • Gérard Cornuéjols
  • Dabeen Lee
    • Categories (Mixed) Integer Linear Programming, 0-1 Programming, Cutting Plane Approaches Tags , ,

    In this paper, we consider polytopes P that are contained in the unit hypercube. We provide conditions on the set of 0,1 vectors not contained in P that guarantee that P has a small Chvatal rank. Our conditions are in terms of the subgraph induced by these infeasible 0,1 vertices in the skeleton graph of … Read more

    On the NP-hardness of deciding emptiness of the split closure of a rational polytope in the 0,1 hypercube

  • Dabeen Lee
    • Categories (Mixed) Integer Linear Programming, 0-1 Programming, Cutting Plane Approaches Tags , ,

    Split cuts are prominent general-purpose cutting planes in integer programming. The split closure of a rational polyhedron is what is obtained after intersecting the half-spaces defined by all the split cuts for the polyhedron. In this paper, we prove that deciding whether the split closure of a rational polytope is empty is NP-hard, even when … Read more

    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