Integer 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

    Outer Approximation With Conic Certificates For Mixed-Integer Convex Problems

  • Chris Coey
  • Miles Lubin
  • Juan Pablo Vielma
    • Categories (Mixed) Integer Nonlinear Programming, Linear, Cone and Semidefinite Programming, Optimization Software Benchmark Tags , ,

    A mixed-integer convex (MI-convex) optimization problem is one that becomes convex when all integrality constraints are relaxed. We present a branch-and-bound LP outer approximation algorithm for an MI-convex problem transformed to MI-conic form. The polyhedral relaxations are refined with K* cuts} derived from conic certificates for continuous primal-dual conic subproblems. Under the assumption that all … Read more

    Mixed-integer bilevel representability

  • Amitabh Basu
  • Christopher Thomas Ryan
  • Sriram Sankaranarayanan
    • Categories (Mixed) Integer Nonlinear Programming, Integer Programming Tags ,

    We study the representability of sets that admit extended formulations using mixed-integer bilevel programs. We show that feasible regions modeled by continuous bilevel constraints (with no integer variables), complementarity constraints, and polyhedral reverse convex constraints are all finite unions of polyhedra. Conversely, any finite union of polyhedra can be represented using any one of these … Read more

    On the Rational Polytopes with Chvatal Rank 1

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

    We study the following problem: given a rational polytope with Chvatal rank 1, does it contain an integer point? Boyd and Pulleyblank observed that this problem is in the complexity class NP ∩ co-NP, an indication that it is probably not NP-complete. It is open whether there is a polynomial time algorithm to solve the … 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

    Split cuts from sparse disjunctions

  • Ricardo Fukasawa
  • Laurent Poirrier
  • Shenghao Yang
    • Categories (Mixed) Integer Linear Programming, Cutting Plane Approaches Tags , , ,

    Split cuts are arguably the most effective class of cutting planes within a branch-and-cut framework for solving general Mixed-Integer Programs (MIP). Sparsity, on the other hand, is a common characteristic of MIP problems, and it is an important part of why the simplex method works so well inside branch-and-cut. In this work, we evaluate the … Read more

    Cutting Planes by Projecting Interior Points onto Polytope Facets

  • Daniel Porumbel
    • Categories Branch and Cut Algorithms, Cutting Plane Approaches, Linear Programming Tags , ,

    Given a point x inside a polytope P and a direction d, the projection of x along d asks to find the maximum step length t such that x+td is feasible; we say x+td is a pierce point because it belongs to the boundary of P. We address this projection sub-problem with arbitrary interior points … Read more

    All Cyclic Group Facets Inject

  • Matthias Köppe
  • Yuan Zhou
    • Categories Cutting Plane Approaches Tags

    We give a variant of Basu–Hildebrand–Molinaro’s approximation theorem for continuous minimal valid functions for Gomory–Johnson’s infinite group problem by piecewise linear two-slope extreme functions [Minimal cut-generating functions are nearly extreme, IPCO 2016]. Our theorem is for piecewise linear minimal valid functions that have only rational breakpoints (in 1/q Z for some q ∈ N) and … Read more