Integer Optimization by Local Search A Domain-Independent Approa
Integer Optimization addresses a wide spectrum of practically important optimization problems and represents a major challenge for algorithmics. The goal of integer optimization is to solve a system of constraints and optimization criteria over discrete v
- PDF / 1,457,937 Bytes
- 146 Pages / 431 x 666 pts Page_size
- 74 Downloads / 225 Views
Lecture Notes in Computer Science Edited by G. Goos, J. Hartmanis and J. van Leeuwen
1637
3 Berlin Heidelberg New York Barcelona Hong Kong London Milan Paris Singapore Tokyo
Joachim Paul Walser
Integer Optimization by Local Search A Domain-Independent Approach
Foreword by Henry Kautz
13
Series Editors Jaime G. Carbonell, Carnegie Mellon University, Pittsburgh, PA, USA J¨org Siekmann, University of Saarland, Saarbr¨ucken, Germany Author Joachim Paul Walser 12 Technologies, Airway Park Lozenberg 23, B-1932 Sint-Stevens-Woluwe, Belgium E-mail: [email protected]
Cataloging-in-Publication data applied for Die Deutsche Bibliothek - CIP-Einheitsaufnahme Walser, Joachim Paul: Integer optimization by local search : a domain-independent approach / Joachim Paul Walser. - Berlin ; Heidelberg ; New York ; Barcelona ; Hong Kong ; London ; Milan ; Paris ; Singapore ; Tokyo : Springer, 1999 (Lecture notes in computer science ; Vol. 1637 : Lecture notes in artificial intelligence) ISBN 3-540-66367-3
CR Subject Classification (1998): I.2.8, F.2, G.2, I.2 ISBN 3-540-66367-3 Springer-Verlag Berlin Heidelberg New York This work is subject to copyright. All rights are reserved, whether the whole or part of the material is concerned, specifically the rights of translation, reprinting, re-use of illustrations, recitation, broadcasting, reproduction on microfilms or in any other way, and storage in data banks. Duplication of this publication or parts thereof is permitted only under the provisions of the German Copyright Law of September 9, 1965, in its current version, and permission for use must always be obtained from Springer-Verlag. Violations are liable for prosecution under the German Copyright Law. c Springer-Verlag Berlin Heidelberg 1999 Printed in Germany Typesetting: Camera-ready by author SPIN 10703430 06/3142 – 5 4 3 2 1 0
Printed on acid-free paper
To my mother, Irene
Foreword
An encouraging trend in the field of artificial intelligence in the past few years has been its growing interaction with the area of operations research. AI has traditionally concentrated on problems of logical inference and satisfiability, or in other words, Boolean feasibility problems. OR, by contrast, has mainly focused on problems of linear optimization. Many significant real world tasks share aspects of both kinds of problems, and there is therefore much interest in integrating and expanding the techniques that have been developed in each field. This monograph by Dr. Joachim Paul Walser is thus particularly timely and significant. He developes new algorithms and systems for applying discrete local search techniques that were originally developed for Boolean feasibility problems to a broad class of integer linear optimization problems. He demonstrates that his general, domain-independent solver can be competitive with specialized algorithms on hard realistic problems, and can often far outperform other state-of-the-art domain-independent solvers. Throughout the monograph Dr. Walser draws connections to classic techniques from OR and AI, an
Data Loading...
