Title | ||
---|---|---|
Dual-feasible functions for integer programming and combinatorial optimization: Algorithms, characterizations, and approximations |
Abstract | ||
---|---|---|
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. (c) 2019 Elsevier B.V. All rights reserved. |
Year | DOI | Venue |
---|---|---|
2022 | 10.1016/j.dam.2019.11.021 | DISCRETE APPLIED MATHEMATICS |
Keywords | DocType | Volume |
Dual-feasible functions, Cut-generating functions, Integer programming, 2-slope theorem, Computer -based search | Journal | 308 |
ISSN | Citations | PageRank |
0166-218X | 0 | 0.34 |
References | Authors | |
0 | 2 |
Name | Order | Citations | PageRank |
---|---|---|---|
Matthias KöPpe | 1 | 191 | 20.95 |
jiawei wang | 2 | 37 | 11.22 |