Combinatorial Optimization

Submodular Minimization in the Context of Modern LP and MILP Methods and Solvers

  • Jon Lee
  • Siqian Shen
  • Andrew Orso
    • Categories 0-1 Programming, Combinatorial Optimization, Linear Programming Tags , , , ,

    We consider the application of mixed-integer linear programming (MILP) solvers to the minimization of submodular functions. We evaluate common large-scale linear-programming (LP) techniques (e.g., column generation, row generation, dual stabilization) for solving a LP reformulation of the submodular minimization (SM) problem. We present heuristics based on the LP framework and a MILP solver. We evaluated … Read more

    Single-Commodity Robust Network Design with Finite and Hose Demand Sets

  • Valentina Cacchiani
  • Frauke Liers
  • Andrea Lodi
  • Michael Juenger
  • Daniel Schmidt
    • Categories Branch and Cut Algorithms, Network Optimization, Robust Optimization Tags , , ,

    We study a single-commodity Robust Network Design problem (sRND) defined on an undirected graph. Our goal is to determine minimum cost capacities such that any traffic demand from a given uncertainty set can be satisfied by a feasible single-commodity flow. We consider two ways of representing the uncertainty set, either as a finite list of … Read more

    New Semidefinite Programming Relaxations for the Linear Ordering and the Traveling Salesman Problem

  • Philipp Hungerländer
    • Categories Approximation Algorithms, Production and Logistics, Semi-definite Programming

    In 2004 Newman suggested a semidefinite programming relaxation for the Linear Ordering Problem (LOP) that is related to the semidefinite program used in the Goemans-Williamson algorithm to approximate the Max Cut problem. Her model is based on the observation that linear orderings can be fully described by a series of cuts. Newman shows that her … Read more

    A Polyhedral Investigation of Star Colorings

  • Christopher Hojny
  • Marc E. Pfetsch
    • Categories Polyhedra Tags , , , ,

    Given a weighted undirected graph~$G$ and a nonnegative integer~$k$, the maximum~$k$-star colorable subgraph problem consists of finding an induced subgraph of~$G$ which has maximum weight and can be star colored with at most~$k$ colors; a star coloring does not color adjacent nodes with the same color and avoids coloring any 4-path with exactly two colors. … Read more

    On the Adaptivity Gap in Two-stage Robust Linear Optimization under Uncertain Constraints

  • Pranjal Awasthi
  • Vineet Goyal
  • Brian Lu
    • Categories Approximation Algorithms, Robust Optimization

    In this paper, we study the performance of static solutions in two-stage adjustable robust packing linear optimization problem with uncertain constraint coefficients. Such problems arise in many important applications such as revenue management and resource allocation problems where demand requests have uncertain resource requirements. The goal is to find a two-stage solution that maximizes the … Read more

    An Axiomatic Duality Framework for the Theta Body and Related Convex Corners

  • Marcel K. de Carli Silva
  • Levent Tunçel
    • Categories Combinatorial Optimization, Linear, Cone and Semidefinite Programming Tags , , ,

    Lovász theta function and the related theta body of graphs have been in the center of the intersection of four research areas: combinatorial optimization, graph theory, information theory, and semidefinite optimization. In this paper, utilizing a modern convex optimization viewpoint, we provide a set of minimal conditions (axioms) under which certain key, desired properties are … Read more

    A Versatile Heuristic Approach for Generalized Hub Location Problems

  • Uwe Clausen
  • J. Fabian Meier
    • Categories Meta Heuristics, Statistics, Transportation

    The usability of hub location models heavily depends on an appropriate modelling approach for the economies of scale. Realistic hub location models require more sophisticated transport cost structures than the traditional flow-independent discount. We develop a general modelling scheme for such problems allowing the definition of complicated (non-linear) costs and constraints; its structure allows an … Read more

    Steiner Trees with Degree Constraints: Structural Results and an Exact Solution Approach

  • Frauke Liers
  • Alexander Martin
  • Susanne Pape
    • Categories Branch and Cut Algorithms, Polyhedra Tags , , , ,

    In this paper we study the Steiner tree problem with degree constraints. Motivated by an application in computational biology we first focus on binary Steiner trees in which all node degrees are required to be at most three. We then present results for general degree-constrained Steiner trees. It is shown that finding a binary Steiner … Read more

    Approximating the Minimum Hub Cover Problem on Planar Graphs

  • Ş. İlker Birbil
  • Kerem Bülbül
  • Hasan M. Jamil
  • Belma Yelbay
    • Categories Applications - Science and Engineering, Approximation Algorithms Tags , , , ,

    We study an approximation algorithm with a performance guarantee to solve a new NP-hard optimization problem on planar graphs. The problem, which is referred to as the minimum hub cover problem, has recently been introduced to the literature to improve query processing over large graph databases. Planar graphs also arise in various graph query processing … Read more

    Lower Bounding Procedures for the Single Allocation Hub Location Problem

  • Christoph Buchheim
  • Uwe Clausen
  • J. Fabian Meier
  • Borzou Rostami
    • Categories 0-1 Programming, Graphs and Matroids, Production and Logistics Tags , ,

    This paper proposes a new lower bounding procedure for the Uncapacitated Single Allocation p-Hub Median Problem based on Lagrangean relaxation. For solving the resulting Lagrangean subproblem, the given problem structure is exploited: it can be decomposed into smaller subproblems that can be solved efficiently by combinatorial algorithms. Our computational experiments for some benchmark instances demonstrate … Read more