Using Confidence Limits for the Global Optimum in Combinatorial Optimization

Ulrich Derigs
Additional contact information
Ulrich Derigs: Universität Bonn, Bonn, West Germany

Operations Research, 1985, vol. 33, issue 5, 1024-1049

Abstract: Let z * be the (unknown) optimal value of a combinatorial optimization problem (in minimization form) and let z be a constant satisfying Prob( z * ≥ z ) ≥ 1 − α for a fixed α ∈ (0, 1). Then z is called a statistical or probabilistic lower bound at significance level 1 − α. We discuss how statistical lower bounds can be used to measure the effectiveness of an approximate solution and to fathom subproblems in a branch and bound approach. After reviewing some methods for obtaining statistical lower bounds, we report on extensive computational experience for two notoriously difficult combinatorial optimization problems—the traveling salesman problem and the quadratic assignment problem. From our experience we conclude that statistical bounds are highly useful for quadratic assignment problems. In this problem context, the quality of simple analytic formulas is comparable to the quality of the maximum likelihood formula. In general, using statistics to aid in the solution of combinatorial optimization problems should be most useful when such problems are “large.”

Keywords: 625 statistical estimators in combinatorial programming algorithms; 799 bounds in combinatorial programming (search for similar items in EconPapers)
Date: 1985
References: Add references at CitEc
Citations: View citations in EconPapers (5)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.33.5.1024 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:33:y:1985:i:5:p:1024-1049

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().