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.
Mots-clés : 0-1-integer programming, multiparametric programming, bottleneck problem
@article{RO_2009__43_1_1_0, author = {Quintero, Jos\'e Luis and Crema, Alejandro}, title = {An algorithm for multiparametric 0-1-integer programming problems relative to a generalized min max objective function}, journal = {RAIRO - Operations Research - Recherche Op\'erationnelle}, pages = {1--12}, publisher = {EDP-Sciences}, volume = {43}, number = {1}, year = {2009}, doi = {10.1051/ro/2009002}, mrnumber = {2502321}, zbl = {1158.90388}, language = {en}, url = {http://www.numdam.org/articles/10.1051/ro/2009002/} }
TY - JOUR AU - Quintero, José Luis AU - Crema, Alejandro TI - An algorithm for multiparametric 0-1-integer programming problems relative to a generalized min max objective function JO - RAIRO - Operations Research - Recherche Opérationnelle PY - 2009 SP - 1 EP - 12 VL - 43 IS - 1 PB - EDP-Sciences UR - http://www.numdam.org/articles/10.1051/ro/2009002/ DO - 10.1051/ro/2009002 LA - en ID - RO_2009__43_1_1_0 ER -
%0 Journal Article %A Quintero, José Luis %A Crema, Alejandro %T An algorithm for multiparametric 0-1-integer programming problems relative to a generalized min max objective function %J RAIRO - Operations Research - Recherche Opérationnelle %D 2009 %P 1-12 %V 43 %N 1 %I EDP-Sciences %U http://www.numdam.org/articles/10.1051/ro/2009002/ %R 10.1051/ro/2009002 %G en %F RO_2009__43_1_1_0
Quintero, José Luis; Crema, Alejandro. An algorithm for multiparametric 0-1-integer programming problems relative to a generalized min max objective function. RAIRO - Operations Research - Recherche Opérationnelle, Tome 43 (2009) no. 1, pp. 1-12. doi : 10.1051/ro/2009002. http://www.numdam.org/articles/10.1051/ro/2009002/
[1] A simple recipe for concise mixed 0-1 linearizations. Oper. Res. Lett. 33 (2005) 55-61. | Zbl
and ,[2] Comparisons and enhancement strategies for linearizing mixed 0-1-quadratic programs. Discrete Optim. 1 (2004) 99-120. | MR | Zbl
, and ,[3] A review of interactive methods for multiobjective integer and mixed-integer programming. Eur. J. Operat. Res. 180 (2007) 99-115. | MR | Zbl
and ,[4]
, http://home.ubalt.edu/ntsbarsh/Business-stat/Refop.htm.[5] 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. | Zbl
,[6] A contraction algorithm for the multiparametric integer linear programming problem. Eur. J. Oper. Res. 101 (1997) 130-139. | Zbl
,[7] An algorithm for the multiparametric 0-1-integer linear programming problem relative to the objective function. Eur. J. Oper. Res. 125 (2000) 18-24. | MR | Zbl
,[8] An algorithm for the multiparametric 0-1-integer linear programming problem relative to the constraint matrix. Oper. Res. Lett. 27 (2000) 1-46. | MR | Zbl
,[9] The multiparametric 0-1-Integer Linear Programming problem: A unified approach. Eur. J. Oper. Res. 139 (2002) 511-520. | MR | Zbl
,[10] Parametric and postoptimality analysis in integer linear programming. Manag. Sci. 23 (1977) 453-466. | Zbl
and ,[11] 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. | MR | Zbl
,[12] An annoted bibliography for post-solution analysis in mixed integer programming and combinatorial optimization, http://www-math.cudenver.edu/~hgreenbe/papers/mipbib.pdf. | Zbl
,[13] IBM Optimization Library C, Application Programming Interface. Available at http://www-306.ibm.com/software/data/bi/osl/pubs/library/featCAPI.htm.
[14] Parametric mixed integer programming: an application to solid waste management. Manag. Sci. 28 (1982) 1270-1284. | Zbl
,[15] Using parametric integer programming to plan the mix of an air transport fleet. INFOR 25 (1987) 117-135. | Zbl
,[16] Parametric-objective integer programming using knapsack facets and Gomory cutting planes. Eur. J. Oper. Res. 31 (1987) 102-109. | MR | Zbl
,[17] Parametric methods in integer linear programming. Ann. Oper. Res. 27 (1990) 77-96. | MR | Zbl
,[18] An efficient, adaptive parameter variation scheme for metaheuristics based on the epsilon constraint method. Eur. J. Oper. Res. 169 (2006) 932-942. | MR | Zbl
, and ,[19] A new methodology for the general multiparametric mixed integer linear programming (MILP) problems. Ind. Eng. Che. Res. 46 (2007) 5141-5151.
and ,[20] The bottleneck generalized assignment problem. Eur. J. Oper. Res. 83 (1995) 621-638. | Zbl
and ,[21] Optimization Soubroutine Library, release 2, Guide and Reference, IBM (1992).
[22] A linearization procedure for quadratic and cubic mixed integer problems. Oper. Res. 40 (1992) S109-S116. | MR | Zbl
and ,[23] An algorithm for multiparametric min max 0-1-integer programming problem relative to the objective function. RAIRO Oper. Res. 39 (2005) 243-252. | Numdam | MR | Zbl
and ,[24] An interactive weighted Tchebycheff procedure for multiple objective programming. Math. Program. 26 (1983) 326-344. | MR | Zbl
and ,[25] A method for finding the set of non-dominated vectors for multiple objective integer linear programs. Eur. J. Oper. Res. 158 (2004) 46-55. | MR | Zbl
and ,[26] 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. | MR | Zbl
and ,[27] Enumerating the set of non-dominated vectors in multiple objective integer linear programming. RAIRO Oper. Res. 42 (2008) 371-388. | Numdam | MR | Zbl
and ,[28] Theoretical and algorithmic study for parametric 0-1 linear programs relative to the objective function. Research Report LIPN 2003-01.
, and ,Cité par Sources :