×

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

MSC:

90C27 Combinatorial optimization
90C35 Programming involving graphs or networks
90C57 Polyhedral combinatorics, branch-and-bound, branch-and-cut
PDFBibTeX XMLCite
Full Text: DOI