Integer and combinatorial optimization problems constitute a major
challenge for algorithmics. They arise when a large number of
discrete organizational decisions have to be made, subject to
constraints and optimization criteria.
This thesis describes and investigates new domain-independent local
search strategies for linear integer optimization. We introduce
WSAT(OIP), an integer local search method which operates on an
algebraic problem representation. WSAT(OIP) generalizes Walksat, a
successful local search procedure for propositional satisfiability
(SAT), to more expressive constraint systems.
For this purpose, we introduce over-constrained integer programs
(OIPs), a constraint class which is closely related to integer
programs. OIP allows for a natural generalization of the principles
of SAT local search to integer optimization. Further, it will be
shown that OIPs are a special case of integer linear programs and
permit combinations with linear programming for bound computation,
initialization by rounding, search space reduction, and feasibility
testing. The representation is similar enough to integer programs to
make use of existing algebraic modeling languages as front-end to a
local search solver. To improve performance on realistic problems,
WSAT(OIP) incorporates strategies from Tabu Search.
We experimentally investigate WSAT(OIP) for a variety of realisic
integer optimization problems from the domains of time tabling,
sports scheduling, radar surveillance, course assignment, and
capacitated production planning. The experimental design examines
efficiency, scaling (with increasing problem size and
constrainedness), and robustness. The results demonstrate that
integer local search can outperform or compete with state-of-the-art
integer programming (IP) branch-and-bound and constraint programming
(CP) approaches to these problems in finding near-optimal solutions.
Key findings of our empirical study include that integer local
search is able to solve difficult constraint problems from
time-tabling and sports scheduling when cast into a 0-1
representation, which are beyond the scope of IP branch-and-bound
strategies and for which devising robust constraint programs is a
non-trivial task.
For several realistic optimization problems (0-1 integer and finite
domain) we show that integer local search exhibits graceful runtime
scaling with increasing problem size and constrainedness. It can
therefore significantly outperform IP branch-and-bound strategies on
large or tightly constrained problems in finding near-optimal
solutions. The problems under consideration are mostly beyond the
limitations of a previous general-purpose simulated annealing
strategy for 0-1 integer programs.