Dual-feasible functions for integer programming and combinatorial optimization: algorithms, characterizations, and approximations

DOI10.1016/J.DAM.2019.11.021MaRDI QIDQ2064286zbMATH OpenOpenAlexWikidataFDO

Authors Matthias Köppe, Jiawei Wang

Publication date 5 January 2022

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.dam.2019.11.021

zbMATH Keywords

integer programmingcut-generating functionsdual-feasible functions2-slope theoremcomputer-based search

Mathematics Subject Classification ID

Optimality conditions and duality in mathematical programming (90C46) Integer programming (90C10)

Recommendations

• A survey of dual-feasible and superadditive functions
• Characterization and approximation of strong general dual feasible functions
• scientific article; zbMATH DE number 2223038
• Theoretical investigations on maximal dual feasible functions
• Structure and interpretation of dual-feasible functions

Cites work

• A \((k+1)\)-slope theorem for the \(k\)-dimensional infinite group relaxation
• A characterization of minimal valid inequalities for mixed integer programs
• An electronic compendium of extreme functions for the Gomory-Johnson infinite group problem
• Cut-generating functions for integer variables
• Cyclic group and knapsack facets
• Dual-feasible functions for integer programming and combinatorial optimization. Basics, extensions and applications
• Equivariant perturbation in Gomory and Johnson's infinite group problem (V). Software for the continuous and discontinuous 1-row case
• Equivariant perturbation in Gomory and Johnson's infinite group problem. I: The one-dimensional case
• Equivariant perturbation in Gomory and Johnson's infinite group problem. VI: The curious case of two-sided discontinuous minimal valid functions
• Exact Algorithm for Minimising the Number of Setups in the One-Dimensional Cutting Stock Problem
• Minimal inequalities
• Minimal inequalities for mixed integer programs
• New computer-based search strategies for extreme functions of the Gomory-Johnson infinite group problem
• On perturbation spaces of minimal valid functions: inverse semigroup theory and equivariant decomposition theorem
• Software for Cut-Generating Functions in the Gomory–Johnson Model and Beyond
• Some continuous functions related to corner polyhedra
• Some continuous functions related to corner polyhedra, II
• Some polyhedra related to combinatorial problems
• The power of pyramid decomposition in Normaliz
• Toward Computer-Assisted Discovery and Automated Proofs of Cutting Plane Theorems

Cited in

(8)

• Dual-feasible functions for integer programming and combinatorial optimization. Basics, extensions and applications
• scientific article; zbMATH DE number 2086935 (Why is no real title available?)
• Success guarantee of dual search in integer programming: \(p\)-th power Lagrangian method.
• On the extremality of maximal dual feasible functions
• Characterization and approximation of strong general dual feasible functions
• A survey of dual-feasible and superadditive functions
• Superadditive characterizations of pure integer programming feasibility
• Structure and interpretation of dual-feasible functions

Describes a project that uses

Uses Software

• GitHub
• cutgeneratingfunctionology
• infinite group relaxation
• SageMath
• Normaliz

This page was built for publication: Dual-feasible functions for integer programming and combinatorial optimization: algorithms, characterizations, and approximations

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2064286)