Representability in mixed integer programmiing, I: Characterization results

AbstractWe 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 (Theorem 2.1) 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 (e.g. [2] and [30]).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 Meyer and in the linear case we continue the development in [35]