Equivalent primal and dual differentiable reformulations of the Euclidean multifacility location problem

Equivalent primal and dual differentiable reformulations of the Euclidean multifacility location problem

0.00 Avg rating0 Votes
Article ID: iaor2002561
Country: United States
Volume: 30
Issue: 11
Start Page Number: 1065
End Page Number: 1074
Publication Date: Nov 1998
Journal: IIE Transactions
Authors: ,
Keywords: duality
Abstract:

In this paper, we consider two equivalent differentiable reformulations of the non-differentiable 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. 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 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 computation results on test problems from the literature, and other randomly generated problems, are also provided.

Reviews

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