%A Qun Chen
%T A Large Scale Integer and Combinatorial Optimizer
%D September 2000
%R 00-03
%I COMPUTER SCIENCES DEPARTMENT, UNIVERSITY OF WISCONSIN
%C MADISON, WI
%X
The topic of this thesis, integer and combinatorial optimization,
involves minimizing (or maximizing) a function of many variables,
some of which belong to a discrete set, subject to constraints.
This area has abundant applications in industry.
Integer and combinatorial optimization problems are often
difficult to solve due to the large and complex set of alternatives.
The objective of this thesis is to present an effective
solution to integer and combinatorial problems by using a traditional
reliable branch-and-bound approach as well as a newly developed fast
adaptive random search method, namely Nested Partitions.
The proposed integer and combinatorial optimizer has two closely related
components: FATCOP and NP/GA. FATCOP is a distributed mixed integer
program solver written in PVM for Condor's opportunistic environment.
It is different from prior parallel branch-and-bound work by implementing
a general purpose parallel mixed integer programming algorithm in
an opportunistic multiple processor environment, as opposed to
a conventional dedicated environment. We show how to make effective
use of opportunistic resources while ensuring the program works
correctly. The solver also provides performance-enhancing features
such as preprocessing, pseudocost branching, cutting plane generation,
locking of variables and general purpose primal heuristics.
FATCOP performs very well on test problems arising
from real applications, and is particularly useful to solve long-running
hard mixed integer programming problems.
For many integer and combinatorial optimization problems,
application-specific tuning may be required. Users can supply
combinatorial approximation algorithms which exploit structure unique
to the problem class. These can be run in conjunction
with the system defaults or in place of them. In this thesis, we
developed a new hybrid algorithm NP/GA based on Nested
Partitions and a Genetic Algorithms. This algorithm retains the global
perspective of the Nested partitions method and the local search
capacities of the Genetic Algorithm, and can be applied to any integer
and combinatorial optimization problems.
We applied our optimizer to product design problems from the marketing
area. We started with building NP/GA heuristic algorithms and showed
that our algorithms outperform all previous approaches. Following
that, we incorporated the heuristics to FATCOP and solved some
reasonable size instances to optimality.