Parametric Mixed Integer Programming: An Application to Solid Waste Management

A method is developed for carrying out parametric analysis on a mixed integer linear program (MILP) as either objective function coefficients or right-hand-side values of the constraints are varied continuously. The method involves solving MILPs at point values of the parameters of variation and joining the results by LP parametric analysis. The procedure for parametric analysis on the objective function can be continued until a theoretical result proves that the analysis is complete. However, a heuristic rule that is presented may greatly reduce the number of individual MILPs that have to be solved and thus reduce the total computational effort. The rule assumes that if the same values of the integer variables are optimal at two different values of the change parameter, these same integer variable values will also be optimal at all intermediate parameter values. If the rule is applied, a complete parametric analysis requires solving 2n different MILPs, where n is the number of different sets of optimal integer variable values found. We determine the savings in number of MILPs solved using the heuristic rule compared to continuing the procedure to obtain theoretical proof of completeness. The paper also proposes various possible "advanced start" aids for solving the individual MILPs. Previously there has existed no method that could be used to perform continuous right-hand-side parametric analysis on an MILP of realistic size. A heuristic rule presented here makes possible such an analysis. The procedure again requires solving 2n different MILPs. The procedures for both objective function and right-hand-side analysis can be implemented using any software that can solve MILPs and perform LP parametric analysis. Computational results are reported using commercially available packages. The procedures are applied to a large fixed-charge model that was developed to analyze where to locate resource recovery plants in Southeastern Ontario. In that model it was essential to consider very wide variation in values of the parameters related to resource recovery. It was found that the results of the parametric analyses could be distilled into clear recommendations regarding which plants to build if a resource recovery policy is implemented.