Back to Search
Start Over
Parametric mixed-integer 0–1 linear programming: The general case for a single parameter
- Source :
- European Journal of Operational Research. 194:663-686
- Publication Year :
- 2009
- Publisher :
- Elsevier BV, 2009.
-
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.
- Subjects :
- Predictor–corrector method
Parametric programming
Mathematical optimization
Information Systems and Management
General Computer Science
Linear programming
Rational function
Management Science and Operations Research
Industrial and Manufacturing Engineering
Integer
Simplex algorithm
Modeling and Simulation
Integer programming
Mathematics
Parametric statistics
Subjects
Details
- ISSN :
- 03772217
- Volume :
- 194
- Database :
- OpenAIRE
- Journal :
- European Journal of Operational Research
- Accession number :
- edsair.doi...........46323c819c691b56ff6215c8db6460fd