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

José Luis Quintero; Alejandro Crema

RAIRO - Operations Research - Recherche Opérationnelle (2005)

  • Volume: 39, Issue: 4, page 243-252
  • ISSN: 0399-0559

Abstract

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

How to cite

top

Quintero, José Luis, and Crema, Alejandro. "An algorithm for multiparametric min max 0-1-integer programming problems relative to the objective function." RAIRO - Operations Research - Recherche Opérationnelle 39.4 (2005): 243-252. <http://eudml.org/doc/245021>.

@article{Quintero2005,
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.},
author = {Quintero, José Luis, Crema, Alejandro},
journal = {RAIRO - Operations Research - Recherche Opérationnelle},
keywords = {0-1-integer programming; multiparametric programming; bottleneck problem},
language = {eng},
number = {4},
pages = {243-252},
publisher = {EDP-Sciences},
title = {An algorithm for multiparametric min max 0-1-integer programming problems relative to the objective function},
url = {http://eudml.org/doc/245021},
volume = {39},
year = {2005},
}

TY - JOUR
AU - Quintero, José Luis
AU - Crema, Alejandro
TI - An algorithm for multiparametric min max 0-1-integer programming problems relative to the objective function
JO - RAIRO - Operations Research - Recherche Opérationnelle
PY - 2005
PB - EDP-Sciences
VL - 39
IS - 4
SP - 243
EP - 252
AB - 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.
LA - eng
KW - 0-1-integer programming; multiparametric programming; bottleneck problem
UR - http://eudml.org/doc/245021
ER -

References

top
  1. [1] H. Arsham, http://ubmail.ubalt.edu/~harsham/refop/Refop.htm 
  2. [2] A. Crema, A contraction algorithm for the multiparametric integer linear programming problem. Eur. J. Oper. Res. 101 (1997) 130–139. Zbl0916.90209
  3. [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. Zbl0972.90049
  4. [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. Zbl0960.90063
  5. [5] A. Crema, The multiparametric 0-1-Integer Linear Programming problem: A unified approach. Eur. J. Oper. Res. 139 (2002) 511–520. Zbl1017.90064
  6. [6] A.M. Geoffrion and R. Nauss, Parametric and postoptimality analysis in integer linear programming. Manage. Sci. 23 (1977) 453–466. Zbl0358.90041
  7. [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. Zbl0914.90204
  8. [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 Zbl0914.90204
  9. [9] L. Jenkins, Parametric methods in integer linear programming. Ann. Oper. Res. 27 (1990) 77–96. Zbl0718.90088
  10. [10] L. Jenkins, Parametric mixed integer programming: an application to solid waste management. Manage. Sci. 28 (1982) 1270–1284. Zbl0504.90069
  11. [11] L. Jenkins, Using parametric integer programming to plan the mix of an air transport fleet. INFOR 25 (1987) 117–135. Zbl0614.90081
  12. [12] L. Jenkins, Parametric-objective integer programming using knapsack facets and Gomory cutting planes. Eur. J. Oper. Res. 31 (1987) 102–109. Zbl0624.90072
  13. [13] S. Martello and P. Toth, The bottleneck generalized assignment problem. Eur. J. Oper. Res. 83 (1995) 621–638. Zbl0899.90130
  14. [14] Optimization Subroutine Library, release 2, Guide and Reference, IBM (1992). 
  15. [15] IBM Optimization Library C, Application Programming Interface. Available at http://www-306.ibm.com/software/data/bi/osl/pubs/library/featCAPI.htm 
  16. [16] M. Oral and O. Kettani, A linearization procedure for quadratic and cubic mixed integer problems. Oper. Res. 40 (1992) S109–S116. Zbl0771.90072
  17. [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. 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.