An Active-set Algorithm for Discrete Network Design Problems

Lihui Zhang, Siriphong Lawphongpanich and Yafeng Yin
Additional contact information
Lihui Zhang: University of Florida
Siriphong Lawphongpanich: University of Florida
Yafeng Yin: University of Florida

Chapter Chapter 14 in Transportation and Traffic Theory 2009: Golden Jubilee, 2009, pp 283-300 from Springer

Abstract: Abstract In this paper, we formulate a discrete network design problem as a mathematical program with complementarity constraints and propose an active set algorithm to solve the problem. Each complementarity constraint requires the product of a pair of nonnegative variables to be zero. Instead of dealing with this type of constraints directly, the proposed algorithm assigns one of the nonnegative variables in each pair a value of zero. Doing so reduces the design problem to a regular nonlinear program. Using the multipliers associated with the constraints forcing nonnegative variables to be zero, the algorithm then constructs and solves binary knapsack problems to make changes to the zero-value assignments in order to improve the system delay. Numerical experiments with data from networks in the literature indicate that the algorithm is effective and has the potential for solving larger network design problems.

Keywords: System Delay; Network Design Problem; User Equilibrium; Complementarity Constraint; Transportation Research Part (search for similar items in EconPapers)
Date: 2009
References: Add references at CitEc
Citations: View citations in EconPapers (11)

There are no downloads for this item, see the EconPapers FAQ for hints about obtaining it.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:sprchp:978-1-4419-0820-9_14

Ordering information: This item can be ordered from
http://www.springer.com/9781441908209

DOI: 10.1007/978-1-4419-0820-9_14

Access Statistics for this chapter

More chapters in Springer Books from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().