×

An algorithm for multiparametric 0-1-integer programming problems relative to a generalized min Max objective function. (English) Zbl 1158.90388

Summary: The multiparametric 0-1-Integer Programming (0-1-IP) problem relative to the objective function is a family of 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 a generalized min max objective function such that the min sum and min max are particular cases.

MSC:

90C10 Integer programming
90C31 Sensitivity, stability, parametric optimization

Software:

OSL
PDFBibTeX XMLCite
Full Text: DOI Numdam EuDML Link

References:

[1] W.P. Adams and R.J. Forrester, A simple recipe for concise mixed 0-1 linearizations. Oper. Res. Lett.33 (2005) 55-61. Zbl1076.90030 · Zbl 1076.90030 · doi:10.1016/j.orl.2004.05.001
[2] W.P. Adams, R.J. Forrester and F.W. Glover, Comparisons and enhancement strategies for linearizing mixed 0-1-quadratic programs. Discrete Optim.1 (2004) 99-120. Zbl1091.90040 · Zbl 1091.90040 · doi:10.1016/j.disopt.2004.03.006
[3] M.J. Alves and J. Climaco, A review of interactive methods for multiobjective integer and mixed-integer programming. Eur. J. Operat. Res.180 (2007) 99-115. Zbl1114.90074 · Zbl 1114.90074 · doi:10.1016/j.ejor.2006.02.033
[4] H. Arsham, . URIhttp://home.ubalt.edu/ntsbarsh/Business-stat/Refop.htm
[5] V.J. Bowman Jr, On the relationship of the Tchebycheff norm and the efficient frontier of multiple-criteria objectives. in Multiple Criteria Decision Making, edited by H. Thiriez, S. Zionts, Lect. Notes Economics Math. Systems, edited by H. Thiriez, S. Zionts, Springer-Verlag, Berlin (1976) 76-86. Zbl0364.90089 · Zbl 0364.90089
[6] A. Crema, A contraction algorithm for the multiparametric integer linear programming problem. Eur. J. Oper. Res.101 (1997) 130-139. Zbl0916.90209 · Zbl 0916.90209 · doi:10.1016/0377-2217(95)00369-X
[7] 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. Zbl0972.90049 · Zbl 0972.90049 · doi:10.1016/S0377-2217(99)00193-9
[8] 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. Zbl0960.90063 · Zbl 0960.90063 · doi:10.1016/S0167-6377(00)00034-1
[9] A. Crema, The multiparametric 0-1-Integer Linear Programming problem: A unified approach. Eur. J. Oper. Res.139 (2002) 511-520. Zbl1017.90064 · Zbl 1017.90064 · doi:10.1016/S0377-2217(01)00163-1
[10] A.M. Geoffrion and R. Nauss, Parametric and postoptimality analysis in integer linear programming. Manag. Sci.23 (1977) 453-466. Zbl0358.90041 · Zbl 0358.90041 · doi:10.1287/mnsc.23.5.453
[11] 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 David L. Woodruff, Kluwer Academic Publishers, Boston, MA (1998) 97-148. Zbl0914.90204 · Zbl 0914.90204
[12] H.J. Greenberg, An annoted bibliography for post-solution analysis in mixed integer programming and combinatorial optimization, hgreenbe/papers/mipbib.pdf. Zbl0914.90204 URIhttp://www-math.cudenver.edu/ · Zbl 0914.90204
[13] IBM Optimization Library C, Application Programming Interface. Available at http://www-306.ibm.com/software/data/bi/osl/pubs/library/featCAPI.htm.
[14] L. Jenkins, Parametric mixed integer programming: an application to solid waste management. Manag. Sci.28 (1982) 1270-1284. Zbl0504.90069 · Zbl 0504.90069 · doi:10.1287/mnsc.28.11.1270
[15] L. Jenkins, Using parametric integer programming to plan the mix of an air transport fleet. INFOR25 (1987) 117-135. Zbl0614.90081 · Zbl 0614.90081
[16] L. Jenkins, Parametric-objective integer programming using knapsack facets and Gomory cutting planes. Eur. J. Oper. Res.31 (1987) 102-109. Zbl0624.90072 · Zbl 0624.90072 · doi:10.1016/0377-2217(87)90143-3
[17] L. Jenkins, Parametric methods in integer linear programming. Ann. Oper. Res.27 (1990) 77-96. Zbl0718.90088 · Zbl 0718.90088 · doi:10.1007/BF02055191
[18] M. Laumanns, L. Thiele and E. Zitzler, An efficient, adaptive parameter variation scheme for metaheuristics based on the epsilon constraint method. Eur. J. Oper. Res.169 (2006) 932-942. Zbl1079.90122 · Zbl 1079.90122 · doi:10.1016/j.ejor.2004.08.029
[19] Z. Li and M.G. Ierapetritou, A new methodology for the general multiparametric mixed integer linear programming (MILP) problems. Ind. Eng. Che. Res.46 (2007) 5141-5151.
[20] S. Martello and P. Toth, The bottleneck generalized assignment problem. Eur. J. Oper. Res.83 (1995) 621-638. Zbl0899.90130 · Zbl 0899.90130 · doi:10.1016/0377-2217(93)E0271-X
[21] Optimization Soubroutine Library, release 2, Guide and Reference, IBM (1992).
[22] M. Oral and O. Kettani, A linearization procedure for quadratic and cubic mixed integer problems. Oper. Res.40 (1992) S109-S116. Zbl0771.90072 · Zbl 0771.90072 · doi:10.1287/opre.40.1.S109
[23] J.L. Quintero and A. Crema, An algorithm for multiparametric min max 0-1-integer programming problem relative to the objective function. RAIRO Oper. Res.39 (2005) 243-252. · Zbl 1169.90463 · doi:10.1051/ro:2006004
[24] R.E. Steuer and E.U. Choo, An interactive weighted Tchebycheff procedure for multiple objective programming. Math. Program.26 (1983) 326-344. · Zbl 0506.90075 · doi:10.1007/BF02591870
[25] J. Sylva and A. Crema, A method for finding the set of non-dominated vectors for multiple objective integer linear programs. Eur. J. Oper. Res.158 (2004) 46-55. Zbl1061.90103 · Zbl 1061.90103 · doi:10.1016/S0377-2217(03)00255-8
[26] J. Sylva and A. Crema, A method for finding well-dispersed subsets of non-dominated vectors for multiple objective mixed integer linear programs. Eur. J. Oper. Res.180 (2007) 1011-1027. Zbl1122.90055 · Zbl 1122.90055 · doi:10.1016/j.ejor.2006.02.049
[27] J. Sylva and A. Crema, Enumerating the set of non-dominated vectors in multiple objective integer linear programming. RAIRO Oper. Res.42 (2008) 371-388. Zbl1153.90511 · Zbl 1153.90511 · doi:10.1051/ro:2008018
[28] B. Thiongane, A. Nagih and G. Plateau, Theoretical and algorithmic study for parametric 0-1 linear programs relative to the objective function. Research Report LIPN 2003-01. · Zbl 1092.90031
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.