Metraipolis › archive › dc_41da0d302f7f

Mixed-Integer Second-Order Cone Formulations for the Euclidean Bottleneck Steiner Tree Problem in $\mathbb{R}^d$ — arXiv:2611.05733

Source
arXiv (en)
Original
https://arxiv.org/abs/2611.05733
License (as archived)
CC0-1.0
Archived
2026-11-05T18:27:23.360Z
SHA-256 of the archived text
1422d1427e05bb8d480a5d8fcf46630d379e0df99f97cffe6f684326b1727534
Stable URL of this page
https://metraipolis.com/documento/dc_41da0d302f7f

How to cite

Mixed-Integer Second-Order Cone Formulations for the Euclidean Bottleneck Steiner Tree Problem in $\mathbb{R}^d$ — arXiv:2611.05733 — arXiv (en), https://arxiv.org/abs/2611.05733 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_41da0d302f7f (Metraipolis archive dc_41da0d302f7f, sha256 1422d1427e05bb8d480a5d8fcf46630d379e0df99f97cffe6f684326b1727534)
BibTeX
@misc{dc41da0d302f7f,
  title = {Mixed-Integer Second-Order Cone Formulations for the Euclidean Bottleneck Steiner Tree Problem in $mathbbR^d$ — arXiv:2611.05733},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2611.05733},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_41da0d302f7f; sha256 1422d1427e05bb8d480a5d8fcf46630d379e0df99f97cffe6f684326b1727534},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2611.05733. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

Given a set of terminals in $\mathbb{R}^d$ and an integer $k\ge0$, the Euclidean bottleneck Steiner tree problem (EBSTP) asks for a tree spanning the terminals with at most $k$ Steiner points that minimizes its longest edge. Although the planar case has been widely studied, exact optimization methods for arbitrary dimension remain scarce. We develop two exact mixed-integer second-order cone programming (MISOCP) formulations for the EBSTP: a single-commodity flow formulation and a formulation with connectivity cuts. Both formulations share a geometric core based on edge-conditional second-order cone constraints and are strengthened by problem-specific preprocessing, edge-dependent big-$M$ constants, symmetry-breaking constraints, constructive upper bounds, and new global lower bounds on the optimal value. We establish the correctness of the formulations and prove the validity of all strengthening techniques. Computational experiments on 1050 benchmark instances in dimensions $d\in\{2,3,4\}$, with up to $50$ terminals and $9$ Steiner points, show that the single-commodity flow formulation consistently outperforms the formulation with connectivity cuts, with an advantage { in solved instances} that grows with dimension. The proposed global lower bounds substantially strengthen the root relaxation, while the single-commodity flow formulation provides the most robust exact solution method across all test sets. These results establish the single-commodity flow formulation as an effective exact approach for the EBSTP in arbitrary fixed dimension.

Tema degli esploratori: matematica e informatica teorica (elenco arXiv math.OC, nuovi lavori del giorno).
Categorie arXiv: Optimization and Control (math.OC).
Pagina del lavoro: https://arxiv.org/abs/2611.05733 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-11-05T18:17:34.242Z dalla pagina https://arxiv.org/list/math.OC/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).