Frangioni, Antonio; Lodi, Andrea; Rinaldi, Giovanni Optimizing over semimetric polytopes. (English) Zbl 1131.90442 Bienstock, Daniel (ed.) et al., Integer programming and combinatorial optimization. 10th international IPCO conference, New York, NY, USA, June 7–11, 2004. Proceedings. Berlin: Springer (ISBN 3-540-22113-1/pbk). Lecture Notes in Computer Science 3064, 431-443 (2004). From the text: Let \(G=(V,E)\) be a complete graph. Then the semimetric polytope \(\mathcal M(G)\) associated with \(G\) is defined by the following system of inequalities \[ \begin{aligned} x_{ij}+x_{ik}+x_{jk} &\leq 2,\\ x_{ij}-x_{ik}-x_{jk} &\leq 0,\\ -x_{ij}+x_{ik}-x_{jk} &\leq 0,\\ -x_{ij}-x_{ik}+x_{jk} &\leq 0, \end{aligned} \] for all distinct \(i,j,k\in V\), called the triangle inequalities. This paper deals with the problem of finding efficient algorithms to optimize a linear function over such a polytope.Although these problems are just standard linear programs with a polynomial number of constraints, they turn out to be surprisingly difficult to solve with standard LP tools such as the simplex method or interior-point methods. An alternative technique is the Lagrangian approach where one dualizes all the triangle inequalities and solves it using a subgradient-type approach. The present paper proposes to extend this method in two ways. Firstly, we dualize only a subset of the triangle inequalities, leaving as explicit constraints all the inequalities associated with the triangles of \(G\) that have a selected node in common. Such a system defines a rooted semimetric polytope. Secondly, the bundle-type algorithm is tested as an alternative to subgradient-type approaches for solving the Lagrangian dual. We show that in most cases bundle-type approaches in comparison with the subgradient-type ones either produce primal and/or dual solutions of substantially higher accuracy, or reduce the running times significantly, or achieve both these results.For the entire collection see [Zbl 1051.90001]. Cited in 4 Documents MSC: 90C27 Combinatorial optimization 90C35 Programming involving graphs or networks 90C57 Polyhedral combinatorics, branch-and-bound, branch-and-cut PDFBibTeX XMLCite \textit{A. Frangioni} et al., Lect. Notes Comput. Sci. 3064, 431--443 (2004; Zbl 1131.90442) Full Text: DOI