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.
Citation
not published yet