Bulletin
100, August 97
Combinatorial Algorithms
for Pattern Recognition
in Composite Tracking Chambers
Jean-François
Pusztaszeri
School of Operations
Research and Industrial Engineering
Cornell University
This work represents the
first successful attempt at employing a combinatorial approach to solve
the data association phase of multiple-target tracking in experimental
high energy physics. It is shown not only to merge reasonably well with
mainstream parameter estimation procedures used in practice, among which
the Extended Kalman Filter (EKF), but also to provide in several instances
the only alternative to exhaustive search when precision requirements are
in place.
More generally, this effort
also reveals that, in the context of multiple-target tracking with simultaneous
returns, the robustness of Kalman filtering can be substantially improved
by coupling it to a combinatorial steering algorithm which take its data
association measure from the suboptimal prediction returned by the EKF.
When indeed convergence criteria of the filter are not met, as often is
the case in practice, the task of the combinatorial framework is to perform
a recursive generation of integer programming subproblems which minimize
local residuals.
The approach was fully tested
within the context of ALEPH, one of the four experiments utilizing the
LEP accelerator at CERN. It was implemented in parts in the official reconstruction
code of the experiment, establishing its usefulness over sequential methods
used until then. Models in this context were of the generalized assignment
and set packing types. In the course of the implementation, care had been
taken to retain nearest-neighbour search methods whenever possible, and
use them for track initiation by adding simple stopping criteria. For large
integer programming instances, use was made of a decomposition heuristic
revealed by a study on the cluster structure of observations.
Work on mathematical modeling
was only started once a thorough investigation of information processing
requirements for this tracking application had been completed, leading
to a clean formulation and to good experimental results. While specifically
developed for ALEPH, the approach has been kept as general as possible,
and is shown to generalize to other experiments with only modest additional
modeling effort.
Dr. Jean-Francois Pusztaszeri
School of Operations Research
and Industrial Engineering
720, Frank H. T. Rhodes
Hall, Cornell University
Ithaca, NY 14853-3801, U.S.A.
Ph. +1.607.255.7885
Fax. +1.607.255.9129
pusztaszeri@cornell.edu
Standortprobleme mit Berücksichtigung
von Kapazitätsrestriktionen :
Modellierung und Lösungsverfahren
Paul Wentges
Abteilung Betriebswirtschaft
Universität Ulm
Standortentscheidungen sind
aufgrund ihres langfristigen Charakters für den wirtschaftlichen Erfolg
einer Unternehmung von großer Wichtigkeit. Wenngleich bei der betrieblichen
Standortwahl sicherlich häufig das sprichwörtliche Fingerspitzengefühl
des erfahrenen Unternehmers nicht ohne Bedeutung ist, dürfte jedoch
vor allem in komplexen Entscheidungssituationen eine systematische Vorgehensweise
und die Anwendung geeigneter Modelle und Methoden in Abhängigkeit
von der jeweiligen Problemstellung für eine gute Standortplanung unerläßlich
sein.
Ziel der Arbeit ist die
detaillierte Auseinandersetzung mit einem der wichtigsten Modelle des Operations
Research aus dem Bereich der gemischt-ganzzahligen Standorttheorie: des
Capacitated-Facility-Location-Problems ((CFLP)). Eine dem (CFLP) typischerweise
zugrundeliegende Problemstellung wird durch das nachfolgend kurz skizzierte
Anwendungsbeispiel beschrieben:
Verteilzentren (Auslieferungslager)
sollen eingerichtet werden, um die Nachfrage von Kunden nach einem bestimmten
Gut zu befriedigen, wobei Kapazitätsrestriktionen bei den einzelnen
Verteilzentren zu berücksichtigen sind. Aus einer vorgegebenen Menge
potentieller Standorte ist nun eine Standortkombination derart auszuwählen,
daß die Summe aus den variablen Transportkosten zur Versorgung aller
Kunden und den fixen Kosten zur Errichtung bzw. Erhaltung der Verteilzentren
minimiert wird.
Da Capacitated-Facility-Location-Probleme
zur Klasse der NP-harten Probleme gehören, sind sie im allgemeinen
schwer zu lösen. Der Schwerpunkt der Arbeit wurde daher darauf gelegt,
bereits bestehende Verfahren zur Lösung des Capacitated-Facility-Location-Problems
auf ihre Tauglichkeit hin zu untersuchen und Verbesserungsmöglichkeiten
für diese
Verfahren auszuloten bzw.
neue Lösungsverfahren zu entwickeln. Im Mittelpunkt der Untersuchungen
stand dabei die Auseinandersetzung mit den Dekompositionsverfahren der
gemischt-ganzzahligen linearen Programmierung.
Als wesentliche Ergebnisse
der Arbeit sind zu nennen:
-
Das Dantzig-Wolfe-Dekompositionsverfahren
zur Bestimmung des optimalen Wertes des Lagrange-Duals von gemischt-ganzzahligen
linearen Programmen konvergiert häufig nur sehr langsam. Mit Hilfe
der entwickelten sogenannten gewichteten Dantzig-Wolfe-Dekomposition wurde
der Versuch unternommen, die relativ große Streuung der Optimalwerte
der jeweils zu lösenden Lagrange-Subprobleme einzudämmen: Anstelle
der optimalen Lösung des Dantzig-Wolfe-Master-Problems wird ein speziell
gewichteter Durchschnitt aller im bisherigen Verlauf des Verfahrens bestimmten
Lagrange-Multiplikatoren als Lagrange-Multiplikator für das nächste
zu lösende Lagrange-Subproblem verwendet. Für das (CFLP) konnten
mit dieser Vorgehensweise deutlich bessere Ergebnisse als mit dem ursprünglichen
Verfahren erzielt werden.
-
Die Konvergenzeigenschaften
des Benders-Dekompositionsverfahrens konnten mit Hilfe neuer Algorithmen
zur Verschärfung der Benders-Schnitte erheblich verbessert werden,
so daß das Verfahren der Benders-Dekomposition auch zur heuristischen
Lösung des (CFLP) empfohlen werden kann. Weiterhin wurde die
Pareto-Optimalität eines Teils der verschärften Benders-Schnitte
nachgewiesen.
-
Das von Van Roy entwickelte
Verfahren der Cross-Dekomposition wurde häufig als das effizienteste
Verfahren zur Lösung des (CFLP) angesehen. Dabei wird der Versuch
unternommen, die beiden Verfahren der Benders- und der Dantzig-Wolfe-Dekomposition
miteinander zu verknüpfen und damit sowohl die primale als auch die
duale Struktur des (CFLP) auszunützen. Mit der dual-gewichteten Cross-Dekomposition,
einer auf der gewichteten Dantzig-Wolfe-Dekomposition beruhenden Modifikation
des ursprünglichen Verfahrens, konnte die Konvergenzgeschwindigkeit
des Verfahrens verbessert werden. Zudem konnte die Konvergenz sowohl der
dual-gewichteten Cross-Dekomposition als auch der gewichteten Danztig-Wolfe
Dekomposition gegen den optimalen Wert des Lagrange-Duals sowie einige
weitere Eigenschaften dieser Verfahren nachgewiesen werden.
Dr. Paul Wentges
Universität Ulm
Abteilung Betriebswirtschaft
D - 89069 Ulm
Tel : 0049-731-502 3544
Fax : 0049-731-502 3584
wentges@mathematik.uni-ulm.de
RETURN
to previous page.