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 variables. Integer Optimization by Local Search introduces a new approach to domain-independent integer optimization, which, unlike traditional strategies, is based on local search. It develops the central concepts and strategies of integer local search and describes possible combinations with classical methods from linear programming. The surprising effectiveness of the approach is demonstrated in a variety of case studies on large-scale, realistic problems, including production planning, timetabling, radar surveillance, and sports scheduling. The monograph is written for practitioners and researchers from artificial intelligence and operations research. Lecture Notes in Artificial Intelligence Foreword Preface Table of Contents List of Figures List of Tables 1. Introduction Introduction Integer Optimization and Heuristics Integer Local Search Experimental Results Research Contributions 2. Frameworks for Combinatorial Optimization] Frameworks for Combinatorial Optimization Integer Programming Branch-and-Bound Finite Domain Constraint Programming Local Search Meta-heuristics RISC and CISC Local Search Local Search for SAT Application Domains of SAT Local Search Modeling Languages Search Relaxations and Integer Local Search 3. Local Search for Integer Constraints Local Search for Integer Constraints Over-Constrained Integer Programs Definition Relation to Integer Linear Programs Constraint-Bounds Integer Local Search: Wsat(oip) The Score The Main Loop Move Selection and Tabu Search Extensions Combinations with Linear Programming Bounds from LP Relaxations Initialization by Rounding LP Solutions Search Space Reduction Using LP Reduced Costs Implementation Issues A Graphical Interpretation Related Work Integer Programming Heuristics Local Search in Constraint Satisfaction Summary 4. Case Studies Methodology Case Studies Methodology Optimization in Practice: Criteria of Success Scaling with Increasing Problem Size Scaling with Increasing Constrainedness Flexibility and Residual Robustness The Problem Class Selection The Empirical Comparisons 5. Time-Tabling and Sports Scheduling Time-Tabling and Sports Scheduling The Progressive Party Problem Problem Description and Formulation Experimental Results and Comparison The ACC Basketball Scheduling Problem Double Round Robin Scheduling Problem Specification of ACC97/98 Integer Local Search Formulation Redundant Constraints Previous (Multi-stage) Approaches Experimental Results under Varied Constrainedness Minimal Distortion Mirroring Conclusions 6. Covering and Assignment Covering and Assignment Radar Surveillance Covering Problem Description and Formulation Experimental Results under Varied Problem Size Course Assignment Problem Description and Formulation Experimental Results under Varied Problem Size A Related Application: Reviewer Assignment Conclusions 7. Capacitated Production Planning Capacitated Production Planning Capacitated Lot-Sizing Integer Local Search Formulation Mixed Integer Programming Formulation Lagrangean Relaxation Approach Restricting the Problem Experimental Results Comparison of Results Lower Bounds Conclusions 8. Extensions Extensions Current Limitations An Alternative Scoring Scheme Future Research Conclusions A. A Complete AMPL Model for ACC97/98 References Index Integer Optimization By Local Search Introduces A New Approach To Domain-independent Integer Optimization, Which, Unlike Traditional Strategies, Is Based On Local Search. It Develops The Central Concepts And Strategies Of Integer Local Search And Describes Possible Combinations With Classical Methods From Linear Programming. The Surprising Effectiveness Of The Approach Is Demonstrated In A Variety Of Case Studies On Large-scale, Realistic Problems, Including Production Planing, Timetabling, Radar Surveillance, And Sports Scheduling. The Monograph Is Written For Practitioners And Researchers From Computer Science, Discrete Mathematics, Artificial Intelligence, And Operations Research.--jacket. 1. Introduction -- 2. Frameworks For Combinatorial Optimization -- 3. Local Search For Integer Constraints -- 4. Case Studies Methodology -- 5. Time-tabling And Sports Scheduling -- 6. Covering And Assignment -- 7. Capacitated Production Planning -- 8. Extensions -- A. A Complete Ampl Model For Acc97/98. Joachim Paul Walser ; Foreword By Henry Kautz. Includes Bibliographical References (p. ).
