Characterization and approximation of strong general dual feasible functions
From MaRDI portal
Publication:1661895
Abstract: Dual feasible functions (DFFs) have been used to provide bounds for standard packing problems and valid inequalities for integer optimization problems. In this paper, the connection between general DFFs and a particular family of cut-generating functions is explored. We find the characterization of (restricted/strongly) maximal general DFFs and prove a 2-slope theorem for extreme general DFFs. We show that any restricted maximal general DFF can be well approximated by an extreme general DFF.
Recommendations
- Dual-feasible functions for integer programming and combinatorial optimization. Basics, extensions and applications
- Dual-feasible functions for integer programming and combinatorial optimization: algorithms, characterizations, and approximations
- Theoretical investigations on maximal dual feasible functions
- A survey of dual-feasible and superadditive functions
- On the extremality of maximal dual feasible functions
Cited in
(7)- A survey of dual-feasible and superadditive functions
- On the extremality of maximal dual feasible functions
- Constructing general dual-feasible functions
- Structure and interpretation of dual-feasible functions
- Dual-feasible functions for integer programming and combinatorial optimization: algorithms, characterizations, and approximations
- Theoretical investigations on maximal dual feasible functions
- Using dual feasible functions to construct fast lower bounds for routing and location problems
This page was built for publication: Characterization and approximation of strong general dual feasible functions
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1661895)
