Modaresi, Sina
(2016)
Valid Inequalities and Reformulation Techniques for Mixed Integer Nonlinear Programming.
Doctoral Dissertation, University of Pittsburgh.
(Unpublished)
Abstract
One of the most important breakthroughs in the area of Mixed Integer Linear Programming (MILP) is the characterization of the convex hull of specially structured non-convex polyhedral sets in order to develop valid inequalities or cutting planes. Development of strong valid inequalities such as Split cuts, Gomory Mixed Integer (GMI) cuts, and Mixed Integer Rounding (MIR) cuts has resulted in highly effective branch-and-cut algorithms. While such cuts are known to be equivalent, each of their characterizations provides different advantages and insights.
The study of cutting planes for Mixed Integer Nonlinear Programming (MINLP) is still much more limited than that for MILP, since characterizing cuts for MINLP requires the study of the convex hull of a non-convex and non-polyhedral set, which has proven to be significantly harder than the polyhedral case. However, there has been significant work on the computational use of cuts in MINLP. Furthermore, there has recently been a significant interest in extending the associated theoretical results from MILP to the realm of MINLP.
This dissertation is focused on the development of new cuts and extended formulations for Mixed Integer Nonlinear Programs. We study the generalization of split, k-branch split, and intersection cuts from Mixed Integer Linear Programming to the realm of Mixed Integer Nonlinear Programming. Constructing such cuts requires calculating the convex hull of the difference between a convex set and an open set with a simple geometric structure. We introduce two techniques to give precise characterizations of such convex hulls and use them to construct split, k-branch split, and intersection cuts for several classes of non-polyhedral sets. We also study the relation between the introduced cuts and some known classes of cutting planes from MILP. Furthermore, we show how an aggregation technique can be easily extended to characterize the convex hull of sets defined by two quadratic or by a conic quadratic and a quadratic inequality. We also computationally evaluate the performance of the introduced cuts and extended formulations on two classes of MINLP problems.
Share
| Citation/Export: |
|
| Social Networking: |
|
Details
| Item Type: |
University of Pittsburgh ETD
|
| Status: |
Unpublished |
| Creators/Authors: |
|
| ETD Committee: |
|
| Date: |
25 January 2016 |
| Date Type: |
Publication |
| Defense Date: |
12 November 2015 |
| Approval Date: |
25 January 2016 |
| Submission Date: |
18 November 2015 |
| Access Restriction: |
No restriction; Release the ETD for access worldwide immediately. |
| Number of Pages: |
120 |
| Institution: |
University of Pittsburgh |
| Schools and Programs: |
Swanson School of Engineering > Industrial Engineering |
| Degree: |
PhD - Doctor of Philosophy |
| Thesis Type: |
Doctoral Dissertation |
| Refereed: |
Yes |
| Uncontrolled Keywords: |
Mixed Integer Nonlinear Programming, Valid Inequality, Split Cut, Intersection Cut, Branch-and-Cut, Extended Formulation |
| Date Deposited: |
25 Jan 2016 21:50 |
| Last Modified: |
15 Nov 2016 14:30 |
| URI: |
http://d-scholarship.pitt.edu/id/eprint/26372 |
Metrics
Monthly Views for the past 3 years
Plum Analytics
Actions (login required)
 |
View Item |
![[img]](http://d-scholarship.pitt.edu/style/images/fileicons/application_pdf.png)
![[feed]](/images/feed-icon-32x32.png){kind=icon}