Using Confidence Limits for the Global Optimum in Combinatorial Optimization

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.”