An algorithm for multiparametric min max 0-1-integer programming problems relative to the objective function
RAIRO - Operations Research - Recherche Opérationnelle, Volume 39 (2005) no. 4, p. 243-252

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.

DOI : https://doi.org/10.1051/ro:2006004
Keywords: 0-1-integer programming, multiparametric programming, bottleneck problem
@article{RO_2005__39_4_243_0,
     author = {Quintero, Jos\'e Luis and Crema, Alejandro},
     title = {An algorithm for multiparametric min max 0-1-integer programming problems relative to the objective function},
     journal = {RAIRO - Operations Research - Recherche Op\'erationnelle},
     publisher = {EDP-Sciences},
     volume = {39},
     number = {4},
     year = {2005},
     pages = {243-252},
     doi = {10.1051/ro:2006004},
     zbl = {pre05233850},
     mrnumber = {2208752},
     language = {en},
     url = {http://www.numdam.org/item/RO_2005__39_4_243_0}
}
Quintero, José Luis; Crema, Alejandro. An algorithm for multiparametric min max 0-1-integer programming problems relative to the objective function. RAIRO - Operations Research - Recherche Opérationnelle, Volume 39 (2005) no. 4, pp. 243-252. doi : 10.1051/ro:2006004. http://www.numdam.org/item/RO_2005__39_4_243_0/

[1] H. Arsham, http://ubmail.ubalt.edu/~harsham/refop/Refop.htm

[2] A. Crema, A contraction algorithm for the multiparametric integer linear programming problem. Eur. J. Oper. Res. 101 (1997) 130-139. | Zbl 0916.90209

[3] A. Crema, An algorithm for the multiparametric 0-1-integer linear programming problem relative to the objective function. Eur. J. Oper. Res. 125 (2000) 18-24. | Zbl 0972.90049

[4] A. Crema, An algorithm for the multiparametric 0-1-integer linear programming problem relative to the constraint matrix. Oper. Res. Lett. 27 (2000) 1-46. | Zbl 0960.90063

[5] A. Crema, The multiparametric 0-1-Integer Linear Programming problem: A unified approach. Eur. J. Oper. Res. 139 (2002) 511-520. | Zbl 1017.90064

[6] A.M. Geoffrion and R. Nauss, Parametric and postoptimality analysis in integer linear programming. Manage. Sci. 23 (1977) 453-466. | Zbl 0358.90041

[7] 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. | Zbl 0914.90204

[8] 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

[9] L. Jenkins, Parametric methods in integer linear programming. Ann. Oper. Res. 27 (1990) 77-96. | Zbl 0718.90088

[10] L. Jenkins, Parametric mixed integer programming: an application to solid waste management. Manage. Sci. 28 (1982) 1270-1284. | Zbl 0504.90069

[11] L. Jenkins, Using parametric integer programming to plan the mix of an air transport fleet. INFOR 25 (1987) 117-135. | Zbl 0614.90081

[12] L. Jenkins, Parametric-objective integer programming using knapsack facets and Gomory cutting planes. Eur. J. Oper. Res. 31 (1987) 102-109. | Zbl 0624.90072

[13] S. Martello and P. Toth, The bottleneck generalized assignment problem. Eur. J. Oper. Res. 83 (1995) 621-638. | Zbl 0899.90130

[14] Optimization Subroutine Library, release 2, Guide and Reference, IBM (1992).

[15] IBM Optimization Library C, Application Programming Interface. Available at http://www-306.ibm.com/software/data/bi/osl/pubs/library/featCAPI.htm

[16] M. Oral and O. Kettani, A linearization procedure for quadratic and cubic mixed integer problems. Oper. Res. 40 (1992) S109-S116. | Zbl 0771.90072

[17] 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.