Subadditive Approaches to Mixed Integer ProgrammingPublic Deposited
Downloadable ContentDownload PDF
- Resource Type
Correctness and efficiency of two algorithms by Burdet and Johnson (1975) and Klabjan (2007) for solving pure integer linear programming problems are studied. These algorithms rely on Gomory's corner relaxation and subadditive duality. Examples are given to demonstrate the failure of these algorithms on specific IPs and ways of correcting errors in some cases are given. Klabjan's Generator Subadditive Functions have been generalized for mixed integer linear programs. These are (subadditive) dual feasible functions which have desirable properties that allow us to use them as certificates of optimality and for sensitivity analysis purposes. Generating certificates of optimality has been done for specific families of discrete optimization problems such as set covering and knapsack problems using (mixed) integer programming formulations. Some computational results have been reported on these problems at the end. Also, subadditive generator functions have been used for finding a finite representation of the convex hull of MILPs which is a generalization of Bachem and Schrader's and Wolsey's works on finite representations and value functions of (mixed) integer linear programs. Babak Moazzez, Carleton University, Thesis (PhD), 2014, Pages: 117.
- Thesis Degree Level
- Thesis Degree Name
- Thesis Degree Discipline
- Rights Notes
- Copyright © 2014 the author(s). Theses may be used for non-commercial research, educational, or related academic purposes only. Such uses include personal study, research, scholarship, and teaching. Theses may only be shared by linking to Carleton University Institutional Repository and no part may be used without proper attribution to the author. No part may be used for commercial purposes directly or indirectly via a for-profit platform; no adaptation or derivative works are permitted without consent from the copyright owner.
- Date Created
- In Collection: