Parametric mixed-integer 0–1 linear programming: The general case for a single parameter |
| |
Authors: | Alexander Mitsos Paul I. Barton |
| |
Affiliation: | Department of Chemical Engineering, Massachusetts Institute of Technology, 66-464, 77 Massachusetts Avenue, Cambridge, MA 02139, United States |
| |
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. |
| |
Keywords: | Parametric programming Post-optimality sensitivity analysis Matrix case MILP MINLP |
本文献已被 ScienceDirect 等数据库收录! |
|