Operations Research Transactions ›› 2024, Vol. 28 ›› Issue (4): 101-110.doi: 10.15960/j.cnki.issn.1007-6093.2024.04.009

Previous Articles     Next Articles

A polyhedral study of piecewise linear unsplittable flow arc set

Shiyu HUANG1,2, Liang CHEN3, Caixia KOU1,2,*()   

  1. 1. Key Laboratory of Mathematics and Information Networks (Beijing University of Posts and Telecommunications), Ministry of Education, Beijing 100876, China
    2. School of Science, Beijing University of Posts and Telecommunications, Beijing 100876, China
    3. Institute of Computational Mathematics and Scientific/Engineering Computing, Academy of Mathematics and Systems Science, Chinese Academy of Sciences, Beijing 100190, China
  • Received:2024-04-05 Online:2024-12-15 Published:2024-12-20
  • Contact: Caixia KOU E-mail:koucx@bupt.edu.cn

Abstract:

Piecewise linear functions arise in many application domains, including transportation, telecommunications and production planning. In this paper, we concentrate on unsplittable multicommodity network flow problem with piecewise linear objective function. By introducing additional 0-1 variables, it can be modeled as a mixed integer linear programming formulation. We use the piecewise linear unsplittble flow arc set polyhedron of the considered problem as a substructure and derive two classes of valid inequalities. In addition, we describe the necessary and sufficient condition for these derived inequalities to be facet-defining. Finally, we demonstrate the effectiveness of using the derived inequalities as cutting planes to solve piecewise linear unsplittable multicommodity network flow problems by numerical results.

Key words: cutting planes, mixed integer programming, network design, piecewise linear optimization

CLC Number: