Branch-and-Cut Algorithms for Combinatorial Optimization and Their Implementation in ABACUS

Elf, Matthias and Gutwenger, Carsten and J√ľnger, Michael and Rinaldi, Giovanni (2001) Branch-and-Cut Algorithms for Combinatorial Optimization and Their Implementation in ABACUS.
Published in: Computational Combinatorial Optimization: Optimal or Provably Near-Optimal Solutions., Lecture Notes in Computer Science. 2241 Springer 2001, pp. 157-222.

Abstract

Branch-and-Cut-and-Price algorithms belong to the most successful techniques forsolving mixed integer linear programs and combinatorial optimization problems to optimality (or, at least, with certified quality). In this unit, we concentrate on sequential Branch-and-Cut for hard combinatorial optimization problems, while Branch-and-Cut for general mixed integer linear programming is treated in [ --> Martin] and parallel Branch-and-Cut is treated in [--> Ladanyi/Ralphs/Trotter]. After telling our most recent story of a successful application of Branch-and-Cut, we give in a brief review of the history, including the contributions of pioneers with an emphasis on the computational aspects of their work. The components of a generic Branch-and-Cut algorithm are described and illustrated on the traveling salesman problem. We first elaborate a bit on the important separation problem where we use the traveling salesman problem and the maximum cut problem as examples, then we show how Branch-and-Cut can be applied to problems with a very large number of variables Branch-and-Cut-and-Price. The last sectionis devoted to the design and applications of the ABACUS software framework for the implementation of Branch-and-Cut algorithms. Finally we make a few remarks on the solution of the exercise consisting of the design of a simple TSP-solver in ABACUS.


Actions:
Full text not available from this repository.
Export as: [error in script]
Editorial actions: View Item View Item (Login required)
Content information:
Item Type: Collection Item
Citations: [error in script] 28 (Google Scholar) | [error in script]
Uncontrolled Keywords: [error in script]
Subjects:
  • 90-XX Operations research, mathematical programming > 90Cxx Mathematical programming > 90C57 Polyhedral combinatorics, branch-and-bound, branch-and-cut

  • 90-XX Operations research, mathematical programming > 90Cxx Mathematical programming > 90C27 Combinatorial optimization

  • Uncontrolled Keywords: Branch and Cut Algorithms, Combinatorial Optimization, Computational Combinatorial Optimization, Discrete Computations, Discrete Structures, Optimization Algorithms, Polyhedral Combinatorics, Traveling Salesman Problem (TSP)
    Subjects: 90-XX Operations research, mathematical programming > 90Cxx Mathematical programming > 90C57 Polyhedral combinatorics, branch-and-bound, branch-and-cut
    90-XX Operations research, mathematical programming > 90Cxx Mathematical programming > 90C27 Combinatorial optimization
    Divisions: Institute of Computer Science > Computer Science Department - Prof. Dr. Juenger
    Depositing User: Matthias Elf
    Date Deposited: 27 Jun 2003 00:00
    Last Modified: 08 Jul 2013 08:26
    Deposit Information:
    ZAIK Number: [error in script]
    Depositing User: Matthias Elf
    Date Deposited: 27 Jun 2003 00:00
    Last Modified: 08 Jul 2013 08:26
    URI: http://e-archive.informatik.uni-koeln.de/id/eprint/454