ECMI-kurs i kombinatorisk optimering 6-9 juni 1995
Professor Jan Karel LENSTRA, Eindhoven, kommer att ge en kurs i
kombinatorisk optimering under veckan efter pingst, 6-9
juni. Innehållet finns
beskrivet nedan.
Gästföreläsningarna realiseras inom ECMI-samarbetet
(ECMI står för
European Consortium for Mathematics in Industry), i vilket både
Göteborgs Universitet och Chalmers Tekniska Högskola deltar.
Första gången är tisdagen den 6 juni kl. 10.00 i Hörsalen, Matematiskt
Centrum, Eklandagatan 86. Omfattningen är cirka 10 tim föreläsningar,
samt (valfritt) handlett eget arbete i anslutning till kursen.
A course in combinatorial optimization
Combinatorial optimization is concerned with planning and design problems
in which the decision variables are restricted to assume discrete values.
Such problems can often be modelled as linear programs in integral
variables. Typical examples are the traveling salesman problem, where one
wants to determine a shortest tour through a set of cities, and the job
shop scheduling problem, where one looks for a minimum-length schedule for
a number of jobs on a number of machines subject to given machine orders
for the jobs and capacity constraints for the machines. In this course I
will give an introduction into the main techniques that have been developed
for the solution of such problems.
- Polynomial-time optimization
- I will review the problem types in combinatorial optimization for which an
optimal solution can be computed fast. These include matching, maximum
flow, and linear programming problems.
- Enumerative optimization
- For many problems, including the traveling salesman and the job shop
scheduling problems, one has to apply some form of enumeration in order to
find an optimal solution. I will discuss enumerative methods such as
dynamic programming and branch-and-bound, and pay attention to techniques
for improving bounds based on Lagrangian relaxation and LP-formulations.
- Computational complexity
- The first two lectures motivate the following question: When is it easy to
find an optimum, and when is it hard? Computational complexity theory
formalizes this distinction. I will give an informal introduction to this
theory and indicate how it can often be easily applied to determine the
complexity of a given optimization problem.
- Approximation: performance guarantees
- When a problem is hard, one has to choose between slow optimization and
fast approximation. In the latter case, the question is how far the
answer obtained can deviate from the optimum. I will review a number of
positive and negative results of this type.
- Approximation: local search
- Local search methods carry no guarantee regarding solution quality or
running time, but for many complex optimization problems they produce good
solutions in reasonable amounts of time. I will discuss the basic technique
of iterative improvement and its recent variants such as simulated
annealing, variable-depth search and tabu search.
Start
Tisdagen den 6 juni 1995 (Tredjedag Pingst) kl. 10.00 i Hörsalen
Ansvarig
Jan Karel Lenstra,
Eindhoven University of Technology / CWI, Amsterdam
Lars Alexandersson
<larsa@math.chalmers.se>
Senast ändrad den 23 mars 1995