Quantitative indicators for strength of inequalities with respect to a polyhedron, Part II: Applications and computational evidence

• 成果类型: Article; Early Access
• 署名作者: Warme, David M.
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610; 1436-4646
• DOI: 10.1007/s10107-025-02317-x
• 发表日期: 2026-04-20
• 关键词: integer programming; Combinatorial Optimization; Steiner tree; Enumerative Combinatorics; Extreme point ratio; Centroid distance; GeoSteiner; STEINER MINIMAL-TREES; plane

摘要

Strength is an important property of inequalities used in integer and mixed-integer optimization, both in theory and practice. Unfortunately, no good formal characterization for strength exists, nor is it well-understood. The first paper explored two quantitative strength indicators (extreme point ratio (EPR) and centroid distance (CD)), applying them to the subtour inequalities of the spanning tree in hypergraph polytope STHGP(n)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\mathrm {STHGP(n)}}$$\end{document}. Although it was known that subtour inequalities of small cardinality were strong, EPR and CD agree that subtour inequalities of large cardinality are significantly stronger. In this second paper, we exploit this previously unknown property algorithmically, presenting strong computational evidence that the EPR and CD indicators are highly predictive of actual computational strength. Previous branch-and-cut implementations for optimizing over STHGP(n)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\mathrm {STHGP(n)}}$$\end{document} find violated subtour inequalities of only relatively small cardinality, strengthening only by reducing the cardinality of violated subtours. We present new methods that strengthen violated subtour inequalities by augmentation (instead of reduction). Combining strengthening via reduction and augmentation yields violated subtour inequalities of both small and large cardinality, covering both classes deemed strong by EPR and CD. Across all instance classes studied, the computational results are remarkable - culminating with an optimal solution of a 1,000,000 terminal random Euclidean Steiner tree instance. The conclusion is that the EPR and CD strength indicators presented in the first paper have strong predictive power regarding actual computational strength (at least regarding STHGP(n)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\mathrm {STHGP(n)}}$$\end{document} subtour inequalities). The ability to accurately measure the strength of inequalities has numerous applications of great importance, both in theory and practice.