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

Y.K. Agarwal, Y.P. Aneja and Sachin Jayaswal

European Journal of Operational Research, 2022, vol. 299, issue 1, 118-136

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.

Keywords: Networks; Integer programming; Polar Duality; Cutting-Plane (search for similar items in EconPapers)
Date: 2022
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0377221721007359
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:ejores:v:299:y:2022:i:1:p:118-136

DOI: 10.1016/j.ejor.2021.08.043

Access Statistics for this article

European Journal of Operational Research is currently edited by Roman Slowinski, Jesus Artalejo, Jean-Charles. Billaut, Robert Dyson and Lorenzo Peccati

More articles in European Journal of Operational Research from Elsevier
Bibliographic data for series maintained by Catherine Liu ().