Hostname: page-component-77c89778f8-n9wrp Total loading time: 0 Render date: 2024-07-23T15:02:07.021Z Has data issue: false hasContentIssue false
  • English
  • Français

An algorithm for multiparametric min max 0-1-integer programmingproblems relative to the objective function

Published online by Cambridge University Press:  08 April 2006

José Luis Quintero  and
Alejandro Crema
José Luis Quintero
Affiliation:
Departamento de Matemáticas Aplicadas, Facultad de Ingeniería, Universidad Central de Venezuela; quintero [email protected]
Alejandro Crema
Affiliation:
Escuela de Computación, Facultad de Ciencias, Universidad Central de Venezuela. Apartado 47002, Caracas 1041-A, Venezuela; [email protected]
Get access

Abstract

The multiparametric min max 0-1-Integer Programming (0-1-IP) problem relative to the objective function is a family of min max 0-1-IP problems which are related by having identical constraint matrix and right-hand-side vector. In this paper we present an algorithm to perform a complete multiparametric analysis relative to the objective function.

Keywords

0-1-Integer Programmingmultiparametric programmingBottleneck problem.
Type
Research Article
Information
RAIRO - Operations Research , Volume 39 , Issue 4 , October 2005 , pp. 243 - 252
Copyright
© EDP Sciences, 2006

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

H. Arsham, http://ubmail.ubalt.edu/~harsham/refop/Refop.htm
Crema, A., A contraction algorithm for the multiparametric integer linear programming problem. Eur. J. Oper. Res. 101 (1997) 130–139. CrossRef
Crema, A., An algorithm for the multiparametric 0-1-integer linear programming problem relative to the objective function. Eur. J. Oper. Res. 125 (2000) 18–24. CrossRef
Crema, A., An algorithm for the multiparametric 0-1-integer linear programming problem relative to the constraint matrix. Oper. Res. Lett. 27 (2000) 1–46. CrossRef
Crema, A., The multiparametric 0-1-Integer Linear Programming problem: A unified approach. Eur. J. Oper. Res. 139 (2002) 511–520. CrossRef
Geoffrion, A.M. and Nauss, R., Parametric and postoptimality analysis in integer linear programming. Manage. Sci. 23 (1977) 453–466. CrossRef
H.J. Greenberg, An annoted bibliography for post-solution analysis in mixed integer propgramming and combinatorial optimization, Advances in Computational and Stochastic Optimization, Logic Programming and Heuristic Search, edited by D.L. Woodruff. Kluwer Academic Publishers, Boston, MA (1998) 97–148.
H.J. Greenberg, An annoted bibliography for post-solution analysis in mixed integer programming and combinatorial optimization, http://carbon.cudenver.edu/~ hgreenbe/aboutme/pubrec.html
Jenkins, L., Parametric methods in integer linear programming. Ann. Oper. Res. 27 (1990) 77–96. CrossRef
Jenkins, L., Parametric mixed integer programming: an application to solid waste management. Manage. Sci. 28 (1982) 1270–1284. CrossRef
Jenkins, L., Using parametric integer programming to plan the mix of an air transport fleet. INFOR 25 (1987) 117–135.
Jenkins, L., Parametric-objective integer programming using knapsack facets and Gomory cutting planes. Eur. J. Oper. Res. 31 (1987) 102–109. CrossRef
Martello, S. and Toth, P., The bottleneck generalized assignment problem. Eur. J. Oper. Res. 83 (1995) 621–638. CrossRef
Optimization Subroutine Library, release 2, Guide and Reference, IBM (1992).
IBM Optimization Library C, Application Programming Interface. Available at http://www-306.ibm.com/software/data/bi/osl/pubs/library/featCAPI.htm
Oral, M. and Kettani, O., A linearization procedure for quadratic and cubic mixed integer problems. Oper. Res. 40 (1992) S109–S116. CrossRef
B. Thiongane, A. Nagih and G. Plateau, Theoretical and algorithmic study for parametric 0–1 linear programs relative to the objective function. Math. Program, submitted.