Chvatal function

From Glossary

Jump to: navigation, search


This class is defined recursively:

  • LaTeX: F is a Chvatal function (of rank 0) if it is a linear function.
  • If LaTeX: F and LaTeX: G are Chvatal functions, then LaTeX: aF+bG is a Chvatal function for any nonnegative LaTeX: a and LaTeX: b, and its rank is LaTeX:  \max \{\mbox{rank}(F), \mbox{rank}(G)\}. (Some require LaTeX: a and LaTeX: b to be rational.)
  • If LaTeX: F is a Chvatal function of rank LaTeX: r, then LaTeX: | F | is a Chvatal function, and its rank is LaTeX: r+1 if LaTeX: | F | is not equal to LaTeX: F.

This arises in integer linear programming in several ways, see Gomory function.


Views
Personal tools