Cut-Generating Functions

International audienceIn optimization problems such as integer programs or their relaxations, one encounters feasible regions that are the inverse images of a specific closed set S by a linear mapping. One would like to generate valid inequalities that cut off infeasible solutions. Formulas for such inequalities can be obtained through cut-generating functions. This paper presents a formal theory of minimal cut-generating functions and maximal S-free sets which is valid independently of the particular S. This theory relies on tools of convex analysis