The Euclidean Steiner tree problem in Rn: A mathematical programming formulation

The Euclidean Steiner tree problem in Rn: A mathematical programming formulation

0.00 Avg rating0 Votes
Article ID: iaor20011674
Country: Netherlands
Volume: 96
Issue: 1
Start Page Number: 209
End Page Number: 220
Publication Date: Nov 2000
Journal: Annals of Operations Research
Authors: , ,
Keywords: programming: integer
Abstract:

A nonconvex mixed-integer programming formulation for the Euclidean Steiner Tree Problem (ESTP) in Rn 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.

Reviews

Required fields are marked *. Your email address will not be published.