Date of Award

5-2011

Document Type

Dissertation

Degree Name

Doctor of Philosophy (PhD)

Legacy Department

Mathematical Science

Committee Chair/Advisor

Adams, Warren

Committee Member

Shier , Douglas

Committee Member

Saltzman , Matthew

Committee Member

Kerivin , Herv

Abstract

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.

Share

COinS
 
 

To view the content in your browser, please download Adobe Reader or, alternately,
you may Download the file to your hard drive.

NOTE: The latest versions of Adobe Reader do not support viewing PDF files within Firefox on Mac OS and if you are using a modern (Intel) Mac, there is no official plugin for viewing PDF files within the browser window.