English

运筹学学报 >

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

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

 

分段线性的不可分流弧集多面体研究

展开
  • 1. 数学与信息网络教育部重点实验室 (北京邮电大学), 北京 100876
    2. 北京邮电大学理学院, 北京 100876
    3. 中国科学院数学与系统科学研究院计算数学与科学工程计算研究所, 北京 100190
寇彩霞, E-mail: koucx@bupt.edu.cn

收稿日期: 2024-04-05

  网络出版日期: 2024-12-20

基金资助

重点研发计划(2022YFB2403400);北京自然科学基金(Z220004);中央高校基本科研业务费专项资金(2023ZCJH02)

版权

运筹学学报编辑部, 2024, 版权所有，未经授权。
收起

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

摘要

分段线性函数在运输、通信和生产规划等领域都有着重要的应用。本文聚焦于目标函数是分段线性函数的不可分多商品流问题。通过引入额外的0-1变量, 该问题可建模为混合整数线性规划问题。我们以分段线性不可分流弧集多面体作为子结构提出两类有效不等式, 并进一步给出了这些不等式定义多面体刻面的充要条件。数值实验通过对不可分多商品流问题产生割平面, 说明了这些有效不等式作为割平面对求解不可分多商品流问题的有效性。

关键词： 割平面; 混合整数规划; 网络设计; 分段线性优化

本文引用格式

黄诗语, 陈亮, 寇彩霞 . 分段线性的不可分流弧集多面体研究[J]. 运筹学学报, 2024 , 28(4) : 101 -110 . DOI: 10.15960/j.cnki.issn.1007-6093.2024.04.009

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

参考文献

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
文章导航

/

〈 〉