Dual-feasible functions for integer programming and combinatorial optimization: Algorithms, characterizations, and approximations
Dual-feasible functions for integer programming and combinatorial optimization: Algorithms, characterizations, and approximations
复制标题
用于整数规划和组合优化的双重可行函数：算法、表征和近似
DOI：
10.1016/j.dam.2019.11.021
复制
发表时间：
2019
影响因子：
1.1
通讯作者：
Wang, Jiawei
中科院分区：
文献类型：
--
作者：
Köppe, Matthias;Wang, Jiawei
在整数规划的超加性对偶理论的框架内，我们研究了单个实变量的两种类型的对偶可行函数（Alves et al., 2016）。我们引入了自动测试分段线性函数的极大值和极值的软件，从而实现基于计算机的搜索。我们建立了与 Gomory-Johnson 及相关模型中的割生成函数的连接，完成了极大函数的表征，并证明了 Gomory-Johnson 2-斜率定理和 Basu-Hildebrand-Molinaro 近似定理的类似物。
Within the framework of the superadditive duality theory of integer programming, we study two types of dual-feasible functions of a single real variable (Alves et al., 2016). We introduce software that automates testing piecewise linear functions for maximality and extremality, enabling a computer-based search. We build a connection to cut-generating functions in the Gomory–Johnson and related models, complete the characterization of maximal functions, and prove analogues of the Gomory–Johnson 2-slope theorem and the Basu–Hildebrand–Molinaro approximation theorem.