Combinatorial Optimization

Decomposition and Dynamic Cut Generation in Integer Linear Programming

  • M.V. Galati
  • Ted K. Ralphs
    • Categories (Mixed) Integer Linear Programming, Branch and Cut Algorithms, Cutting Plane Approaches Tags , , , ,

    Decomposition algorithms such as Lagrangian relaxation and Dantzig-Wolfe decomposition are well-known methods that can be used to generate bounds for mixed-integer linear programming problems. Traditionally, these methods have been viewed as distinct from polyhedral methods, in which bounds are obtained by dynamically generating valid inequalities to strengthen the linear programming relaxation. Recently, a number of … Read more

    Continuous Line Drawings via the Traveling Salesman Problem

  • Robert Bosch
  • Adrianne Herman
    • Categories Applications - OR and Management Sciences, Applications - Science and Engineering, Combinatorial Optimization Tags ,

    We describe how to use the traveling salesman problem (TSP) to create continuous line drawings of target pictures. Citation Dept. of Mathematics, Oberlin College, Oberlin, Ohio 44074 Article Download View Continuous Line Drawings via the Traveling Salesman Problem

    A Fast Swap-based Local Search Procedure for Location Problems

  • Mauricio G.C. Resende
  • Renato F. Werneck
    • Categories Combinatorial Optimization, Facility Planning and Design Tags , ,

    We present a new implementation of a widely used swap-based local search procedure for the P-median problem, proposed in 1968 by Teitz and Bart. Our method produces the same output as the best alternatives described in the literature and, even though it does not have a better worst-case complexity, it can be significantly faster in … Read more

    A Branch-and-Cut Algorithm for Graph Coloring

  • Isabel Méndez-Díaz
  • Paula Zabala
    • Categories Branch and Cut Algorithms, Polyhedra

    In a previous work, we proposed a new integer programming formulation for the graph coloring problem which, to a certain extent, avoids symmetry. We studied the facet structure of the 0/1-polytope associated with it. Based on these theoretical results, we present now a Branch-and-Cut algorithm for the graph coloring problem. Our computational experiences compare favorably … Read more

    The Quadratic Selective Travelling Saleman Problem

  • Thomas R. Stidsen
  • Tommy Thomadsen
    • Categories 0-1 Programming, Branch and Cut Algorithms, Network Optimization Tags , , ,

    A well-known extension of the Travelling Salesman Problem (TSP) is the Selective TSP (STSP): Each node has an associated profit and instead of visiting all nodes, the most profitable set of nodes, taking into account the tour cost, is visited. The Quadratic STSP (QSTSP) adds the additional complication that each pair of nodes have an … Read more

    Bounds for the Quadratic Assignment Problem Using the Bundle Method

  • Franz Rendl
  • Renata Sotirov
    • Categories Combinatorial Optimization Tags , , ,

    Semidefinite Programming (SDP) has recently turned out to be a very powerful tool for approximating some NP-hard problems. The nature of the Quadratic Assignment Problem suggests SDP as a way to derive tractable relaxation. We recall some SDP relaxations of QAP and solve them approximately using the Bundle Method. The computational results demonstrate the efficiency … Read more

    Polyhedral investigations on stable multi-sets

  • Arie M.C.A. Koster
  • Adrian Zymolka
    • Categories Branch and Cut Algorithms, Graphs and Matroids, Polyhedra Tags , ,

    Stable multi-sets are an evident generalization of the well-known stable sets. As integer programs, they constitute a general structure which allows for a wide applicability of the results. Moreover, the study of stable multi-sets provides new insights to well-known properties of stable sets. In this paper, we continue our investigations started in Koster and Zymolka … Read more

    Reservoir Operation by Ant Colony Optimization Algorithms

  • Abbas Afshar
  • Mohammad Reza Jalali
  • M. A. Marino
    • Categories Civil and Environmental Engineering, Meta Heuristics

    In this paper, ant colony optimization (ACO) algorithms are proposed for reservoir operation. Through a collection of cooperative agents called ants, the nearoptimum solution to the reservoir operation can be effectively achieved. To apply ACO algorithms, the problem is approached by considering a finite horizon with a time series of inflow, classifying the reservoir volume … Read more

    Domination analysis for minimum multiprocessor scheduling

  • Gregory Gutin
  • Anders Yeo
  • Tommy Jensen
    • Categories Approximation Algorithms Tags , ,

    Let $P$ be a combinatorial optimization problem, and let $A$ be an approximation algorithm for $P$. The domination ratio $\domr(A,s)$ is the maximal real $q$ such that the solution $x(I)$ obtained by $A$ for any instance $I$ of $P$ of size $s$ is not worse than at least the fraction $q$ of the feasible solutions … Read more

    Polyhedral Analysis for Concentrator Location Problems

  • Martine Labbé
  • Hande Yaman
    • Categories Branch and Cut Algorithms, Polyhedra, Telecommunications Tags , ,

    The concentrator location problem is to choose a subset of a given terminal set to install concentrators and to assign each remaining terminal node to a concentrator to minimize the cost of installation and assignment. The concentrators may have capacity constraints. We study the polyhedral properties of concentrator location problems with different capacity structures. We … Read more