IJMEMES logo

International Journal of Mathematical, Engineering and Management Sciences

ISSN: 2455-7749


An Improved CPU Time in Triangle Splitting Method for Solving a Biobjective Mixed Integer Program

An Improved CPU Time in Triangle Splitting Method for Solving a Biobjective Mixed Integer Program

Ali Al-Hasani
School of Mathematical and Geospatial Sciences, RMIT University, Melbourne, Australia. Department of Mathematics, College of Sciences, University of Basrah, Al- Basrah, Iraq.

Masar Al-Rabeeah
School of Mathematical and Geospatial Sciences, RMIT University, Melbourne, Australia. Department of Mathematics, College of Sciences, University of Basrah, Al- Basrah, Iraq.

Santosh Kumar
School of Mathematical and Geospatial Sciences, RMIT University, Melbourne, Australia. Department of Mathematics and Statistics, University of Melbourne, Melbourne, Australia.

Andrew Eberhard
School of Mathematical and Geospatial Sciences, RMIT University, Melbourne, Australia.

DOI https://dx.doi.org/10.33889/IJMEMS.2018.3.4-025

Received on February 08, 2018
  ;
Accepted on April 02, 2018

Abstract

In this paper, an existing algorithm known as Triangle Splitting Method (TSM) for the Bi-Objective Mixed Integer Program (BOMIP) has been modified, which has been named “An Improved Triangle Splitting Method (ITSM)”. The TSM solves many unnecessary single objectives Mixed Integer Programs (MIP) to split each triangle with two rectangles, and second, it doesn’t find the all efficient frontiers. The proposed ITSM has resulted in redaction of CPU time by solving one MIP at each triangle and finds more number of nondominated frontiers compared to the TSM. The proposed modification has been tested in many instances.

Keywords- Biobjective mixed integer programming, Nondominated frontiers, Exact algorithm for multi-objective optimization.

Citation

Al-Hasani, A., Al-Rabeeah, M., Kumar, S., & Eberhard, A. (2018). An Improved CPU Time in Triangle Splitting Method for Solving a Biobjective Mixed Integer Program. International Journal of Mathematical, Engineering and Management Sciences, 3(4), 351-364. https://dx.doi.org/10.33889/IJMEMS.2018.3.4-025.

Conflict of Interest

Acknowledgements

References

Aneja, Y. P., & Nair, K. P. (1979). Bicriteria transportation problem. Management Science, 25(1), 73-78.

Boland, N., Charkhgard, H., & Savelsbergh, M. (2015). A criterion space search algorithm for biobjective mixed integer programming: The triangle splitting method. INFORMS Journal on Computing, 27(4), 597-618.

Bose, G. K., & Pain, P. (2018). Metaheuristic approach of multi-objective optimization during EDM process. International Journal of Mathematical, Engineering and Management Sciences, 3(3), 301-314.

Cplex, I. I. (2010). 12.2 User’s Manual. Book 12.2 User’s Manual, Series 12.2 User’s Manual.

Davis, R. E., Kendrick, D. A., & Weitzman, M. (1971). A branch-and-bound algorithm for zero-one mixed integer programming problems. Operations Research, 19(4), 1036-1044.

Ehrgott, M., & Ruzika, S. (2008). Improved ε-constraint method for multiobjective programming. Journal of Optimization Theory and Applications, 138(3), 375-396.

Fischetti, M., & Lodi, A. (2003). Local branching. Mathematical Programming, 98(1-3), 23-47.

Greco, S., Figueira, J., & Ehrgott, M. (2005). Multiple criteria decision analysis. Springer’s International series, (ISOR, volume 233).

Mavrotas, G., & Diakoulaki, D. (1998). A branch and bound algorithm for mixed zero-one multiple objective linear programming. European Journal of Operational Research, 107(3), 530-541.

Mavrotas, G., & Diakoulaki, D. (2005). Multi-criteria branch and bound: A vector maximization algorithm for mixed 0-1 multiple objective linear programming. Applied Mathematics and Computation, 171(1), 53-71.

Pramy, F. A. (2018). An approach for solving fuzzy multi-objective linear fractional programming problems. International Journal of Mathematical, Engineering and Management Sciences, 3(3), 280-293.

Soylu, B., & Yıldız, G. B. (2016). An exact algorithm for biobjective mixed integer linear programming problems. Computers & Operations Research, 72, 204-213.

Steuer, R. E. (1986). Multiple criteria optimization: theory, computation, and applications. Wiley, pp 546.

Vincent, T., Seipp, F., Ruzika, S., Przybylski, A., & Gandibleux, X. (2013). Multiple objective branch and bound for mixed 0-1 linear programming: Corrections and improvements for the biobjective case. Computers & Operations Research, 40(1), 498-509.