首页|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

扫码查看
原文链接
  • NSTL
  • Elsevier
? 2019 Elsevier B.V.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.

2-slope theoremComputer-based searchCut-generating functionsDual-feasible functionsInteger programming

Koppe M.、Wang J.

展开 >

Dept. of Mathematics University of California

2022

10.1016/j.dam.2019.11.021

Discrete Applied Mathematics

Discrete Applied Mathematics

EISCI
ISSN：0166-218X
年,卷(期)：2022.308
  • 30