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

DOI10.1016/j.dam.2019.11.021zbMath1483.90081OpenAlexW2998244089WikidataQ114191509 ScholiaQ114191509MaRDI QIDQ2064286

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

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

Uses Software

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

Cites Work

• Light on the infinite group relaxation. I: Foundations and taxonomy
• The power of pyramid decomposition in Normaliz
• A characterization of minimal valid inequalities for mixed integer programs
• Minimal inequalities for mixed integer programs
• Cyclic group and knapsack facets
• New computer-based search strategies for extreme functions of the Gomory-Johnson infinite group problem
• Equivariant perturbation in Gomory and Johnson's infinite group problem. VI: The curious case of two-sided discontinuous minimal valid functions
• An electronic compendium of extreme functions for the Gomory-Johnson infinite group problem
• Extreme functions with an arbitrary number of slopes
• Minimal cut-generating functions are nearly extreme
• On perturbation spaces of minimal valid functions: inverse semigroup theory and equivariant decomposition theorem
• Some polyhedra related to combinatorial problems
• Dual-feasible functions for integer programming and combinatorial optimization. Basics, extensions and applications
• Software for Cut-Generating Functions in the Gomory–Johnson Model and Beyond
• Cut-Generating Functions for Integer Variables
• Toward Computer-Assisted Discovery and Automated Proofs of Cutting Plane Theorems
• A $(k+1)$-Slope Theorem for the $k$-Dimensional Infinite Group Relaxation
• Minimal inequalities
• Exact Algorithm for Minimising the Number of Setups in the One-Dimensional Cutting Stock Problem
• 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
• Some continuous functions related to corner polyhedra
• Some continuous functions related to corner polyhedra, II