The Euclidean Steiner tree problem in \(\mathbb{R}^{n}\): A mathematical programming formulation. (English) Zbl 0966.90064
Summary: A nonconvex mixed-integer programming formulation for the Euclidean Steiner Tree Problem (ESTP) in \(\mathbb{R}^{n}\) is presented. After obtaining separability between integer and continuous variables in the objective function, a Lagrange dual program is proposed. To solve this dual problem (and obtaining a lower bound for ESTP) we use subgradient techniques. In order to evaluate a subgradient at each iteration we have to solve three optimization problems, two in polynomial time, and one is a special convex nondifferentiable programming problem.
MSC:
90C27 | Combinatorial optimization |
90C11 | Mixed integer programming |
90C46 | Optimality conditions and duality in mathematical programming |
49J30 | Existence of optimal solutions belonging to restricted classes (Lipschitz controls, bang-bang controls, etc.) |
90C35 | Programming involving graphs or networks |