Premium
Reduced‐size formulations for metric and cut polyhedra in sparse graphs
Author(s) -
Nguyen Viet Hung,
Minoux Michel,
Nguyen Dang Phuong
Publication year - 2017
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.21723
Subject(s) - polytope , mathematics , polyhedron , combinatorics , metric space , metric (unit) , reduction (mathematics) , graph , discrete mathematics , time complexity , operations management , geometry , economics
Given a graph G = ( V , E ) with | V | = n and | E | = m , we consider the metric cone MET ( G ) and the metric polytope METP ( G ) defined onℝ E . These polyhedra are relaxations of several important problems in combinatorial optimization such as the max‐cut problem and the multicommodity flow problem. They are known to have non‐compact formulations via the cycle inequalities in the original spaceℝ Eand compact (i.e., polynomial size) extended formulations via the triangle inequalities defined on the complete graphK n . In this article, we show that one can reduce the number of triangle inequalities to O ( n m ) and still have extended formulations for MET ( G ) and METP ( G ) . This is particularly interesting for sparse graphs when m = O ( n ) , since formulations of size O ( n 2 ) variables and constraints are thus obtained. Moreover, the possibility of achieving further reduction in size for special classes of sparse graphs is investigated; it is shown that for the case of series‐parallel graphs , for which the max‐cut problem can be solved in linear time (Barahona, Discr Appl Math 13 (1986), 23–26), one can refine the above reduction to obtain extended formulations for MET ( G ) and METP ( G ) featuring O ( n ) variables and constraints. © 2016 Wiley Periodicals, Inc. NETWORKS, Vol. 69(1), 142–150 2017