Subadditive Approaches to Mixed Integer Programming

It appears your Web browser is not configured to display PDF files. Download adobe Acrobat or click here to download the PDF file.

Click here to download the PDF file.

Creator: 

Moazzez, Babak

Date: 

2014

Abstract: 

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.

Subject: 

Mathematics

Language: 

English

Publisher: 

Carleton University

Thesis Degree Name: 

Doctor of Philosophy: 
Ph.D.

Thesis Degree Level: 

Doctoral

Thesis Degree Discipline: 

Applied Mathematics

Parent Collection: 

Theses and Dissertations

Items in CURVE are protected by copyright, with all rights reserved, unless otherwise indicated. They are made available with permission from the author(s).