Tight Polyhedral Representations of Discrete Sets Using Projections, Simplices, and Base-2 Expansions

This research effort focuses on the acquisition of polyhedral outer-approximations to the convex hull of feasible solutions for mixed-integer linear and mixed-integer nonlinear programs. The goal is to produce desirable formulations that have superior size and/or relaxation strength. These two qualities often have great influence on the success of underlying solution strategies, and so it is with these qualities in mind that the work of this dissertation presents three distinct contributions. The first studies a family of relatively unknown polytopes that enable the linearization of polynomial expressions involving two discrete variables. Projections of higher-dimensional convex hulls are employed to reduce the dimensionality of the requisite linearizing polyhedra. For certain lower dimensions, a complete characterization of the convex hull is obtained; for others, a family of facets is acquired. Furthermore, a novel linearization for the product of a bounded continuous variable and a general discrete variable is obtained. The second contribution investigates the use of simplicial facets in the formation of novel convex hull representations for a class of mixed-discrete problems having a subset of their variables taking on discrete, affinely independent realizations. These simplicial facets provide new theoretical machinery necessary to extend the reformulation-linearization technique (RLT) for mixed-binary and mixed-discrete programs. In doing so, new insight is provided which allows for the subsumation of previous mixed-binary and mixed-discrete RLT results. The third contribution presents a novel approach for representing functions of discrete variables and their products using logarithmic numbers of 0-1 variables in order to economize on the number of these binary variables. Here, base-2 expansions are used within linear restrictions to enforce the appropriate behavior of functions of discrete variables. Products amongst functions are handled by scaling these linear restrictions. This approach provides insight into, improves upon, and subsumes recent related linearization methods from the literature.