Characterization and approximation of strong general dual feasible functions

DOI10.1007/978-3-319-96151-4_23zbMATH Open1403.90576arXiv1801.03591OpenAlexW3098903423MaRDI QIDQ1661895FDOQ1661895

Authors: Matthias Köppe, Jiawei Wang 

Publication date: 17 August 2018

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.

Full work available at URL: https://arxiv.org/abs/1801.03591

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

zbMATH Keywords

integer programmingcut-generating functionsdual feasible functions2-slope theorem

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Integer programming (90C10)

Cited In (4)

• Constructing general dual-feasible functions
• A survey of dual-feasible and superadditive functions
• Theoretical investigations on maximal dual feasible functions
• Structure and interpretation of dual-feasible functions

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)