Abstract
This paper presents a new complexity result for solving multiobjective integer programming problems. We prove that encoding the entire set of nondominated solutions of the problem in a short sum of rational functions is polynomially doable, when the dimension of the decision space is fixed. This result extends a previous result presented in De Loera et al. (INFORMS J. Comput. 21(1):39–48, 2009) in that there the number of the objective functions is assumed to be fixed whereas ours allows this number to vary.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Barvinok A.: A polynomial time algorithm for counting integral points in polyhedra when the dimension is fixed. Math. Oper. Res. 19, 769–779 (1994)
Barvinok A., Woods K.: Short rational generating functions for lattice point problems. J. Am. Math. Soc. 16, 957–979 (2003)
Blanco V., Puerto J.: Partial Gröbner bases for multiobjective combinatorial optimization. SIAM J. Discret. Math. 23(2), 571–595 (2009)
Blanco, V., Puerto, J.: Some algebraic methods for solving multiobjective polynomial integer programs. J. Symb. Comput. (2010). doi:10.1016/j.jsc.2010.10.003
Brion M.: Points entiers dans les polyèdres convexes. Annales scientifiques de l’Ècole Normale Supèrieure Sér. 4 21(4), 653–663 (1988)
Chinchuluun A., Pardalos P.M.: A survey of recent developments in multiobjective optimization. Ann. Oper. Res. 154(1), 29–50 (2007)
Chinchuluun, A., Pardalos, P., Migdalas, A., Pitsoulis, L. (eds): Pareto optimality, game theory and equilibria. Springer, Berlin (2008)
De Loera J.A., Haws D., Hemmecke R., Huggins P., Sturmfels B., Yoshida R.: Short rational functions for toric algebra and applications. J. Symb. Comput. 38(2), 959–973 (2004)
De Loera J.A., Haws D., Hemmecke R., Huggins P., Yoshida R.: A computational study of integer programming algorithms based on Barvinok’s rational functions. Discret. Optim. 2(2), 135–144 (2005)
De Loera J.A., Hemmecke R., Köppe M.: Pareto optima of multicriteria integer linear programs. INFORMS J. Comput. 21(1), 39–48 (2009)
Ehrgott, M., Gandibleux, X. (eds): Multiple Criteria optimization. state of the art annotated bibliographic surveys. Kluwer, Boston (2002)
Fernández E., Puerto J.: The multiobjective solution of the uncapacitated plant location problem. Eur. J. Oper. Res. 45(3), 509–529 (2003)
Fonseca M.C., García-Sánchez A., Ortega-Mier M., Saldanha-da-Gama F.: A stochastic bi-objective location model for strategic reverse logistics. TOP 18(1), 158–184 (2010)
Lasserre J.B.: Generating functions and duality for integer programs. Discret. Optim. 2(1), 167–187 (2005)
Setämaa-Kärkkäinen A., Miettinen K., Vuori J.: Heuristic for a new multiobjective scheduling problem. Optim. Lett. 1(3), 213–225 (2007)
Rodríguez, R., Luque, M., González, M.: Portfolio selection in the Spanish stock market by interactive multiobjective programming. TOP (2010). Available online doi:10.1007/s11750-010-0139-7
Scholz D.: The multicriteria big cube small cube method. TOP 18(1), 286–302 (2010)
El-Sherbeny, N.: Resolution of a Vehicle Routing Problem with Multiobjective Simulated Annealing Method, PhD thesis, Faculte Polytechnique de Mons, Belgium (2001)
Steuer R.E.: Multiple criteria optimization: theory, computation and application. Wiley, New York (1985)
Ulungu E., Teghem J.: The two-phases method: an efficient procedure to solve biobjective combinatorial optimization problems. Found. Comput. Decis. Sci. 20(2), 149–165 (1995)
Woods K., Yoshida R.: Short rational generating functions and their applications to integer programming. SIAG/OPT Views News 16, 15–19 (2005)
Zionts S.: A survey of multiple criteria integer programming methods. Ann. Discret. Math. 5, 389–398 (1979)
Zopounidis, C., Pardalos, P. (eds.): Handbook of Multicriteria Analysis Series: Applied Optimization, vol. 103, p. 455 (2010). ISBN 978-3-540-92827-0 (print), 978-3-540-92828-7
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Blanco, V., Puerto, J. A new complexity result on multiobjective linear integer programming using short rational generating functions. Optim Lett 6, 537–543 (2012). https://doi.org/10.1007/s11590-011-0279-1
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s11590-011-0279-1