Equivalent primal and dual differentiable reformulations of the Euclidean multifacility location problem
作者:
HANIFD. SHERALI,
INTESAR Al-LOUGHANI,
期刊:
IIE Transactions
(Taylor Available online 1998)
卷期:
Volume 30,
issue 11
页码: 1065-1074
ISSN:0740-817X
年代: 1998
DOI:10.1080/07408179808966563
出版商: Taylor & Francis Group
数据来源: Taylor
摘要:
In this paper, we consider two equivalent differentiable reformulations of the nondifferentiable Euclidean multifacility location problem (EMFLP). The first of these is derived via a Lagrangian dual approach based on the optimum of a linear function over a unit ball (circle). The resulting formulation turns out to be identical to the known dual problem proposed by Francis and Cabot [1]. Hence, besides providing an easy direct derivation of the dual problem, this approach lends insights into its connections with classical Lagrangian duality and related results. In particular, it characterizes a straightforward recovery of primal location decisions. The second equivalent differentiable formulation is constructed directly in the primal space. Although the individual constraints of the resulting problem are generally nonconvex, we show that their intersection represents a convex feasible region. We then establish the relationship between the Karush-Kuhn-Tucker (KKT) conditions for this problem and the necessary and sufficient optimality conditions for EMFLP. This lends insights into the possible performance of standard differentiable nonlinear programming algorithms when applied to solve this reformulated problem. Some computational results on test problems from the literature, and other randomly generated problems, are also provided.
点击下载:
PDF (1240KB)
返 回