Branch and Cut Algorithms

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

    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

    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

    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

    Computational study of a cutting plane algorithm for University Course Timetabling

  • Pasquale Avella
  • Igor Vasil'ev
    • Categories Branch and Cut Algorithms, Scheduling Tags ,

    In this paper we describe a successful case-study where a Branch-and-Cut algorithm yields the \lq\lq optimal” solution of a real-world timetabling problem of University courses \emph{(University Course Timetabling problem)}. The problem is formulated as a \emph{Set Packing problem} with side constraints. To tighten the initial formulation, we utilize well-known valid inequalities of the Set Packing … Read more

    A Branch and Cut Algorithm for Hub Location Problems with Single Assignment

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

    The hub location problem with single assignment is the problem of locating hubs and assigning the terminal nodes to hubs in order to minimize the cost of hub installation and the cost of routing the traffic in the network. There may also be capacity restrictions on the amount of traffic that can transit by hubs. … Read more

    Computational study of large-scale p-Median problems

  • Pasquale Avella
  • Antonio Sassano
  • Igor Vasil'ev
    • Categories Branch and Cut Algorithms Tags , ,

    Given a directed graph G(V,A), the p-Median problem consists of determining p nodes (the median nodes) minimizing the total distance from the other nodes of the graph. We present a Branch-and-Cut algorithm yielding provably good solutions for instances up to 3795 nodes (14,402,025 variables). Key ingredients of our approach are: lagrangian relaxation, a simple procedure … Read more

    Parallel Interval Continuous Global Optimization Algorithms

  • Abdeljalil Benyoub
    • Categories Branch and Cut Algorithms, Global Optimization, Parallel Algorithms Tags , , , , ,

    We theorically study, on a distributed memory architecture, the parallelization of Hansen’s algorithm for the continuous global optimization with inequality constraints, using interval arithmetic. We propose a parallel algorithm based on a dynamic redistribution of the working list among the processors. On the other hand, we exploit the reduction technique, developped by Hansen, for computing … Read more

    Two-connected networks with rings of bounded cardinality

  • Bernard Fortz
  • Martine Labbé
    • Categories Branch and Cut Algorithms, Telecommunications Tags ,

    We study the problem of designing at minimum cost a two-connected network such that each edge belongs to a cycle using at most K edges. This problem is a particular case of the two-connected networks with bounded meshes problem studied by Fortz, Labbé and Maffioli. In this paper, we compute a lower bound on the … Read more