Скачать или смотреть 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 seconds, on average, which otherwise take around 1,000 seconds with the addition of only the knapsack cover inequalities, and around 4 hours for the Cplex MIP solver at its default setting.

About the Speaker:
Sachin Jayaswal is faculty member in the Production & Quantitative Methods Area at the Indian Institute of Management Ahmedabad (IIMA). His research interests include Facility Location, Network Design, Large-Scale Optimization, and Game-Theoretic Models in Supply Chains. His publications have appeared in peer-reviewed international journals like European Journal of Operational Research, Transportation Research-B, Computers & Operations Research, Annals of Operations Research, Journal of Global Optimization, Optimization Letters, International Journal of Production Research, among others. He serves on the editorial board of OPSEARCH. He teaches courses in Operations Management, Mathematical Modeling for Decision Making, Large Scale Optimization, and Game Theory. Sachin obtained his Ph.D. in Management Sciences from the University of Waterloo, Canada, M.Tech in Industrial Engineer & Operations Research from IIT Bombay, and B.Sc. (Engg.) in Electrical Engineering, with Gold Medal, from Bhagalpur college of Engineering. Prior to his PhD, he worked in the IT industry for some time.