  


An Integer Programming Approach to the Path Selection Problems
Deokseong Kim(deokseong.kimsamsung.com) Abstract: We consider two types of path selection problems defined on arccapacitated networks. Given an arccapacitated 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 branchandprice 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; branchandprice Category 1: Network Optimization Category 2: Integer Programming Citation: not published yet Download: [PDF] Entry Submitted: 05/28/2007 Modify/Update this entry  
Visitors  Authors  More about us  Links  
Subscribe, Unsubscribe Digest Archive Search, Browse the Repository

Submit Update Policies 
Coordinator's Board Classification Scheme Credits Give us feedback 
Optimization Journals, Sites, Societies  