Abstract
We propose a multi-criteria Composite Index Method (CIM) to compare the performance of alternative approaches to solving an optimization problem. The CIM is convenient in those situations when neither approach dominates the other when tested on different sizes of problem instances. The CIM takes problem instance size and multiple performance criteria into consideration within a weighting scheme to produce a single number that measures the relative improvement of one alternative over the other. Different weights are given to each dimension based on their relative importance as determined by the end user. We summarize the successful application of the CIM to an \({\mathcal {N}\mathcal {P}}\)-hard combinatorial optimization problem known as the backhaul profit maximization problem (BPMP). Using the CIM we tested a series of eleven techniques for improving solution time using CPLEX to solve two different BPMP models proposed in the literature.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
AMPL: AMPL Version 10.6.16. AMPL Optimization LLC (2009)
Bai, Y., Olinick, E.V.: An empirical study of mixed integer programming formulations of the backhaul profit maximization problem (2019). https://scholar.smu.edu/engineering_management_research/1/. Accessed 20 Feb 2020
Barr, R.S., Hickman, B.L.: Reporting computational experiments with parallel algorithms: issues, measures, and experts’ opinions. ORSA J. Comput. 5(1), 2–18 (1993)
Barr, R.S., Hickman, B.L.: Parallel simplex for large pure network problems: computational testing and sources of speedup. Oper. Res. 42(1), 65–80 (1994)
Beiranvand, V., Hare, W., Lucet, Y.: Best practices for comparing optimization algorithms. Optim. Eng. 18(4), 815–848 (2017). https://doi.org/10.1007/s11081-017-9366-1
Box, M.: A comparison of several current optimization methods, and the use of transformations in constrained problems. Comput. J. 9(1), 67–77 (1966)
Carle, M.A.: Deterministic behavior of CPLEX: ticks or seconds? (2019). https://tinyurl.com/kvy6jbbc. Accessed 14 Feb 2022
Crowder, H., Dembo, R.S., Mulvey, J.M.: On reporting computational experiments with mathematical software. ACM Trans. Math. Softw. (TOMS) 5(2), 193–203 (1979)
Dolan, E.D., Moré, J.J.: Benchmarking optimization software with performance profiles. Math. Program. 91(2), 201–213 (2002)
Dong, A., Bai, Y., Olinick, E.V., Yu, A.J.: The backhaul profit maximization problem: optimization models and solution procedures. INFORMS J. Optim. (2022). https://pubsonline.informs.org/doi/10.1287/ijoo.2022.0071
Dong, Y.: The Stochastic Inventory Routing Problem. Ph.D. thesis, Southern Methodist University (2015). https://search.proquest.com/docview/1757808242
Dong, Y., Olinick, E.V., Jason Kratz, T., Matula, D.W.: A compact linear programming formulation of the maximum concurrent flow problem. Networks 65(1), 68–87 (2015). https://doi.org/10.1002/net.21583, http://dx.doi.org/10.1002/net.21583
Hoffman, A., Mannos, M., Sokolowsky, D., Wiegmann, N.: Computational experience in solving linear programs. J. Soc. Ind. Appl. Math. 1(1), 17–33 (1953)
IBM. https://vdocuments.mx/ibm-ilog-cplex-user-manual-126.html. Accessed 14 Feb 2022
Matula: A new formulation of the maximum concurrent flow problem a proof of the maximum-concurrent-flow/max-elongation duality theorem (1986). https://s2.smu.edu/~matula/MCFP86.pdf
Yu, J., Dong, Y.: Maximizing profit for vehicle routing under time and weight constraints. Int. J. Prod. Econ. 145(2), 573–583 (2013)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2022 Springer Nature Switzerland AG
About this paper
Cite this paper
Bai, Y., Olinick, E. (2022). A Composite Index Method for Optimization Benchmarking. In: Simos, D.E., Rasskazova, V.A., Archetti, F., Kotsireas, I.S., Pardalos, P.M. (eds) Learning and Intelligent Optimization. LION 2022. Lecture Notes in Computer Science, vol 13621. Springer, Cham. https://doi.org/10.1007/978-3-031-24866-5_4
Download citation
DOI: https://doi.org/10.1007/978-3-031-24866-5_4
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-031-24865-8
Online ISBN: 978-3-031-24866-5
eBook Packages: Computer ScienceComputer Science (R0)