中文

Operations Research Transactions >

2024 , Vol. 28 >Issue 4: 101 - 110

DOI: https://doi.org/10.15960/j.cnki.issn.1007-6093.2024.04.009

A polyhedral study of piecewise linear unsplittable flow arc set

Expand
  • 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 date: 2024-04-05

  Online published: 2024-12-20

Copyright

, 2024, All rights reserved, without authorization
Fold

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

Cite this article

Shiyu HUANG, Liang CHEN, Caixia KOU . A polyhedral study of piecewise linear unsplittable flow arc set[J]. Operations Research Transactions, 2024 , 28(4) : 101 -110 . DOI: 10.15960/j.cnki.issn.1007-6093.2024.04.009

References

1 BalakrishnanA,GravesS C.A composite algorithm for a concave-cost network flow problem[J].Networks,1989,19(2):175-202.
2 MagnantiT L,MirchandaniP,VachaniR.Modeling and solving the two-facility capacitated network loading problem[J].Operations Research,1995,43(1):142-157.
3 HolmbergK.Solving the staircase cost facility location problem with decomposition and piecewise linearization[J].European Journal of Operational Research,1994,75(1):41-61.
4 CroxtonK L,GendronB,MagnantiT L.A comparison of mixed-integer programming models for nonconvex piecewise linear cost minimization problems[J].Management Science,2003,49(9):1268-1273.
5 SridharS,LinderothJ,LuedtkeJ.Locally ideal formulations for piecewise linear functions with indicator variables[J].Operations Research Letters,2013,41(6):627-632.
6 VielmaJ P,AhmedS,NemhauserG.Mixed-integer models for nonseparable piecewise-linear optimization: Unifying framework and extensions[J].Operations Research,2009,58(2):303-315.
7 CeriaS,CordierC,MarchandH,et al.Cutting planes for integer programs with general integer variables[J].Mathematical Programming,1998,81,201-214.
8 MarchandH,WolseyL A.The 0-1 knapsack problem with a single continuous variable[J].Mathematical Programming,1999,85,15-33.
9 BalasE.Facets of the knapsack polytope[J].Mathematical Programming,1975,8,146-164.
10 WeismantelR.On the 0/1 knapsack polytope[J].Mathematical Programming,1997,77,49-68.
11 GuZ,NemhauserG L,SavelsberghM W.Lifted cover inequalities for 0-1 integer programs: Computation[J].INFORMS Journal on Computing,1998,10(4):427-437.
12 Brockmüller B, Günlück O, Wolsey L A, et al. Designing private line networks-polyhedral analysis and computation[R]. Université catholique de Louvain, Center for Operations Research and Econometrics, 1996.
13 AtamtürkA,RajanD.On splittable and unsplittable flow capacitated network design arc-set polyhedra[J].Mathematical Programming,2002,92(2):315-333.
14 van HoeselS P,KosterA M,van de LeenselR L,et al.Polyhedral results for the edge capacity polytope[J].Mathematical Programming,2002,92,335-358.
15 BenhamicheA,MahjoubA R,PerrotN,et al.Unsplittable non-additive capacitated network design using set functions polyhedra[J].Computers & Operations Research,2016,66,105-115.
16 ChenL,ChenW,YangM,et al.An exact separation algorithm for unsplittable flow capacitated network design arc-set polyhedron[J].Journal of Global Optimization,2021,81,659-689.
17 CroxtonK L,GendronB,MagnantiT L.Variable disaggregation in network flow problems with piecewise linear costs[J].Operations Research,2007,55(1):146-157.
18 CrainicT G,FrangioniA,GendronB.Bundle-based relaxation methods for multicommodity capacitated fixed charge network design[J].Discrete Applied Mathematics,2001,112(1-3):73-99.
19 Achterberg T. Constraint integer programming[D]. Berlin: Technical University of Berlin, 2007.
Options
Outlines

/

〈 〉