Skip to main content
SpringerLink
Log in
Book cover

Computational Combinatorial Optimization

Optimal or Provably Near-Optimal Solutions

  • Textbook
  • © 2001

Overview

Editors:
  1. Michael Jünger

    1. Universität zu Köln,Institut für Informatik, Köln, Germany

    View editor publications

    You can also search for this editor in PubMed   Google Scholar

  2. Denis Naddef

    1. ENSIMAG - antenne de Montbonnot Laboratoire Informatique et Distribution, ZIRST, Montbonnot Saint Martin, France

    View editor publications

    You can also search for this editor in PubMed   Google Scholar

Part of the book series: Lecture Notes in Computer Science (LNCS, volume 2241)

This is a preview of subscription content, log in via an institution to check access.

Access this book

Log in via an institution
eBook USD 39.99
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book USD 54.99
Price excludes VAT (USA)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Other ways to access

Licence this eBook for your library

Institutional subscriptions

Table of contents (7 chapters)

  1. Front Matter

    Pages I-I
    Download chapter PDF

  2. General Mixed Integer Programming: Computational Issues for Branch-and-Cut Algorithms

    • Alexander Martin
    Pages 1-25

  3. Projection and Lifting in Combinatorial Optimization

    • Egon Balas
    Pages 26-56

  4. Mathematical Programming Models and Formulations for Deterministic Production Planning Problems

    • Yves Pochet
    Pages 57-111

  5. Lagrangian Relaxation

    • Claude Lemaréchal
    Pages 112-156

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

    • Matthias Elf, Carsten Gutwenger, Michael Jünger, Giovanni Rinaldi
    Pages 157-222

  7. Branch, Cut, and Price: Sequential and Parallel

    • Laszlo Ladányi, Ted K. Ralphs, Leslie E. Trotter Jr
    Pages 223-260

  8. TSP Cuts Which Do Not Conform to the Template Paradigm

    • David Applegate, Robert Bixby, Vašek Chvátal, William Cook
    Pages 261-303

  9. Back Matter

    Pages 305-305
    Download chapter PDF
Back to top

Keywords

About this book

This tutorial contains written versions of seven lectures on Computational Combinatorial Optimization given by leading members of the optimization community. The lectures introduce modern combinatorial optimization techniques, with an emphasis on branch and cut algorithms and Lagrangian relaxation approaches. Polyhedral combinatorics as the mathematical backbone of successful algorithms are covered from many perspectives, in particular, polyhedral projection and lifting techniques and the importance of modeling are extensively discussed. Applications to prominent combinatorial optimization problems, e.g., in production and transport planning, are treated in many places; in particular, the book contains a state-of-the-art account of the most successful techniques for solving the traveling salesman problem to optimality.

Editors and Affiliations

  • Universität zu Köln,Institut für Informatik, Köln, Germany

    Michael Jünger

  • ENSIMAG - antenne de Montbonnot Laboratoire Informatique et Distribution, ZIRST, Montbonnot Saint Martin, France

    Denis Naddef

Bibliographic Information

Publish with us

Policies and ethics

Back to top

Search

Navigation