Directed fixed charge multicommodity network design: a cutting plane approach using polar duality

Abstract

We present an efficient cutting-plane based approach to exactly solve a directed fixed charge network design (DFCND) problem, wherein the valid inequalities to the problem are generated using the polar duality approach. The biggest challenge in using this approach arises in constructing the polar dual of the problem. This would require enumerating all the extreme points of the convex hull of DFCND, which is computationally impractical for any instance of a reasonable size. Moreover, the resulting polar dual would be too large to solve efficiently, which is required at every iteration of the cutting-plane algorithm. The novelty of our solution approach lies in suggesting a way to circumvent this challenge by instead generating the violated facets, using polar duality, of the smaller substructures involving only a small subset of constraints and variables, obtained from 2-, 3-and 4-partitions of the underlying graph. For problem instances based on sparse graphs with zero flow costs, addition of these inequalities closes more than 20% of the optimality gap remaining after the addition of the knapsack cover inequalities used in the literature. This allows us to solve the problem instances in less than 400 s, on average, which otherwise take around 1000 s with the addition of only the knapsack cover inequalities, and around 4 hours for the Cplex MIP solver at its default setting.