Dissertation Defense :: A Polyhedral Study of Nonconvex Piecewise Linear Optimization
Piecewise linear functions are widely used to approximate nonlinear functions. However, when minimizing (maximizing) a piecewise linear function (plf), it is necessary to introduce nonlinearities in the model if the function is not convex (concave). Traditionally the nonlinearities are modelled by introducing auxiliary 0-1 variables and additional constraints that relate the continuous and 0-1 variables or by specialized branching in the scape of continuous variables. We enhance the latter approach through the use of strong inequalities valid for the convex hull of the feasible set in the space of continuous variables. In the thesis we first study the convex hull of single constraint relaxations with only positive coefficients. We then relax this assumption and extend the idea to general single constraint relaxations. We also extend the inequalities to the case where the plf is lower semi-continuous. For each case we report computational results that demonstrate that our approach is significantly better than the traditional approaches to these problems.
- Workflow Status: Published
- Created By: Barbara Christopher
- Created: 10/08/2010
- Modified By: Fletcher Moore
- Modified: 10/07/2016