A Two-Stage Approach and Algorithm for Single, Bi and Multi-Objective Integer Linear Programming Problems

Dr. Anil Kashyap; Rajoo; Dr. Subhashish Biswas

doi:https://doi.org/10.14445/22315373/IJMTT-V66I5P510

International Journal of Mathematics Trends and Technology

Research Article | Open Access | Download PDF

Volume 66 | Issue 5 | Year 2020 | Article Id. IJMTT-V66I5P510 | DOI : https://doi.org/10.14445/22315373/IJMTT-V66I5P510

A Two-Stage Approach and Algorithm for Single, Bi and Multi-Objective Integer Linear Programming Problems

Dr. Anil Kashyap, Rajoo, Dr. Subhashish Biswas

Abstract

The objective of this paper is to present a new exact approach for solving Single, Bi, and Multi-Objective Integer Linear Programming. The new approach employing two of the existing exact algorithms in the literature, including the approximation algorithms, interactive algorithms, balanced box and e-constraint methods, in two stages. A computationally study shows that the new approach has four desirable characteristics. (1) It solves less single-objective integer linear programming. (2) It solves less bi-objective integer linear programming. (3) Its solution time is significantly smaller. (4) It is competitive with two-stage algorithms proposed by Sylva, J. & Crema, A; in 2004.

Keywords

Two-stage approach, Balanced Box Method, E-Constraint Method, Single, Bi and Multi-Objective Integer Linear Programming, Approximation algorithms and interactive algorithms.

References

[1] M. J. Alves & J. Climaco, “A review of interactive methods for multi-objective integer and mixed-integer programming”, European Journal of Operation Research, vol. 180, pp. 99-115, 2000.
[2] H. Benson, “An Outer Approximation Algorithm for Generating All Efficient Extreme Points in the Outcome Set of a Multiple Objective Linear Programming Problem”, Journal of Global Optimization, vol. 13(1), pp. 1-24, 1998.
[3] N. Boland, H. Charkhgard, & M. Savelsbergh, “A criterion space search algorithm for bi-objective integer programming: The balanced box method”, INFORMS Journal on Computing, vol. 27 (4), pp. 735–754, 2015.
[4] K. Bretthauer & B. Shetty, “The nonlinear knapsack problem-algorithms and Applications”, European Journal of Operation Research, vol. 138, pp. 459-472, 2002.
[5] V. Chankong & Y. Y. Haimes, “Multi objective Decision Making: Theory and Methodology”, Elsevier Science, New York, 1983.
[6] S. Chanas, D. & Kuchta, “Multi-objective programming in optimization of interval objective functions - a generalized approach”, European Journal of Operational Research, vol. 94, pp. 594-598, 1996.
[7] L. G. Chalmet, L. Lemonidis, & D. J. Elzinga, “An algorithm for bi-criterion integer programming problem”, European Journal of Operational Research, vol. 25, pp. 292–300, 1986.
[8] K. Dachert, J. Gorski & K. Klamroth, “An augmented weighted Tchebycheff method with adaptively chosen parameters for discrete bicriteria optimization problems”, Computers & Operations Research, vol. 39, pp. 2929–2943, 2012.
[9] K. Dachert & K. Klamroth, “A linear bound on the number of scalarization needed to solve discrete tricriteria optimization problems”, J. global optimization, pp. 1-34, 2015.
[10] M. Ehrgott & X. Gandibleux, “A survey and annotated bibliography of multi-objective combinatorial optimization”, OR Spektrum, vol. 22 (4), pp. 425-460, 2000.
[11] G. Kirlik & S. Sayin, “A new algorithm for generating all nondominated solutions of Multi-objective discrete optimization problems”, European Journal of Operational Research, vol. 232 (3), pp. 479-488, 2014.
[12] D. Klein & E. Hannan, “An algorithm for the multiple objective integer linear programming Problem”, European Journal of Operation Research, vol. 9, pp. 378-385, 1982.
[13] B. Lokman & M. Koksalan, “Finding all non-dominated point of multi objective integer programs”, Journal of Global Optimization, vol. 57, pp. 347-365, 2013.
[14] B. Lokman, M. Koksalan, P. J. Korhonen, & J. Wallenius, “An Interactive Algorithm to Find the Most Preferred Solution of Multi-objective Integer Programs”, Annals of Operations Research, vol. 245 (1-2), pp. 67-95, 2016.
[15] AH. Hamel A. Lohne, & B. Rudloff, “Benson type algorithms for linear vector optimization and applications”, Journal of Global Optimization, pp.811–836, 2014.
[16] S.C. Narula & V. Vassilev, “An interactive algorithm for solving multiple objective integer linear programming problems”, European Journal of Operational Research, vol. 79, pp. 443-450, 1994.
[17] M. Ozlen & M. Azizoglu, “Multi-objective integer programming: a general approach for generating all non-dominated solutions”, European Journal of Operational Research, vol. 199, pp. 25-35, 2009.
[18] L. Shao & M. Ehrgott, “An objective space cut and bound algorithm for convex multiplicative programmes” Journal of Global Optimization, pp.711–728, 2014.
[19] J. Sylva & A. Crema, “A method for finding the set of non-dominated vectors for multiple objective integer linear programs”, European Journal of Operation Research vol. 158, pp. 46-55, 2004.
[20] G. Mavrotas & D. Diakoulaki, “A branch and bound algorithm for mixed zero–one multiple objective linear programming.” European Journal of Operational Research vol. no. 107, pp. 530–541, 1998.

Citation :

Dr. Anil Kashyap, Rajoo, Dr. Subhashish Biswas, "A Two-Stage Approach and Algorithm for Single, Bi and Multi-Objective Integer Linear Programming Problems," International Journal of Mathematics Trends and Technology (IJMTT), vol. 66, no. 5, pp. 75-81, 2020. Crossref, https://doi.org/10.14445/22315373/IJMTT-V66I5P510