Polyhedra

LP and SDP Branch-and-Cut Algorithms for the Minimum Graph Bisection Problem: A Computational Comparison

  • Marzena Fuegenschuh
  • Christoph Helmberg
  • Alexander Martin
    • Categories Branch and Cut Algorithms, Polyhedra Tags , , ,

    While semidefinite relaxations are known to deliver good approximations for combinatorial optimization problems like graph bisection, their practical scope is mostly associated with small dense instances. For large sparse instances, cutting plane techniques are considered the method of choice. These are also applicable for semidefinite relaxations via the spectral bundle method, which allows to exploit … Read more

    Recoverable Robust Knapsack: the Discrete Scenario Case

  • Christina Büsing
  • Arie M.C.A. Koster
  • Manuel Kutschka
    • Categories Cutting Plane Approaches, Polyhedra, Robust Optimization Tags , , ,

    Admission control problems have been studied extensively in the past. In a typical setting, resources like bandwidth have to be distributed to the different customers according to their demands maximizing the profit of the company. Yet, in real-world applications those demands are deviating and in order to satisfy their service requirements often a robust approach … Read more

    The Time Dependent Traveling Salesman Problem: Polyhedra and Algorithm

  • Hernan Abeledo
  • Ricardo Fukasawa
  • Artur Alves Pessoa
  • Eduardo Uchoa
    • Categories Branch and Cut Algorithms, Polyhedra Tags ,

    The Time Dependent Traveling Salesman Problem (TDTSP) is a generalization of the classical Traveling Salesman Problem (TSP), where arc costs depend on their position in the tour with respect to the source node. While TSP instances with thousands of vertices can be solved routinely, there are very challenging TDTSP instances with less than 100 vertices. … Read more

    Integer-empty polytopes in the 0/1-cube with maximal Gomory-Chvátal rank

  • Sebastian Pokutta
  • Andreas S. Schulz
    • Categories 0-1 Programming, Cutting Plane Approaches, Polyhedra

    We provide a complete characterization of all polytopes P ⊆ [0,1]^n with empty integer hull whose Gomory-Chvátal rank is n (and, therefore, maximal). In particular, we show that the first Gomory- Chvátal closure of all these polytopes is identical. Article Download View Integer-empty polytopes in the 0/1-cube with maximal Gomory-Chvátal rank

    The Maximum k-Colorable Subgraph Problem and Orbitopes

  • Tim Januschowski
  • Marc E. Pfetsch
    • Categories Cutting Plane Approaches, Polyhedra Tags , , ,

    Given an undirected node-weighted graph and a positive integer k, the maximum k-colorable subgraph probem is to select a k-colorable induced subgraph of largest weight. The natural integer programming formulation for this problem exhibits a high degree of symmetry which arises by permuting the color classes. It is well known that such symmetry has negative … Read more

    Random half-integral polytopes

  • Gábor Braun
  • Sebastian Pokutta
    • Categories 0-1 Programming, Cutting Plane Approaches, Polyhedra Tags , , ,

    We show that half-integral polytopes obtained as the convex hull of a random set of half-integral points of the 0/1 cube have rank as high as Ω(logn/loglogn) with positive probability — even if the size of the set relative to the total number of half-integral points of the cube tends to 0. The high rank … Read more

    Facets of the minimum-adjacency vertex coloring polytope

  • Diego Delle Donne
  • Javier Marenco
    • Categories 0-1 Programming, Polyhedra Tags , ,

    In this work we study a particular way of dealing with interference in combinatorial optimization models representing wireless communication networks. In a typical wireless network, co-channel interference occurs whenever two overlapping antennas use the same frequency channel, and a less critical interference is generated whenever two overlapping antennas use adjacent channels. This motivates the formulation … 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

    Small bipartite subgraph polytopes

  • Laura Galli
  • Adam N. Letchford
    • Categories 0-1 Programming, Polyhedra Tags ,

    We compute a complete linear description of the bipartite subgraph polytope, for up to seven nodes, and a conjectured complete description for eight nodes. We then show how these descriptions were used to compute the integrality ratio of various relaxations of the max-cut problem, again for up to eight nodes. Citation L. Galli & A.N. … Read more

    An exact approach to the problem of extracting an embedded network matrix

  • Cid C. de Souza
  • Martine Labbé
  • R. M. V. Figueiredo
    • Categories Branch and Cut Algorithms, Network Optimization, Polyhedra Tags , , ,

    We study the problem of detecting a maximum embedded network submatrix in a {-1,0,+1}-matrix. Our aim is to solve the problem to optimality. We introduce a 0-1 integer linear formulation for this problem based on its representation over a signed graph. A polyhedral study is presented and a branch-and-cut algorithm is described for finding an … Read more