Multiple and alternate optima of LP problems via recursive MILP : a MATLAB implementation

Abstract

In this thesis, the Recursive Mixed Integer Linear Programming (RMILP) algorithm invented by Prof. Grossman's group at the Carnegie Mellon University is studied. The algorithm is guaranteed to find all the alternate optima of the LP problems. The main advantage of the proposed algorithm is that it can be built on efficient tools such as GAMS algebraic modeling system and does not require any modification of the LP solver. But the RMILP code written in GAMS was not generic. Since it was problem specific coding, it must be changed for each different problem. Prof. Akman generated a generic GAMS code that can be used even by a novice LP user without modification of the recursive MILP part by the user. In this thesis, final tests of Prof. Akman's work and implementation in MATLAB were performed. With this purpose, a MATLAB code consisting of two parts namely, a function part and a main part is developed. In the main part, the user enters the problem specific data and termination criterion. Then the function part is called, where LP and MILP problems are solved recursively. The same function part can be used for any standard LP problem without any modification. The MATLAB code is generic; it can accommodate any LP/MILP solver. The MATLAB code developed provides the user with all the alternate optimal solutions, as well as next K best vertex solutions of an LP problem. With this capability, the decision maker will see the difference between the optimal value and the next best objective function value, or next K best objective function values with a single run of the code. Alternate solutions enable decision maker to make choice by considering other incremental factors that are not explicitly incorporated into the optimization model. Several LP problems were solved using GAMS and MATLAB and the same results were obtained on both software platforms. In both GAMS and MATLAB, some solutions were replicated depending on the LP/MILP solvers. A dendrogram, representing hierarchical solution clusters, was used to visualize the proximity of the alternate solutions and to eliminate replicates.