Combinatorial Optimization

A Note on “A linear-size zero-one programming model for the minimum spanning tree problem in planar graphs”

  • Austin Buchanan
  • Hamidreza Validi
    • Categories Combinatorial Optimization, Integer Programming

    In the paper “A linear-size zero-one programming model for the minimum spanning tree problem in planar graphs” (Networks 39(1):53–60, 2002), Williams introduced an extended formulation for the spanning tree polytope of a planar graph. This formulation is remarkably small (using only $O(n)$ variables and constraints) and remarkably strong (defining an integral polytope). In this note, … Read more

    An Enhanced Branch and Price Algorithm for the Time-Dependent Vehicle Routing Problem with Time Windows

  • Gonzalo Lera-Romero
  • Juan José Miranda-Bront
  • Francisco J. Soulignac
    • Categories Applications - OR and Management Sciences, Combinatorial Optimization

    In this paper we implement a branch and price (BP) algorithm for a time dependent vehicle routing problem with time windows (TDVRPTW) in which the goal is to minimize the total route duration (DM-TDVRPTW). The travel time between two customers depends on the departure time and, thus, it need not remain fixed along the planning … Read more

    New facets for the consecutive ones polytope

  • Laura Brentegani
  • Luigi De Giovanni
  • Mattia Festa
    • Categories Branch and Cut Algorithms, Cutting Plane Approaches, Polyhedra Tags , ,

    A 0/1 matrix has the Consecutive Ones Property if a permutation of its columns exists such that the ones appear consecutively in each row. In many applications, one has to find a matrix having the consecutive ones property and optimizing a linear objective function. For this problem, literature proposes, among other approaches, an Integer Linear … 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

    Benders Decomposition for Very Large Scale Partial Set Covering and Maximal Covering Problems

  • Jean-François Cordeau
  • Fabio Furini
  • Ivana Ljubić
    • Categories Branch and Cut Algorithms, Combinatorial Optimization Tags , , , ,

    Covering problems constitute an important family of facility location problems. This paper intro- duces a new exact algorithm for two important members of this family: i) the maximal covering location problem, which requires finding a subset of facilities that maximizes the amount of demand covered while respecting a budget constraint on the cost of the … Read more

    Scalable Algorithms for the Sparse Ridge Regression

  • Xinwei Deng
  • Weijun Xie
    • Categories Approximation Algorithms, Data-Mining, Integer Programming Tags , , , ,

    Sparse regression and variable selection for large-scale data have been rapidly developed in the past decades. This work focuses on sparse ridge regression, which enforces the sparsity by use of the L0 norm. We first prove that the continuous relaxation of the mixed integer second order conic (MISOC) reformulation using perspective formulation is equivalent to … Read more

    An Approximation Algorithm for Vehicle Routing with Compatibility Constraints

  • Viswanath Nagarajan
  • Siqian Shen
  • Miao Yu
    • Categories Approximation Algorithms, Transportation Tags , ,

    We study a multiple-vehicle routing problem with a minimum makespan objective and compatibility constraints. We provide an approximation algorithm and a nearly-matching hardness of approximation result. We also provide computational results on benchmark instances with diverse sizes showing that the proposed algorithm (i) has a good empirical approximation factor, (ii) runs in a short amount … Read more

    The optimal design of low-latency virtual backbones

  • Austin Buchanan
  • Hamidreza Validi
    • Categories Branch and Cut Algorithms, Integer Programming, Network Optimization

    Two nodes of a wireless network may not be able to communicate with each other directly perhaps due to obstacles or insufficient signal strength. This necessitates the use of intermediate nodes to relay information. Often, one designates a (preferably small) subset of them to relay these messages (i.e., to serve as a virtual backbone for … Read more

    The Synthesis Problem of Decentralized Energy Systems is strongly NP-hard

  • Martin Comis
  • Sebastian Goderbauer
  • Felix J. L. Willamowski
    • Categories Applications - Science and Engineering, Chemical Engineering, Combinatorial Optimization

    We analyze the computational complexity of the synthesis problem of decentralized energy systems. This synthesis problem consists of combining various types of energy conversion units and determining their sizing as well as operations in order to meet time-varying energy demands while maximizing an objective function, e.g., the net present value. In this paper, we prove … Read more