Parametric mixed-integer 0-1 linear programming: The general case for a single parameter

TitleParametric mixed-integer 0-1 linear programming: The general case for a single parameter
Publication TypeJournal Article
Year of Publication2009
AuthorsMitsos A, Barton PI
JournalEuropean Journal of Operational Research
Volume194
Pagination663 - 686
ISSN0377-2217
KeywordsMatrix case, MILP, MINLP, Parametric programming, Post-optimality sensitivity analysis
Abstract

Two algorithms for the general case of parametric mixed-integer linear programs (MILPs) are proposed. Parametric MILPs are considered in which a single parameter can simultaneously influence the objective function, the right-hand side and the matrix. The first algorithm is based on branch-and-bound on the integer variables, solving a parametric linear program (LP) at each node. The second algorithm is based on the optimality range of a qualitatively invariant solution, decomposing the parametric optimization problem into a series of regular MILPs, parametric LPs and regular mixed-integer nonlinear programs (MINLPs). The number of subproblems required for a particular instance is equal to the number of critical regions. For the parametric LPs an improvement of the well-known rational simplex algorithm is presented, that requires less consecutive operations on rational functions. Also, an alternative based on predictor-corrector continuation is proposed. Numerical results for a test set are discussed.

URLhttp://www.sciencedirect.com/science/article/B6VCT-4RM7MXF-4/2/6fb3d08f911e56398d171b4361ff7bb5
DOI10.1016/j.ejor.2008.01.007