Über eine Anwendung statistischer Schranken in der Kombinatorischen Optimierung

Sei z* der optimale Wert eines Kombinatorischen Optimierungsproblems (o.e. gegeben als Minimierungsproblem) und sei z bekannt mit der Eigenschaft Prob(z > z*) ≤ 1 − α wobei α ∈ (0,1) vorgegeben. Dann heißt zstatistische untere Schranke mit Signifikanzniveau 1 − α.Wir zeigen, wie derartige untere Schranken gewonnen werden können und diskutieren ihre Bedeutung bei der Gütemessung neuer Heuristikeninnerhalb von Branch and Bound-Verfahren.Abschließend berichten wir kurz über numerische Erfahrungen mit diesem Ansatz beim Traveling Salesman Problem und beim Quadratischen Zuordnungsproblem.