Subadditive Approaches to Mixed Integer Programming

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.