Software for Cut-Generating Functions in the Gomory–Johnson Model and Beyond

DOI10.1007/978-3-319-42432-3_35zbMATH Open1434.68706arXiv1605.00197OpenAlexW2346911733MaRDI QIDQ2819232FDOQ2819232

Yuan Zhou, Chun Yu Hong, Matthias Köppe

Publication date: 28 September 2016

Published in: Mathematical Software – ICMS 2016 (Search for Journal in Brave)

Abstract: We present software for investigations with cut generating functions in the Gomory-Johnson model and extensions, implemented in the computer algebra system SageMath.

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

zbMATH Keywords

integer programmingcutting planesgroup relaxations

Mathematics Subject Classification ID

Symbolic computation and algebraic computation (68W30) Integer programming (90C10) Software, source code, etc. for problems pertaining to operations research and mathematical programming (90-04)

Cites Work

• Valid inequalities for mips and group polyhedra from approximate liftings
• T-space and cutting planes
• An electronic compendium of extreme functions for the Gomory-Johnson infinite group problem
• Light on the infinite group relaxation. I: Foundations and taxonomy
• Equivariant Perturbation in Gomory and Johnson's Infinite Group Problem. I. The One-Dimensional Case
• Cut-Generating Functions and S-Free Sets
• Some continuous functions related to corner polyhedra
• Some continuous functions related to corner polyhedra, II
• Dual-feasible functions for integer programming and combinatorial optimization. Basics, extensions and applications
• Lifting, superadditivity, mixed integer rounding and single node flow sets revisited
• Extreme functions with an arbitrary number of slopes

Cited In (4)

• Equivariant perturbation in Gomory and Johnson's infinite group problem. VI: The curious case of two-sided discontinuous minimal valid functions
• Structure and interpretation of dual-feasible functions
• Dual-feasible functions for integer programming and combinatorial optimization: algorithms, characterizations, and approximations
• New computer-based search strategies for extreme functions of the Gomory-Johnson infinite group problem

Uses Software

• SageMath
• infinite group relaxation
• GitHub

This page was built for publication: Software for Cut-Generating Functions in the Gomory–Johnson Model and Beyond

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