(12a) Parametric Mixed-Integer Linear Programming: the General Case

Mathematical programs often involve unknown parameters and the task of parametric optimization is, in principle, to solve the mathematical program for all possible values of these unknown parameters. Obviously this is not explicitly possible for real-valued parameters. Discretization approaches are non-rigorous since there is no guarantee for optimality between the mesh points. Therefore, algorithms for parametric optimization typically divide the parameter space into regions of optimality; for each region infeasibility is established or an optimal solution is given as a smooth function of the parameters for this region. For one parameter the transition between the solutions is called a breakpoint and in a sense parametric optimization algorithms identify these breakpoints. It should be noted that the complexity of parametric optimization is not polynomial even in special cases of the parametric linear program [1] and as a consequence any algorithm for more general cases is bound not to be polynomial either.

Parametric optimization has several applications. As a tool for decision making it is useful when the value of the parameters is not known during the optimization phase but known during the decision making phase [2]. Within chemical engineering parametric optimization has been extensively used for applications of model-predictive control, e.g., [3] as well as for process synthesis under uncertainty, e.g., [4]. Another potential application of parametric optimization is as a tool for resource allocation decisions. Suppose that a model contains parameters describing the performance of unit operations; parametric optimization can determine the influence of these parameters on the system performance. Identifying the most critical parameters can help determine whether it is worthwhile to pursue improving the performance of this unit. It can be demonstrated that local post-optimality sensitivity analysis does not always provide a correct estimate of the influence of the parameters.

Parametric optimization is a relatively mature field with many contributions, see, e.g., [5,6,7] for reviews. With the exception of a few algorithms for linear or purely integer programs the available literature assumes that parameters only influence the objective function and/or the right-hand side of the constraints. Extension to the general case where a parameter can simultaneously affect the non-constant part of constraints, the right-hand side and the objective function is non-trivial because the resulting problems do not have the nice structure employed for the special cases. Algorithms dealing with the general case are desired, since it is especially relevant for the resource allocation formulation described above.

In this contribution we focus on mixed-integer linear programs with a single unknown parameter simultaneously affecting the right-hand side vector, the cost vector and the design matrix. We briefly discuss some of the theoretical properties of the problem at hand and the implications for algorithmic development.

The main focus of the presentation is a discussion of the proposed algorithms and their convergence properties. One class of algorithms is based on branch-and-bound on the integer variables, extending the idea of [8] solving a parametric linear program at each node. This class of algorithms has the potential of relatively low computational requirements but with the drawback of significant implementation requirements. In principle an algorithm based on rational operations [9] could be used for the parametric linear programs and we propose computational improvements of this algorithm. For real-world problems, rational operations are not practical and therefore we also propose an algorithm for parametric linear programs based on parametric solution with a continuation method. The other class of algorithms proposed is based on decomposition of the parametric optimization problem into a series of optimization problems extending ideas from [10]. This approach involves subproblems that are computationally more expensive but has the benefit that the use of state-of-the art, off-the-shelf codes is made possible.

We present the application of the algorithms to case studies. We first discuss simple numerical examples with some interesting theoretical properties. Subsequently we present case studies taken from man-portable power generation discussing resource allocation, as well as examples from macro-power generation scheduling. Finally we discuss extensions of our algorithms to the nonlinear case and to the multiparametric case.

[1] Katta G. Murty. Computational complexity of parametric linear programming. Mathematical Programming, 19(2):213--219, 1980.

[2] Stein W. Wallace. Decision making under uncertainty: Is sensitivity analysis of any use. Operations Research, 48(1), 2000.

[3] Efstratios N. Pistikopoulos, Vivek Dua, Nikolaos A. Bozinis, Alberto Bemporad and Manfred Morari. On-line optimization via off-line parametric optimization tools. Computers and Chemical Engineering, 24:183--188, 2000.

[4] Ipsita Banerjee and Marianthi G. Ierapetritou. Parametric process synthesis for general nonlinear models. Computers and Chemical Engineering, 27, 2003.

[5] A. M. Geoffrion and R. Nauss. Parametric and postoptimality analysis in integer linear programming. Management Science, 23(5), 1977.

[6] Tomas Gal. Postoptimal Analyses, Parametric Programming and Related Topics. deGruyter, 2nd edition, 1995.

[7] V Dua, K.P. Papalexandri, and E. N. Pistikopoulos. Global optimization issues in multiparametric continuous and mixed-integer optimization problems. Journal of Global Optimization, 30:59--89, 2004.

[8] Yoshiaki Ohtake and Naonori Nishida. A branch-and-bound algorithm for 0-1 parametric mixed integer programming. Operations Research Letters, 4(1):41--45, 1985.

[9] Werner Dinkelbach, editor. Sensitivitätsanalysen und parametrische Programmierung. Springer, 1969.

[10] Anastasios Pertsinidis. On the Parametric Optimization of Mathematical Programs with Binary Variables and its Applications in Chemical Engineering Process Synthesis. PhD thesis, Carnegie Mellon, 1991.