group relaxation

Equivariant Perturbation in Gomory and Johnson’s Infinite Group Problem. VII. Inverse semigroup theory, closures, decomposition of perturbations

  • Robert Hildebrand
  • Matthias Köppe
  • Yuan Zhou
    • Categories Cutting Plane Approaches Tags , ,

    In this self-contained paper, we present a theory of the piecewise linear minimal valid functions for the 1-row Gomory-Johnson infinite group problem. The non-extreme minimal valid functions are those that admit effective perturbations. We give a precise description of the space of these perturbations as a direct sum of certain finite- and infinite-dimensional subspaces. The … Read more

    All Cyclic Group Facets Inject

  • Matthias Köppe
  • Yuan Zhou
    • Categories Cutting Plane Approaches Tags

    We give a variant of Basu–Hildebrand–Molinaro’s approximation theorem for continuous minimal valid functions for Gomory–Johnson’s infinite group problem by piecewise linear two-slope extreme functions [Minimal cut-generating functions are nearly extreme, IPCO 2016]. Our theorem is for piecewise linear minimal valid functions that have only rational breakpoints (in 1/q Z for some q ∈ N) and … Read more

    New computer-based search strategies for extreme functions of the Gomory–Johnson infinite group problem

  • Matthias Köppe
  • Yuan Zhou
    • Categories (Mixed) Integer Linear Programming, Cutting Plane Approaches Tags , ,

    We describe new computer-based search strategies for extreme functions for the Gomory–Johnson infinite group problem. They lead to the discovery of new extreme functions, whose existence settles several open questions. ArticleDownload View PDF

    Equivariant Perturbation in Gomory and Johnson’s Infinite Group Problem. III. Foundations for the k-Dimensional Case with Applications to k=2

  • Amitabh Basu
  • Robert Hildebrand
  • Matthias Köppe
    • Categories (Mixed) Integer Linear Programming, Cutting Plane Approaches Tags , ,

    We develop foundational tools for classifying the extreme valid functions for the k-dimensional infinite group problem. In particular, (1) we present the general regular solution to Cauchy’s additive functional equation on bounded convex domains. This provides a k-dimensional generalization of the so-called interval lemma, allowing us to deduce affine properties of the function from certain … Read more

    Constrained Infinite Group Relaxations of MIPs

  • Santanu S. Dey
  • Laurence A. Wolsey
    • Categories (Mixed) Integer Linear Programming, Cutting Plane Approaches, Integer Programming Tags , ,

    Recently minimal and extreme inequalities for continuous group relaxations of general mixed integer sets have been characterized. In this paper, we consider a stronger relaxation of general mixed integer sets by allowing constraints, such as bounds, on the free integer variables in the continuous group relaxation. We generalize a number of results for the continuous … Read more