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

doi:10.15960/j.cnki.issn.1007-6093.2024.04.009

运筹学学报（中英文） ›› 2024, Vol. 28 ›› Issue (4): 101-110.doi: 10.15960/j.cnki.issn.1007-6093.2024.04.009

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

黄诗语¹^,², 陈亮³, 寇彩霞¹^,²^,*()

1. 数学与信息网络教育部重点实验室 (北京邮电大学), 北京 100876
2. 北京邮电大学理学院, 北京 100876
3. 中国科学院数学与系统科学研究院计算数学与科学工程计算研究所, 北京 100190

收稿日期:2024-04-05 出版日期:2024-12-15 发布日期:2024-12-20
通讯作者: 寇彩霞 E-mail:koucx@bupt.edu.cn
基金资助:
重点研发计划(2022YFB2403400);北京自然科学基金(Z220004);中央高校基本科研业务费专项资金(2023ZCJH02)

A polyhedral study of piecewise linear unsplittable flow arc set

Shiyu HUANG¹^,², Liang CHEN³, Caixia KOU¹^,²^,*()

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

摘要：

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

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

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

中图分类号:

O221.4

黄诗语, 陈亮, 寇彩霞. 分段线性的不可分流弧集多面体研究[J]. 运筹学学报（中英文）, 2024, 28(4): 101-110.

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.

图/表 1

参考文献 19

1	BalakrishnanA,GravesS C.A composite algorithm for a concave-cost network flow problem[J].Networks,1989,19(2):175-202. doi: 10.1002/net.3230190202
2	MagnantiT L,MirchandaniP,VachaniR.Modeling and solving the two-facility capacitated network loading problem[J].Operations Research,1995,43(1):142-157. doi: 10.1287/opre.43.1.142
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. doi: 10.1016/0377-2217(94)90184-8
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. doi: 10.1287/mnsc.49.9.1268.16570
5	SridharS,LinderothJ,LuedtkeJ.Locally ideal formulations for piecewise linear functions with indicator variables[J].Operations Research Letters,2013,41(6):627-632. doi: 10.1016/j.orl.2013.08.010
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. doi: 10.1007/s101070050044
9	BalasE.Facets of the knapsack polytope[J].Mathematical Programming,1975,8,146-164. doi: 10.1007/BF01580440
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. doi: 10.1287/ijoc.10.4.427
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. doi: 10.1007/s101070100269
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. doi: 10.1007/s101070200292
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. doi: 10.1007/s10898-020-00967-z
17	CroxtonK L,GendronB,MagnantiT L.Variable disaggregation in network flow problems with piecewise linear costs[J].Operations Research,2007,55(1):146-157. doi: 10.1287/opre.1060.0314
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. doi: 10.1016/S0166-218X(00)00310-3
19	Achterberg T. Constraint integer programming[D]. Berlin: Technical University of Berlin, 2007.

	S	T	N	RGap	NC	ST	TRatio	NRatio
CPX	511	343.9	2 504	93.4	—	—	—	—
CPX+C(R)	509	321.8	2 255	93.7	275	1.9	1.1	1.1
CPX+C(200)	513	304.6	1 932	93.7	557	3.0	1.1	1.3
CPX+C(100)	517	295.8	1 831	93.7	664	3.5	1.2	1.4
CPX+C(50)	519	284.1	1 683	93.7	778	4.4	1.2	1.5
CPX+C(1)	520	273.6	1 147	93.7	1 399	32.8	1.3	2.2

[1]	徐博, 马卫民, 柯华, 张浩. 基于秩2矩阵近似的飞机起降多目标调度模型与算法研究[J]. 运筹学学报（中英文）, 2024, 28(4): 29-43.
[2]	魏贺, 刘昊飞, 许丹丹, 韩雪华, 王良, 张晓东. 双层规划在城市交通领域研究与应用的系统综述[J]. 运筹学学报, 2023, 27(2): 1-26.
[3]	安邦, 程朋. 基于分支割平面的一类无容量限制设施选址问题求解算法[J]. 运筹学学报, 2015, 19(4): 1-13.
[4]	何胜学. 无预警紧急疏散中公交车辆路径的确定方法[J]. 运筹学学报, 2014, 18(3): 47-59.

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

A polyhedral study of piecewise linear unsplittable flow arc set

RichHTML

PDF

可视化

摘要/Abstract

引用本文

使用本文

图/表 1

参考文献 19

相关文章 4

编辑推荐

Metrics

本文评价