Optimization Online


An Integer Programming Approach to the Path Selection Problems

Deokseong Kim(deokseong.kim***at***samsung.com)
Kyungsik Lee(globaloptima***at***hufs.ac.kr)
Kyungchul Park(olivaw***at***naver.com)
Sungsoo Park(sspark***at***kaist.ac.kr)

Abstract: We consider two types of path selection problems defined on arc-capacitated networks. Given an arc-capacitated network and a set of selected ordered pairs of nodes (commodity) each of which has a demand quantity, the first problem is to select a subset of commodities and setup one path for each chosen commodity to maximize profit, while satisfying the arc capacity constraints. The second is to setup one path for each of the given commodities so that the total cost is minimized under the same capacity constraints as the first problem. We present new integer programming formulations for the two problems whose linear programming relaxations provide stronger bounds than earlier formulations. Since each of these integer programs has an exponentially many variables, column generation procedures are proposed to solve the linear programming relaxations. To get an integer optimum solution, we devise a branch-and-price procedure which incorporates an effective branching strategy. Computational experiments show that our algorithm can yield optimal solutions within reasonably small computing time. We also perform computational experiments to make comparisons with other existing approaches. The results show that our algorithm outperforms other approaches, mainly due to stronger bounds and smaller sizes of the enumeration trees.

Keywords: multicommodity flows; path selection problems; integer programming; column generation; branch-and-price

Category 1: Network Optimization

Category 2: Integer Programming

Citation: not published yet

Download: [PDF]

Entry Submitted: 05/28/2007
Entry Accepted: 05/29/2007
Entry Last Modified: 05/28/2007

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Programming Society