The author discusses the construction of lower confidence limits for the optimal values of combinatorial minimization problems. By a detailed computional study on Euclidean travelling salesman problems (TSP) and quadratic assignment problems (QAP) it is confirmed that the Weibull approach suggested by B. L. Golden and F. B. Alt [Nav. Res. Logist. Q. 26, 69-77 (1979; Zbl 0397.90100)] and M. Los and P. Lardinois [Trans. Res. 16B, 89-124 (1982)] is empirically correct. Due to difficulties in estimating the shape parameter in the Los-Lardinois formula this approach led in several cases to incorrect lower bounds, whereas the Golden-Alt formula always yields correct bounds. The computational studies revealed moreover that for TSP a statistical approach using lower confidence limits does not pay, since good and fast deterministic lower bounds are available. For QAP, however, a statistical approach may lead to a powerful heuristic, for example if the statistical lower bounds are used within a branch and bound framework.