کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
477331 | 1446153 | 2009 | 24 صفحه PDF | دانلود رایگان |
![عکس صفحه اول مقاله: Parametric mixed-integer 0–1 linear programming: The general case for a single parameter Parametric mixed-integer 0–1 linear programming: The general case for a single parameter](/preview/png/477331.png)
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.
Journal: European Journal of Operational Research - Volume 194, Issue 3, 1 May 2009, Pages 663–686