Integer Programming

Elementary polytopes with high lift-and-project ranks for strong positive semidefinite operators

  • Yu Hin (Gary) Au
  • Levent Tunçel
    • Categories 0-1 Programming, Convex Optimization, Semi-definite Programming Tags , , , , , ,

    We consider operators acting on convex subsets of the unit hypercube. These operators are used in constructing convex relaxations of combinatorial optimization problems presented as a 0,1 integer programming problem or a 0,1 polynomial optimization problem. Our focus is mostly on operators that, when expressed as a lift-and-project operator, involve the use of semidefiniteness constraints … Read more

    Decomposition of loosely coupled integer programs: A multiobjective perspective

  • Shabbir Ahmed
  • Merve Bodur
  • Natashia Boland
  • George L. Nemhauser
    • Categories Integer Programming, Multi-Criteria Optimization Tags , , ,

    We consider integer programming (IP) problems consisting of (possibly a large number of) subsystems and a small number of coupling constraints that link variables from different subsystems. Such problems are called loosely coupled or nearly decomposable. Motivated by recent developments in multiobjective programming (MOP), we develop a MOP-based decomposition algorithm to solve loosely coupled IPs. … Read more

    Improved Handling of Uncertainty and Robustness in Set Covering Problems

  • Christina Büsing
  • Dirk Degel
  • Arie M.C.A. Koster
  • Pascal Lutter
  • Brigitte Werners
    • Categories Applications - OR and Management Sciences, Cutting Plane Approaches, Robust Optimization Tags , , ,

    This paper studies the emergency service facility location problem in an uncertain environment. The main focus is the integration of uncertainty regarding the covered area due to uncertain traveling times. Previous approaches only consider either probabilistic or fuzzy optimization to cope with uncertainty. However, in many real-world problems the required statistical parameters are not precisely … Read more

    Extended Formulations and Branch-and-Cut Algorithms for the Black-and-White Traveling Salesman Problem

  • Luís Gouveia
  • Markus Leitner
  • Mario Ruthmair
    • Categories (Mixed) Integer Linear Programming, Branch and Cut Algorithms, Transportation

    In this paper we study integer linear programming models and develop branch-and-cut algorithms to solve the Black-and-White Traveling Salesman Problem (BWTSP) (Bourgeois et al., 2003) which is a variant of the well known Traveling Salesman Problem (TSP). Two strategies to model the BWTSP have been used in the literature. The problem is either modeled on … Read more

    A Benders decomposition based framework for solving cable trench problems

  • Hatice Calik
  • Markus Leitner
  • Martin Luipersbeck
    • Categories Integer Programming, Network Optimization Tags , , ,

    In this work, we present an algorithmic framework based on Benders decomposition for the Capacitated p-Cable Trench Problem with Covering. We show that our approach can be applied to most variants of the Cable Trench Problem (CTP) that have been considered in the literature. The proposed algorithm is augmented with a stabilization procedure to accelerate … Read more

    Improving Benders decomposition via a non-linear cut selection procedure

  • R.S. Camargo
  • F. M. S. Lima
  • G. Miranda
    • Categories Applications - OR and Management Sciences, Cutting Plane Approaches, Network Optimization

    A non-linear lifting procedure is proposed to generate high density Benders cuts. The new denser cuts cover more master problem variables than traditional Benders cuts, shortening the required number of iterations to reach optimality, and speeding up the Benders decomposition algorithm. To lessen the intricacy stemmed from the non-linearity, a simple outer approximation lineariza- tion … Read more

    On the polyhedrality of closures of multi-branch split sets and other polyhedra with bounded max-facet-width

  • Sanjeeb Dash
  • Oktay Gunluk
  • Diego Moran Ramirez
    • Categories (Mixed) Integer Linear Programming Tags , , ,

    For a fixed integer $t > 0$, we say that a $t$-branch split set (the union of $t$ split sets) is dominated by another one on a polyhedron $P$ if all cuts for $P$ obtained from the first $t$-branch split set are implied by cuts obtained from the second one. We prove that given a … Read more

    Convex Relaxations for Quadratic On/Off Constraints and Applications to Optimal Transmission Switching

  • Ksenia Bestuzheva
  • Carleton Coffrin
  • Hassan L. Hijazi
    • Categories (Mixed) Integer Nonlinear Programming, Applications - Science and Engineering, Convex Optimization Tags , , , ,

    This paper studies mixed-integer nonlinear programs featuring disjunctive constraints and trigonometric functions. We first characterize the convex hull of univariate quadratic on/off constraints in the space of original variables using perspective functions. We then introduce new tight quadratic relaxations for trigonometric functions featuring variables with asymmetrical bounds. These results are used to further tighten recent … Read more

    Facets for Node-Capacitated Multicut Polytopes from Path-Block Cycles with Two Common Nodes

  • Michael M. Sørensen
    • Categories Cutting Plane Approaches, Polyhedra

    A path-block cycle is a graph that consists of several cycles that all intersect in a common subset of nodes. The associated path-block-cycle inequalities are valid, and sometimes facet-defining, inequalities for polytopes in connection with graph partitioning problems and corresponding multicut problems. Special cases of the inequalities were introduced by De Souza & Laurent (1995) … Read more

    Best subset selection for eliminating multicollinearity

  • Ken Kobayashi
  • Tomomi Matsui
  • Ryuhei Miyashiro
  • Kazuhide Nakata
  • Yuichi Takano
  • Ryuta Tamura
    • Categories Applications - Science and Engineering, Global Optimization, Integer Programming Tags , , , , ,

    This paper proposes a method for eliminating multicollinearity from linear regression models. Specifically, we select the best subset of explanatory variables subject to the upper bound on the condition number of the correlation matrix of selected variables. We first develop a cutting plane algorithm that, to approximate the condition number constraint, iteratively appends valid inequalities … Read more