Mixed-Integer Second-Order Cone Formulations for the Euclidean Bottleneck Steiner Tree Problem in ℝd
Abstract
Given a set of terminals in ℝd and an integer k≥0, 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∈{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.
Related
- The Calderón problem for near-Euclidean metrics
- Local rigidity of conformally Euclidean metrics for the anisotropic Calderón problem
- Exact cost of the Euclidean Maximum Traveling Salesman Problem in one dimension
- The solvability of the Lp-dual mixed Euclidean-Gauss Minkowski problem
- Exact Asymptotics for the 2D Euclidean Random Matching Problem
BibTeX
@misc{braun2026mixedinteger,
title = {{Mixed-Integer Second-Order Cone Formulations for the Euclidean Bottleneck Steiner Tree Problem in $\mathbbR^d$}},
author = {Gabriel P. Braun and Marcia Fampa and Nelson Maculan and Renan V. Pinto},
howpublished = {arXiv},
year = {2026},
month = nov,
doi = {10.48550/arxiv.2611.05733},
eprint = {2611.05733},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2611.05733},
}
RIS
TY - UNPB
TI - Mixed-Integer Second-Order Cone Formulations for the Euclidean Bottleneck Steiner Tree Problem in ℝ^d
AU - Gabriel P. Braun
AU - Marcia Fampa
AU - Nelson Maculan
AU - Renan V. Pinto
PY - 2026
DA - 2026/11/03
PB - arXiv
DO - 10.48550/arxiv.2611.05733
UR - https://arxiv.org/abs/2611.05733
AB - Given a set of terminals in ℝ^d and an integer k≥0, 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∈{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.
ER -