Guy Desaulniers，Column Generation(2005).pdf-资料库

COLUMN GENERATION

G E R AD 25th Anniversary Series Essays and Surveys in Global Optimization Charles Audet, Pierre Hansen, and Gilles Savard, editors Graph Theory and Combinatorial Optimization David Avis, Alain Hertz, and Odile Marcotte, editors Numerical Methods in Finance Hatem Ben-Ameur and Michele Breton, editors Analysis, Control and Optimization of Complex Dynamic Sys tems El-Kebir Boukas and Roland Malhame, editors Column Generation Guy Desaulniers, Jacques Desrosiers, and Marius M. Solomon, editors Statistical Modeling and Analysis for Complex Data Problems Pierre Duchesne and Bruno Remillard, editors Performance Evaluation and Planning Methods for the Next Generation Internet Andre Girard, Brunilde Sanso, and Felisa Vazquez-Abad, editors Dynamic Games: Theory and Applications Alain Haurie and Georges Zaccour, editors Logistics Systems: Design and Optimization Andre Langevin and Diane Riopel, editors Energy and Environment Richard Loulou, Jean-Philippe Waaub, and Georges Zaccour, editors

COLUMN GENERATION Edited by GUY DESAULNffiRS GERAD and Ecole Polytechnique de Montreal JACQUES DESROSIERS GERAD and HEC Montreal MARIUS M. SOLOMON GERAD and Northeastern University, Boston Spri ringer

Guy Desaulniers GERAD & Ecole Polytechnique de Montreal Montreal, Canada Jacques Desrosiers GERAD and HEC Montreal, Canada Marius M. Solomon GERAD and Northeastern University Boston, MA, USA Library of Congress Cataloging-in-Publication Data Column generation / edited by Guy Desaulniers, Jacques Desrosiers, Marius M. Solomon, p. cm. - (GERAD 25* anniversary series) Includes bibliographical references. ISBN-13: 978-0-387-25485-2 (acid-free paper) ISBN-10: 0-387-25485-4 (acid-free paper) ISBN-10: 0-387-25486-2 (e-book) 1. Production scheduling. I. Desaulniers, Guy. II. Desrosiers, Jacques. III. Solomon, Marius M. IV. Series. TS 157.5.C64 2005 658.5'3—dc22 2005043438 © 2005 by Springer Science+Business Media, Inc. All rights reserved. This work may not be translated or copied in whole or in part without the written permission of the pubhsher (Springer Science + Business Media, Inc., 233 Spring Street, New York, NY I00I3, USA), except for brief excerpts in cormection with reviews or scholarly analysis. Use in cormection with any form of information storage and retrieval, electronic adaptation, computer software, or by similar or dissimilar methodology now know or hereafter developed is forbidden. The use in this pubhcation of trade names, trademarks, service marks and similar terms, even if the are not identified as such, is not to be taken as an expression of opinion as to whether or not they are subject to proprietary rights. Printed in the United States of America. 9 8 7 6 5 4 3 21 SPIN II053088 springeronIine.com

Foreword GERAD celebrates this year its 25th anniversary. The Center was created in 1980 by a small group of professors and researchers of HEC Montreal, McGill University and of the Ecole Polytechnique de Montreal. GERAD's activities achieved sufficient scope to justify its conversion in June 1988 into a Joint Research Centre of HEC Montreal, the Ecole Polytechnique de Montreal and McGill University. In 1996, the Uni- versite du Quebec ä Montreal joined these three institutions. GERAD has fifty members (professors), more than twenty research associates and post doctoral students and more than two hundreds master and Ph.D. students. GERAD is a multi-university center and a vital forum for the develop ment of operations research. Its mission is defined around the following four complementarily objectives: • The original and expert contribution to all research fields in GERAD's area of expertise; • The dissemination of research results in the best scientific outlets as well as in the society in general; • The training of graduate students and post doctoral researchers; • The contribution to the economic community by solving important problems and providing transferable tools. GERAD's research thrusts and fields of expertise are as follows: • Development of mathematical analysis tools and techniques to solve the complex problems that arise in management sciences and engineering; • Development of algorithms to resolve such problems efficiently; • Application of these techniques and tools to problems posed in related disciplines, such as statistics, financial engineering, game theory and artificial intelligence; • Apphcation of advanced tools to optimization and planning of large technical and economic systems, such as energy systems, trans portation/communication networks, and production systems; • Integration of scientific findings into software, expert systems and decision-support systems that can be used by industry.

vi COL UMN GENERA TION One of the marking events of the celebrations of the 25th anniver sary of GERAD is the pubUcation of ten volumes covering most of the Center's research areas of expertise. The list follows: Essays and Surveys in Global Optimization, edited by C. Audet, P. Hansen and G. Savard; Graph Theory and Combinatorial Optimization, edited by D. Avis, A. Hertz and O. Marcotte; Numerical Methods in Finance, edited by H. Ben-Ameur and M. Breton; Analysis, Con trol and Optimization of Complex Dynamic Systems, edited by E.K. Boukas and R. Malhame; Column Generation, edited by G. Desaulniers, J. Desrosiers and M.M. Solomon; Statistical Modeling and Analysis for Complex Data Problems, edited by P. Duchesne and B. Remillard; Performance Evaluation and Planning Meth ods for the Next Generation Internet, edited by A. Girard, B. Sanso and F. Vazquez-Abad; Dynamic Games: Theory and Applica tions, edited by A. Haurie and G, Zaccour; Logistics Systems: De sign and Optimization, edited by A. Langevin and D. Riopel; Energy and Environment, edited by R. Loulou, J.-P. Waaub and G. Zaccour. I would like to express my gratitude to the Editors of the ten volumes, to the authors who accepted with great enthusiasm to submit their work and to the reviewers for their benevolent work and timely response. I would also like to thank Mrs. Nicole Paradis, Francine Benoit and Louise Letendre and Mr. Andre Montpetit for their excellent editing work. The GERAD group has earned its reputation as a worldwide leader in its field. This is certainly due to the enthusiasm and motivation of GERAD's researchers and students, but also to the funding and the infrastructures available, I would like to seize the opportunity to thank the organizations that, from the beginning, believed in the potential and the value of GERAD and have supported it over the years. These are HEC Montreal, Ecole Polytechnique de Montreal, McGill University, Universite du Quebec ä Montreal and, of course, the Natural Sciences and Engineering Research Council of Canada (NSERC) and the Fonds quebecois de la recherche sur la nature et les technologies (FQRNT). Georges Zaccour Director of GERAD

Avant-propos Le Groupe d'etudes et de recherche en analyse des decisions (GERAD) fete cette annee son vingt-cinquieme anniversaire. Fonde en 1980 par une poignee de professeurs et chercheurs de HEC Montreal engages dans des recherches en equipe avec des collegues de PUniversite McGill et de TEcole Polytechnique de Montreal, le Centre comporte maintenant une cinquantaine de membres, plus d'une vingtaine de professionnels de recherche et stagiaires post-doctoraux et plus de 200 etudiants des cycles superieurs. Les activites du GERAD ont pris sufRsamment d'ampleur pour justifier en juin 1988 sa transformation en un Centre de recherche conjoint de HEC Montreal, de PEcole Polytechnique de Montreal et de rUniversite McGill. En 1996, TUniversite du Quebec ä Montreal s'est jointe ä ces institutions pour parrainer le GERAD. Le GERAD est un regroupement de chercheurs autour de la discipline de la recherche operationnelle. Sa mission s'articule autour des objectifs complementaires suivants : • la contribution originale et experte dans tons les axes de recherche de ses champs de competence; • la diffusion des resultats dans les plus grandes revues du domaine ainsi qu'aupres des differents publics qui forment I'environnement du Centre; • la formation d'etudiants des cycles superieurs et de stagiaires post- doctoraux; • la contribution ä la communaute economique ä travers la resolution de problemes et le developpement de coffres d'outils transferables. Les principaux axes de recherche du GERAD, en allant du plus theo- rique au plus applique, sont les suivants : • le developpement d'outils et de techniques d'analyse mathematiques de la recherche operationnelle pour la resolution de problemes com plexes qui se posent dans les sciences de la gestion et du genie; • la confection d'algorithmes permettant la resolution efRcace de ces problemes; • I'application de ces outils ä des problemes poses dans des disciplines connexes ä la recherche operationnelle telles que la statistique, I'in- genierie financiere, la theorie des jeux et Pintelligence artificielle; • Tapplication de ces outils ä Toptimisation et ä la planification de grands systemes technico-economiques comme les systemes energe- tiques, les reseaux de telecommunication et de transport, la logis- tique et la distributique dans les industries manufacturieres et de service;

资料库

Guy Desaulniers，Column Generation(2005).pdf

相关推荐

课程资源

热门标签

最新资料