Representability in mixed integer programming. I: Characterization results (Q1089258)

We define the concept of a representation of a set of either linear constraints in bounded integers, or convex constraints in bounded integers. A regularity condition plays a crucial role in the convex case. Then we characterize the representable sets and provide several examples of our representations. A consequence of our characterization is that the only representable sets are those from 'either/or' constraints. This latter case can be treated by generalizations of techniques from the disjunctive methods of cutting- plane theory. The representations given here are intended for use as part of the constraints of a larger optimization problem, where they often can serve to tighten the (linear or convex) relaxation. The study of representations was initiated by \textit{R. R. Meyer} [Nav. Res. Logist. Q. 28, 115-131 (1981; Zbl 0453.90068)] and in the linear case we continue the development of the author and \textit{J. K. Lowe} [Math. Program. Study 22, 167-184 (1984; Zbl 0554.90081)].