Skip to main content
Registrieren
Springer Professional
TOOLBAR 1 2 3 4
SUCHE
MENÜ 1 2 3 4
Suchformular schließen
Erweiterte Suche
main-content
nach oben
​
insite
Drucken
​
print
​
share

1999 | Buch

Integer Optimization by Local Search

A Domain-Independent Approach

Introduction Erstes Kapitel lesen

Buchreihe: Lecture Notes in Computer Science

Herausgeber: Joachim Paul Walser

Verlag: Springer Berlin Heidelberg

Print ISBN: 978-3-540-66367-6

Electronic ISBN: 978-3-540-48369-4

Enthalten in: Professional Book Archive

Zugang erhalten Inhaltsverzeichnis

Über dieses Buch

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.

Inhaltsverzeichnis

Frontmatter

1.. Introduction
Abstract
Integer and combinatorial optimization problems arise when a large number of discrete organizational decisions have to be made, subject to constraints and optimization criteria. This monograph describes and investigates new domain-independent local search strategies for linear integer optimization. This chapter briefly introduces integer optimization and heuristics, and presents an outline of integer local search, the approach to integer optimization that is the subject of this book. Integer local search generalizes local search for propositional satisfiability to linear integer optimization. Research in this area is situated in the interface between artificial intelligence and operations research. Since the two fields have been relatively separated in their past, terminology conflicts occasionally arise that we will attempt to point out.
Fred Glover

2.. Frameworks for Combinatorial Optimization
Abstract
This chapter outlines some successful frameworks for combinatorial optimization. It is meant as a brief introduction into terminology and outlines the basic principles of the frameworks which are applied in the subsequent case studies. The three frameworks that will be discussed, integer linear programming (ILP), finite domain constraint programming (CP) and local search are well established, comprise of a variety of techniques, and many successful applications have been reported. ILP and CP can be considered the state-of-the-art of general-purpose optimization methods, whereas local search should be seen as an approach that can be tailored to many different optimization problems by adapting its conceptual components to the respective problem context. We also discuss successful local search methods for solving propositional satisfiability problems.

3.. Local Search for Integer Constraints
Abstract
This chapter introduces new local search strategies for integer optimization and represents the technical core of this book. It describes and discusses Wsat(oip), a domain-independent method that generalizes the Walksat procedure of Selman, Kautz, and Cohen [134] for propositional satisfiability to integer optimization and integer constraint solving. For performance on realistic applications, the method additionally incorporates principles from Tabu Search [58].

4.. Case Studies Methodology
Abstract
The previous chapter has described new methods for integer local search and presented the Wsat(oip) procedure. The next three chapters will empirically investigate the performance of Wsat(oip) in a number of realistic case studies. In between, this chapter reflects on issues and goals of our experimental analysis.
John N. Hooker

5.. Time-Tabling and Sports Scheduling
Abstract
This chapter investigates two difficult time-tabling/scheduling problems, ‘the Progressive Party Problem’ (PPP) and scheduling of the Atlantic Coast (basketball) Competition of 1997/98 (ACC). Both problems were recently introduced and solved in the literature [115, 136]. The previous results demonstrate that finding feasible solutions for these problem is challenging, even when using approaches that incorporate domain-knowledge.

6.. Covering and Assignment
Abstract
This chapter investigates two integer optimization problems, radar surveillance and course assignment. For both problems, the 0-1 OIP encoding is straightforward. Structurally, the problems are extensions of set covering and generalized assignment, respectively. The first problem stems from an industrial project at the Swedish Institute for Computer Science (SICS), while the second problem arose from an operating application at the Universität des Saarlandes. Both studies in this chapter will focus on performance variation of integer local search and IP branch-and-bound with increasing problem size.

7.. Capacitated Production Planning
Abstract
This chapter investigates two integer optimization problems, radar surveillance and course assignment. For both problems, the 0-1 OIP encoding is straightforward. Structurally, the problems are extensions of set covering and generalized assignment, respectively. The first problem stems from an industrial project at the Swedish Institute for Computer Science (SICS), while the second problem arose from an operating application at the Universität des Saarlandes. Both studies in this chapter will focus on performance variation of integer local search and IP branch-and-bound with increasing problem size.

8.. Extensions
Abstract
The primary goals in this book so far have been twofold: To describe new effective algorithms within the integer local search framework and to demonstrate their capabilities for practical applications. In this section, we will critically examine the limitations of the current methods and subsequently suggest an extension to overcome some of the current limitations, and provide some ideas for future research.

Backmatter

Weitere Informationen

Version: 0.1251.0