Equivariant perturbation in Gomory and Johnson's infinite group problem. III: Foundations for the \(k\)-dimensional case with applications to \(k=2\) (Q526839): Difference between revisions

From MaRDI portal
Importer (talk | contribs)
Created a new Item
 
Importer (talk | contribs)
Changed an Item
Property / review text
 
This paper develops foundational tools for classifying the extreme valid functions for the \(k\)-dimensional infinite group problem. The authors present the general regular solution to Cauchy's additive functional equation on restricted lower-dimensional convex domains. This provides a \(k\)-dimensional generalization of the so-called interval lemma, allowing them to deduce affine properties of the function from certain additivity relations. Next, they study the discrete geometry of additivity domains of piecewise linear functions, providing a framework for finite tests of minimality and extremality. They then give a theory of non-extremality certificates in the form of perturbation functions. They apply these tools in the context of minimal valid functions for the two-dimensional infinite group problem that are piecewise linear on a standard triangulation of the plane, under a regularity condition called diagonal constrainedness. They show that the extremality of a minimal valid function is equivalent to the extremality of its restriction to a certain finite two-dimensional group problem. This gives an algorithm for testing the extremality of a given minimal valid function. For Part I and II see [Math. Oper. Res. 40, No. 1, 105--129 (2015; Zbl 1308.90106)] and [Lect. Notes Comput. Sci. 7801, 62--73 (2013; Zbl 1372.90070)].
Property / review text: This paper develops foundational tools for classifying the extreme valid functions for the \(k\)-dimensional infinite group problem. The authors present the general regular solution to Cauchy's additive functional equation on restricted lower-dimensional convex domains. This provides a \(k\)-dimensional generalization of the so-called interval lemma, allowing them to deduce affine properties of the function from certain additivity relations. Next, they study the discrete geometry of additivity domains of piecewise linear functions, providing a framework for finite tests of minimality and extremality. They then give a theory of non-extremality certificates in the form of perturbation functions. They apply these tools in the context of minimal valid functions for the two-dimensional infinite group problem that are piecewise linear on a standard triangulation of the plane, under a regularity condition called diagonal constrainedness. They show that the extremality of a minimal valid function is equivalent to the extremality of its restriction to a certain finite two-dimensional group problem. This gives an algorithm for testing the extremality of a given minimal valid function. For Part I and II see [Math. Oper. Res. 40, No. 1, 105--129 (2015; Zbl 1308.90106)] and [Lect. Notes Comput. Sci. 7801, 62--73 (2013; Zbl 1372.90070)]. / rank
 
Normal rank
Property / reviewed by
 
Property / reviewed by: Matthias Ehrgott / rank
 
Normal rank
Property / Mathematics Subject Classification ID
 
Property / Mathematics Subject Classification ID: 90C10 / rank
 
Normal rank
Property / Mathematics Subject Classification ID
 
Property / Mathematics Subject Classification ID: 90C57 / rank
 
Normal rank
Property / Mathematics Subject Classification ID
 
Property / Mathematics Subject Classification ID: 39B52 / rank
 
Normal rank
Property / Mathematics Subject Classification ID
 
Property / Mathematics Subject Classification ID: 39B62 / rank
 
Normal rank
Property / zbMATH DE Number
 
Property / zbMATH DE Number: 6715570 / rank
 
Normal rank
Property / zbMATH Keywords
 
cutting planes
Property / zbMATH Keywords: cutting planes / rank
 
Normal rank
Property / zbMATH Keywords
 
infinite group problem
Property / zbMATH Keywords: infinite group problem / rank
 
Normal rank
Property / zbMATH Keywords
 
Cauchy's functional equation
Property / zbMATH Keywords: Cauchy's functional equation / rank
 
Normal rank
Property / zbMATH Keywords
 
minimal valid functions
Property / zbMATH Keywords: minimal valid functions / rank
 
Normal rank

Revision as of 06:50, 1 July 2023

scientific article
Language Label Description Also known as
English
Equivariant perturbation in Gomory and Johnson's infinite group problem. III: Foundations for the \(k\)-dimensional case with applications to \(k=2\)
scientific article

    Statements

    Equivariant perturbation in Gomory and Johnson's infinite group problem. III: Foundations for the \(k\)-dimensional case with applications to \(k=2\) (English)
    0 references
    0 references
    0 references
    0 references
    15 May 2017
    0 references
    This paper develops foundational tools for classifying the extreme valid functions for the \(k\)-dimensional infinite group problem. The authors present the general regular solution to Cauchy's additive functional equation on restricted lower-dimensional convex domains. This provides a \(k\)-dimensional generalization of the so-called interval lemma, allowing them to deduce affine properties of the function from certain additivity relations. Next, they study the discrete geometry of additivity domains of piecewise linear functions, providing a framework for finite tests of minimality and extremality. They then give a theory of non-extremality certificates in the form of perturbation functions. They apply these tools in the context of minimal valid functions for the two-dimensional infinite group problem that are piecewise linear on a standard triangulation of the plane, under a regularity condition called diagonal constrainedness. They show that the extremality of a minimal valid function is equivalent to the extremality of its restriction to a certain finite two-dimensional group problem. This gives an algorithm for testing the extremality of a given minimal valid function. For Part I and II see [Math. Oper. Res. 40, No. 1, 105--129 (2015; Zbl 1308.90106)] and [Lect. Notes Comput. Sci. 7801, 62--73 (2013; Zbl 1372.90070)].
    0 references
    cutting planes
    0 references
    infinite group problem
    0 references
    Cauchy's functional equation
    0 references
    minimal valid functions
    0 references

    Identifiers

    0 references
    0 references
    0 references
    0 references
    0 references