A General Framework for Providing Interval Representations of Pareto Optimal Outcomes for Large-Scale Bi- and Tri-Criteria MIP Problems
Volume 35, Issue 2 (2024), pp. 255–282
Pub. online: 12 April 2024
Type: Research Article
Open Access
Open Access
Received
1 December 2023
1 December 2023
Accepted
1 March 2024
1 March 2024
Published
12 April 2024
12 April 2024
Abstract
The Multi-Objective Mixed-Integer Programming (MOMIP) problem is one of the most challenging. To derive its Pareto optimal solutions one can use the well-known Chebyshev scalarization and Mixed-Integer Programming (MIP) solvers. However, for a large-scale instance of the MOMIP problem, its scalarization may not be solved to optimality, even by state-of-the-art optimization packages, within the time limit imposed on optimization. If a MIP solver cannot derive the optimal solution within the assumed time limit, it provides the optimality gap, which gauges the quality of the approximate solution. However, for the MOMIP case, no information is provided on the lower and upper bounds of the components of the Pareto optimal outcome. For the MOMIP problem with two and three objective functions, an algorithm is proposed to provide the so-called interval representation of the Pareto optimal outcome designated by the weighting vector when there is a time limit on solving the Chebyshev scalarization. Such interval representations can be used to navigate on the Pareto front. The results of several numerical experiments on selected large-scale instances of the multi-objective multidimensional 0–1 knapsack problem illustrate the proposed approach. The limitations and possible enhancements of the proposed method are also discussed.
References
Ahmadi, A., Aghaei, J., Shayanfar, H.A., Rabiee, A. (2012). Mixed integer programming of multiobjective hydro-thermal self scheduling. Applied Soft Computing, 12, 2137–2146. https://doi.org/10.1016/j.asoc.2012.03.020.
Delorme, X., Battaïa, O., Dolgui, A. (2014). Multi-objective approaches for design of assembly lines. In: Benyoucef, L., Hennet, C., J., Tiwari, M. (Eds.), Applications of Multi-Criteria and Game Theory Approaches: Manufacturing and Logistics. Springer, London, pp. 31–56. https://doi.org/10.1007/978-1-4471-5295-8_2.
Dyer, M.E. (1980). Calculating Surrogate Constraints. Mathematical Programming, 19, 255–278. https://doi.org/10.1007/BF01581647.
Ehrgott, M. (2005). Multicriteria Optimization. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-27659-9.
Eiselt, H.A., Marianov, V. (2014). A bi-objective model for the location of landfills for municipal solid waste. European Journal of Operational Research, 2351, 187–194. https://doi.org/10.1016/j.ejor.2013.10.005.
Forget, N., Gadegaard, S.L., Klamroth, K., Nielsen, L.R., Przybylski, A. (2022). Branch-and-bound and objective branching with three or more objectives. Computers & Operations Research, 148, 106012. https://doi.org/10.1016/j.cor.2022.106012.
Glover, F. (1965). A multiphase-dual algorithm for the zero-one integer programming problem. Operations Research, 13(6), 879–919. https://doi.org/10.1287/opre.13.6.879.
Glover, F. (1968). Surrogate constraints. Operations Research, 164, 741–749. https://doi.org/10.1287/opre.16.4.741.
Gurobi (2023). GUROBI. Last accessed March 31, 2023. https://www.gurobi.com/.
IBM (2023). CPLEX. Last accessed March 31, 2023. https://www.ibm.com/products/ilog-cplex-optimization-studio.
Kaliszewski, I. (2006). Soft Computing for Complex Multiple Criteria Decision Making. Springer, New York. https://doi.org/10.1007/0-387-30177-1.
Kaliszewski, I., Miroforidis, J. (2014). Two-sided Pareto front approximations. Journal of Optimization Theory and Its Applications, 162, 845–855. https://doi.org/10.1007/s10957-013-0498-y.
Kaliszewski, I., Miroforidis, J. (2019). Lower and upper bounds for the general multiobjective optimization problem. AIP Conference Proceedings, 2070, 020038. https://doi.org/10.1063/1.5090005.
Kaliszewski, I., Miroforidis, J. (2021). Cooperative multiobjective optimization with bounds on objective functions. Journal of Global Optimization, 79, 369–385. https://doi.org/10.1007/s10898-020-00946-4.
Kaliszewski, I., Miroforidis, J. (2022). Probing the Pareto front of a large-scale multiobjective problem with a MIP solver. Operational Research, 22, 5617–5673. https://doi.org/10.1007/s12351-022-00708-y.
Kaliszewski, I., Miroforidis, J., Podkopaev, D. (2016). Multiple Criteria Decision Making by Multiobjective Optimization – A Toolbox. Springer Cham. https://doi.org/10.1007/978-3-319-32756-3.
Miettinen, K.M. (1999). Nonlinear Multiobjective Optimization. Kluwer Academic Publishers. https://doi.org/10.1007/978-1-4615-5563-6.
Miroforidis, J. (2021). Bounds on efficient outcomes for large-scale cardinality-constrained Markowitz problems. Journal of Global Optimization, 80, 617–634. https://doi.org/10.1007/s10898-021-01022-1.
Narciso, M.G., Lorena, L.A.N. (1999). Lagrangean/surrogate relaxation for generalized assignment problems. European Journal of Operational Research, 114(1), 165–177. https://doi.org/10.1016/S0377-2217(98)00038-1.
Oke, O., Siddiqui, S. (2015). Efficient automated schematic map drawing using multiobjective mixed integer programming. Computers & Operations Research, 61, 1–17. https://doi.org/10.1016/j.cor.2015.02.010.
Przybylski, A., Gandibleux, X. (2017). Multi-objective branch and bound. European Journal of Operational Research, 260(3), 856–872. https://doi.org/10.1016/j.ejor.2017.01.032.
Samanlioglu, F. (2013). A multi-objective mathematical model for the industrial hazardous waste location-routing problem. European Journal of Operational Research, 226(2), 332–340. https://doi.org/10.1016/j.ejor.2012.11.019.
Sikorski, J. (1986). Quasi–Subgradient algorithms for calculating surrogate constraints. In: Malanowski, K., Mizukami, K. (Eds.), Analysis and Algorithms of Optimization Problems, Lecture Notes in Control and Information Sciences, Vol. 82. Springer Berlin Heidelberg, Berlin, Heidelberg, pp. 202–236. https://doi.org/10.1007/BFb0007163.
Biographies
Filcek Grzegorz
G. Filcek is an assistant professor at the Wrocław University of Science and Technology, Poland. He obtained his PhD in computer science from the same institution in 2011. His scientific interests include multi-objective optimization, multiple criteria decision-making, intelligent decision support systems, blockchain technologies, and system engineering.
Miroforidis Janusz
J. Miroforidis is an assistant professor at the Systems Research Institute, Polish Academy of Sciences, Poland. He obtained his PhD in computer science from the same institution in 2010. His scientific interests are multi-objective optimization, multiple criteria decision making, and computer-aided decision making.
