integer linear programming

Robust Network Design: Formulations, Valid Inequalities, and Computations

  • Arie M.C.A. Koster
  • Manuel Kutschka
  • Christian Raack
    • Categories Cutting Plane Approaches, Polyhedra, Robust Optimization Tags , , , ,

    Traffic in communication networks fluctuates heavily over time. Thus, to avoid capacity bottlenecks, operators highly overestimate the traffic volume during network planning. In this paper we consider telecommunication network design under traffic uncertainty, adapting the robust optimization approach of Bertsimas and Sim (2004). We present three different mathematical formulations for this problem, provide valid inequalities, … Read more

    Recoverable Robust Knapsacks: $\GammahBcScenarios

  • Christina Büsing
  • Arie M.C.A. Koster
  • Manuel Kutschka
    • Categories (Mixed) Integer Linear Programming, Robust Optimization Tags , , , ,

    In this paper, we investigate the recoverable robust knapsack problem, where the uncertainty of the item weights follows the approach of Bertsimas and Sim (2003,2004). In contrast to the robust approach, a limited recovery action is allowed, i.e., upto k items may be removed when the actual weights are known. This problem is motivated by … Read more

    Optimizing the Layout of Proportional Symbol Maps: Polyhedra and Computation

  • Pedro J. de Rezende
  • Cid C. de Souza
  • Guilherme Kunigami
  • Tallys H. Yunes
    • Categories (Mixed) Integer Linear Programming, Basic Sciences Applications, Branch and Cut Algorithms Tags , , ,

    Proportional symbol maps are a cartographic tool to assist in the visualization and analysis of quantitative data associated with specific locations, such as earthquake magnitudes, oil well production, and temperature at weather stations. As the name suggests, symbol sizes are proportional to the magnitude of the physical quantities that they represent. We present two novel … Read more

    Exact Solution of Graph Coloring Problems via Constraint Programming and Column Generation

  • Stefano Gualandi
  • Federico Malucelli
    • Categories Combinatorial Optimization, Integer Programming Tags , , ,

    We consider two approaches for solving the classical minimum vertex coloring problem�that is, the problem of coloring the vertices of a graph so that adjacent vertices have different colors and minimizing the number of used colors, namely, constraint programming and column generation. Constraint programming is able to solve very efficiently many of the benchmarks but … Read more

    A Class Representative Model for Pure Parsimony Haplotyping

  • Daniele Catanzaro
  • Martine Labbé
  • Alessandra Godi
    • Categories (Mixed) Integer Linear Programming, Basic Sciences Applications Tags , ,

    Parsimonious haplotype estimation from aligned Single Nucleotide Polymorphism (SNP) fragments consists of finding the minimum number of haplotypes necessary to explain a given set of genotypes. This problem is known to be NP-Hard. Here we describe a new integer linear-programming model to tackle this problem based on the concept of class representatives, already used for … Read more

    Solving chance-constrained combinatorial problems to optimality

  • Olivier Klopfenstein
    • Categories 0-1 Programming, Stochastic Programming Tags ,

    The aim of this paper is to provide new efficient methods for solving general chance-constrained integer linear programs to optimality. Valid linear inequalities are given for these problems. They are proved to characterize properly the set of solutions. They are based on a specific scenario, whose definition impacts strongly on the quality of the linear … Read more

    Tractable algorithms for chance-constrained combinatorial problems

  • Olivier Klopfenstein
    • Categories Combinatorial Optimization, Robust Optimization, Stochastic Programming Tags , , , , ,

    This paper aims at proposing tractable algorithms to find effectively good solutions to large size chance-constrained combinatorial problems. A new robust model is introduced to deal with uncertainty in mixed-integer linear problems. It is shown to be strongly related to chance-constrained programming when considering pure 0-1 problems. Furthermore, its tractability is highlighted. Then, an optimization … Read more

    A new model and a computational study for Demand-wise Shared Protection

  • Claus G. Gruber
  • Arie M.C.A. Koster
  • Sebastian Orlowski
  • Adrian Zymolka
  • Roland Wessäly
    • Categories (Mixed) Integer Linear Programming, Network Optimization, Telecommunications Tags , , ,

    This report combines the contributions to INOC 2005 (Wessälly et al., 2005) and DRCN 2005 (Gruber et al., 2005). A new integer linear programming model for the end-to-end survivability concept deman d-wise shared protection (DSP) is presented. DSP is based on the idea that backup capacity is dedicated to a particular demand, but shared within … Read more