## Abstract

The non-extreme minimal valid functions for the Gomory–Johnson infinite group problem are those that admit effective perturbations. For a class of piecewise linear functions for the 1-row problem we give a precise description of the space of these perturbations as a direct sum of certain finite- and infinite-dimensional subspaces. The infinite-dimensional subspaces have partial symmetries; to describe them, we develop a theory of inverse semigroups of partial bijections, interacting with the functional equations satisfied by the perturbations. Our paper provides the foundation for grid-free algorithms for testing extremality and for computing liftings of non-extreme functions. The grid-freeness makes the algorithms suitable for piecewise linear functions whose breakpoints are rational numbers with huge denominators.

Original language | English |
---|---|

Title of host publication | Integer Programming and Combinatorial Optimization - 20th International Conference, IPCO 2019, Proceedings |

Editors | Andrea Lodi, Viswanath Nagarajan |

Pages | 247-260 |

Number of pages | 14 |

DOIs | |

State | Published - 2019 |

Event | 20th International Conference on Integer Programming and Combinatorial Optimization, IPCO 2019 - Ann Arbor, United States Duration: May 22 2019 → May 24 2019 |

### Publication series

Name | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) |
---|---|

Volume | 11480 LNCS |

ISSN (Print) | 0302-9743 |

ISSN (Electronic) | 1611-3349 |

### Conference

Conference | 20th International Conference on Integer Programming and Combinatorial Optimization, IPCO 2019 |
---|---|

Country/Territory | United States |

City | Ann Arbor |

Period | 5/22/19 → 5/24/19 |

### Bibliographical note

Publisher Copyright:© 2019, Springer Nature Switzerland AG.

## Keywords

- Cutting planes
- Group relaxations
- Integer programs

## ASJC Scopus subject areas

- Theoretical Computer Science
- General Computer Science