Light on the infinite group relaxation. I: Foundations and taxonomy
From MaRDI portal
Publication:262442
DOI10.1007/S10288-015-0292-9zbMath1353.90089arXiv1410.8584OpenAlexW204293848MaRDI QIDQ262442
Matthias Köppe, Robert Hildebrand, Amitabh Basu
Publication date: 29 March 2016
Published in: 4OR (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1410.8584
integer programmingcutting planescut-generating functionsinfinite group problemminimal and extreme functions
Related Items (23)
Theoretical challenges towards cutting-plane selection ⋮ The structure of the infinite models in integer programming ⋮ Structure and interpretation of dual-feasible functions ⋮ New computer-based search strategies for extreme functions of the Gomory-Johnson infinite group problem ⋮ Optimal Cutting Planes from the Group Relaxations ⋮ Approximation of Minimal Functions by Extreme Functions ⋮ Nonunique Lifting of Integer Variables in Minimal Inequalities ⋮ Can Cut-Generating Functions Be Good and Efficient? ⋮ Equivariant perturbation in Gomory and Johnson's infinite group problem (V). Software for the continuous and discontinuous 1-row case ⋮ Some cut-generating functions for second-order conic sets ⋮ Equivariant perturbation in Gomory and Johnson's infinite group problem. VI: The curious case of two-sided discontinuous minimal valid functions ⋮ Facets, weak facets, and extreme functions of the Gomory-Johnson infinite group problem ⋮ Piecewise smooth extreme functions are piecewise linear ⋮ An extreme function which is nonnegative and discontinuous everywhere ⋮ Extreme functions with an arbitrary number of slopes ⋮ Minimal cut-generating functions are nearly extreme ⋮ The strength of multi-row aggregation cuts for sign-pattern integer programs ⋮ Software for Cut-Generating Functions in the Gomory–Johnson Model and Beyond ⋮ Dual-feasible functions for integer programming and combinatorial optimization: algorithms, characterizations, and approximations ⋮ Toward Computer-Assisted Discovery and Automated Proofs of Cutting Plane Theorems ⋮ Equivariant perturbation in Gomory and Johnson's infinite group problem. VII: Inverse semigroup theory, closures, decomposition of perturbations ⋮ A geometric approach to cut-generating functions ⋮ Light on the infinite group relaxation. I: Foundations and taxonomy
Uses Software
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- cutgeneratingfunctionology
- Light on the infinite group relaxation. I: Foundations and taxonomy
- Unique lifting of integer variables in minimal inequalities
- A counterexample to a conjecture of Gomory and Johnson
- Equivariant perturbation in Gomory and Johnson's infinite group problem. III: Foundations for the \(k\)-dimensional case with applications to \(k=2\)
- Revival of the Gomory cuts in the 1990's
- The atoms of integer programming
- On the extreme inequalities of infinite group problems
- George Dantzig's contributions to integer programming
- Relations between facets of low- and high-dimensional group problems
- Valid inequalities for mips and group polyhedra from approximate liftings
- Strengthening cuts for mixed integer programs
- A class of facet producing graphs for vertex packing polyhedra
- On certain polytopes associated with graphs
- Corner polyhedra and their connection with cutting planes
- T-space and cutting planes
- Cyclic group and knapsack facets
- Strengthening Chvátal-Gomory cuts and Gomory fractional cuts
- New computer-based search strategies for extreme functions of the Gomory-Johnson infinite group problem
- An electronic compendium of extreme functions for the Gomory-Johnson infinite group problem
- A lift-and-project cutting plane algorithm for mixed 0-1 programs
- Generalized mixed integer rounding inequalities: Facets for infinite group polyhedra
- A 3-slope theorem for the infinite relaxation in the plane
- Some polyhedra related to combinatorial problems
- Gomory cuts revisited
- Valid inequalities based on simple mixed-integer sets
- Two row mixed-integer cuts via lifting
- A $(k+1)$-Slope Theorem for the $k$-Dimensional Infinite Group Relaxation
- Unique Minimal Liftings for Simplicial Polytopes
- Clique Tree Inequalities and the Symmetric Travelling Salesman Problem
- On the symmetric travelling salesman problem I: Inequalities
- On the symmetric travelling salesman problem II: Lifting theorems and facets
- Constrained Infinite Group Relaxations of MIPs
- Minimal Inequalities for an Infinite Relaxation of Integer Programs
- A Geometric Perspective on Lifting
- Minimal Valid Inequalities for Integer Constraints
- Maximal Lattice-Free Convex Sets in Linear Subspaces
- Outline of an algorithm for integer solutions to linear programs
- The Group-Theoretic Approach in Mixed Integer Programming
- The traveling salesman problem on a graph and some related integer polyhedra
- Faces for a linear inequality in 0–1 variables
- Facets of the knapsack polytope
- Mixed 0-1 Programming by Lift-and-Project in a Branch-and-Cut Framework
- Halin graphs and the travelling salesman problem
- Properties of vertex packing and independence system polyhedra
- Equivariant Perturbation in Gomory and Johnson’s Infinite Group Problem: II. The Unimodular Two-Dimensional Case
- On the facial structure of set packing polyhedra
- Equivariant Perturbation in Gomory and Johnson's Infinite Group Problem. I. The One-Dimensional Case
- Cut-Generating Functions and S-Free Sets
- ON THE RELATION BETWEEN INTEGER AND NONINTEGER SOLUTIONS TO LINEAR PROGRAMS
- Solution of a Large-Scale Traveling-Salesman Problem
- Facets of Two-Dimensional Infinite Group Problems
- On the Unique-Lifting Property
- Inequalities from Two Rows of a Simplex Tableau
- Intersection Cuts—A New Type of Cutting Planes for Integer Programming
- Some continuous functions related to corner polyhedra
- Some continuous functions related to corner polyhedra, II
This page was built for publication: Light on the infinite group relaxation. I: Foundations and taxonomy
