Loading...
Please wait, while we are loading the content...
Similar Documents
An integer programming approach to the path selection problems (2003).
| Content Provider | CiteSeerX |
|---|---|
| Author | Park, Sungsoo Lee, Kyungsik Kim, Deokseong |
| Abstract | We consider two types of path selection problems for arc capacitated network. Given an arc capacitated network and a set of commodities, one problem is to find a subset of commodities to be routed and an assignment of them to the paths so that profit is maximized. The other problem is to route all given commodities in the network so that cost is minimized. Bifurcation of flow is not allowed in both cases. We formulate the problems as integer programming models and solve them. Column generation technique to solve the linear programming relaxation is proposed with two types of columns. To obtain an optimum integer solution for the problems, we propose a branching strategy in the branch-and-price scheme. Computational experiments show that the algorithm gives optimal solutions within reasonably small computing time. |
| File Format | |
| Publisher Date | 2003-01-01 |
| Access Restriction | Open |
| Subject Keyword | Branching Strategy Integer Programming Model Branch-and-price Scheme Path Selection Problem Optimal Solution Small Computing Time Computational Experiment Column Generation Technique Linear Programming Relaxation Optimum Integer Solution Integer Programming Approach |
| Content Type | Text |
