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

A polyhedral study of piecewise linear unsplittable flow arc set

作　　者：黄诗语 陈亮 寇彩霞 HUANG Shiyu;CHEN Liang;KOU Caixia(KeyLaboratory of Mathematics and Information Networks(Beijing University of Posts and Telecommunications),Ministry of Education,Beijing 100876,China;School of Science,Beijing University of Posts and Telecommunications,Beijing 100876,China;Institute of Computational Mathematics and Scientific/Engineering Computing,Academy of Mathematics and Systems Science,Chinese Academy of Sciences,Beijing 100190,China)

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

出　　处：《运筹学学报(中英文)》2024年第4期101-110,共10页Operations Research Transactions

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

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

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

分 类 号：O221.4[理学—运筹学与控制论]