Quantitative Indicators for Strength of Inequalities with Respect to a Polyhedron

• 成果类型: Article; Early Access
• 署名作者: Warme, David M.
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610; 1436-4646
• DOI: 10.1007/s10107-026-02342-4
• 发表日期: 2026-04-13
• 关键词: integer programming; Combinatorial Optimization; Steiner tree; traveling salesman problem; Enumerative Combinatorics; Extreme point ratio; Centroid distance; cutting planes

摘要

We study the notion of strength of inequalities used in integer and mixed-integer programming, and the branch-and-cut algorithms used to solve such problems. Strength is an ethereal property lacking any good formal definition, but crucially affects speed of computations. We review several quantitative indicators proposed in the literature that we claim provide a measure of the relative strength of inequalities with respect to a given polyhedron. We evaluate two of these indicators (extreme point ratio (EPR) and centroid distance (CD)) in closed-form for subtour inequalities of both the traveling salesman polytope TSP(n)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${ extrm{TSP}(n)}$$\end{document}, and 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}$${ extrm{STHGP}(n)}$$\end{document}. Within each facet class, the two indicators yield strikingly similar strength rankings, with excellent agreement on which facets are strongest and which are weakest. Both indicators corroborate all known computational experience with both polytopes. The indicators also reveal properties of STHGP(n)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${ extrm{STHGP}(n)}$$\end{document} subtours that were previously neither known nor suspected. We also evaluate these indicators for subtours of the spanning tree in graphs polytope STGP(n)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${ extrm{STGP}(n)}$$\end{document}, obtaining unexpected results that lead us to believe EPR to be a more accurate estimate of strength than CD. Applications include: comparing the relative strength of different classes of inequalities; design of rapidly-converging separation algorithms; and design or justification for constraint strengthening procedures. The companion paper exploits one of the newly revealed properties of STHGP(n)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${ extrm{STHGP}(n)}$$\end{document} subtours in GeoSteiner, presenting detailed computational results. Across all distance metrics and instances studied, these results are remarkable - culminating with an optimal solution of a 1,000,000 terminal random Euclidean instance. This confirms these indicators to be highly predictive and strongly correlated with actual computational strength.