An algorithm for multiparametric 0-1-Integer Programming problems relative to a generalized min max objective function

José Luis Quintero; Alejandro Crema

RAIRO - Operations Research (2009)

  • Volume: 43, Issue: 1, page 1-12
  • ISSN: 0399-0559

Abstract

top
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.

How to cite

top

Quintero, José Luis, and Crema, Alejandro. "An algorithm for multiparametric 0-1-Integer Programming problems relative to a generalized min max objective function." RAIRO - Operations Research 43.1 (2009): 1-12. <http://eudml.org/doc/250630>.

@article{Quintero2009,
abstract = { 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. },
author = {Quintero, José Luis, Crema, Alejandro},
journal = {RAIRO - Operations Research},
keywords = {0-1-Integer Programming; multiparametric programming; Bottleneck problem.; 0-1-integer programming; bottleneck problem},
language = {eng},
month = {1},
number = {1},
pages = {1-12},
publisher = {EDP Sciences},
title = {An algorithm for multiparametric 0-1-Integer Programming problems relative to a generalized min max objective function},
url = {http://eudml.org/doc/250630},
volume = {43},
year = {2009},
}

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
DA - 2009/1//
PB - EDP Sciences
VL - 43
IS - 1
SP - 1
EP - 12
AB - 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.
LA - eng
KW - 0-1-Integer Programming; multiparametric programming; Bottleneck problem.; 0-1-integer programming; bottleneck problem
UR - http://eudml.org/doc/250630
ER -

References

top
  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
  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
  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
  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.  
  6. A. Crema, A contraction algorithm for the multiparametric integer linear programming problem. Eur. J. Oper. Res.101 (1997) 130–139.  Zbl0916.90209
  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
  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
  9. A. Crema, The multiparametric 0-1-Integer Linear Programming problem: A unified approach. Eur. J. Oper. Res.139 (2002) 511–520.  Zbl1017.90064
  10. A.M. Geoffrion and R. Nauss, Parametric and postoptimality analysis in integer linear programming. Manag. Sci.23 (1977) 453–466.  Zbl0358.90041
  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.  
  12. H.J. Greenberg, An annoted bibliography for post-solution analysis in mixed integer programming and combinatorial optimization, hgreenbe/papers/mipbib.pdf.  Zbl0914.90204URIhttp://www-math.cudenver.edu/
  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
  15. L. Jenkins, Using parametric integer programming to plan the mix of an air transport fleet. INFOR25 (1987) 117–135.  Zbl0614.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
  17. L. Jenkins, Parametric methods in integer linear programming. Ann. Oper. Res.27 (1990) 77–96.  Zbl0718.90088
  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
  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
  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
  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.  Zbl1169.90463
  24. R.E. Steuer and E.U. Choo, An interactive weighted Tchebycheff procedure for multiple objective programming. Math. Program.26 (1983) 326–344.  Zbl0506.90075
  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
  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
  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
  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.  Zbl1092.90031

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.