A lagrange relaxation method for the network design problem considering facility location

Ming Zhe Chen*, Naoto Katayama, Hiroaki Mohri

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review


The network design problem, which attempts to simultaneously take into account facility location and network topology, has a number of applications in transportation network design, distribution systems, telecommunication network planning, and other areas. In this paper, we investigate a new model that simultaneously optimizes facility locations for distribution centers and concentrators, network topology for line-haul trucks and fiber-optic communication lines, and routes of commodity flow for freight and communication data. Our model consists of uncapacitated facility location, uncapaci-tated arc design, general network design, an unlimited number of freight transshipment at facilities, and multi-commodity flow routing that has a large number of origin-destination pairs. It has been noted that this model is not suitable for solving problems that exist in the real world with current OR software on the market. We present a new formulation of this problem that minimizes the sum of flow costs, arc design costs, and facility location costs, and a new Lagrange relaxation problem with relaxed flow conservation constraints and some forcing constraints. We present an exact solution method for this Lagrange relaxation problem, and a subgradient method for Lagrange multipliers. In addition, we present an approximate solution method for obtaining good upper bound using solutions of a Lagrange relaxation problem, which is called Lagrange heuristics. Numerical examples up to 100 nodes are given to show the effectiveness of our formulation and solution methods for lower and upper bound.

Original languageEnglish
Pages (from-to)330-338
Number of pages9
JournalJournal of Japan Industrial Management Association
Issue number5
Publication statusPublished - 2005 Dec 1


  • Facility location
  • Lagrange relaxation
  • Mathematical programming
  • Network design
  • Optimization

ASJC Scopus subject areas

  • Strategy and Management
  • Management Science and Operations Research
  • Industrial and Manufacturing Engineering
  • Applied Mathematics


Dive into the research topics of 'A lagrange relaxation method for the network design problem considering facility location'. Together they form a unique fingerprint.

Cite this