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

  IJMTT-book-cover
 
International Journal of Mathematics Trends and Technology (IJMTT)
 
© 2020 by IJMTT Journal
Volume-66 Issue-5
Year of Publication : 2020
Authors : Dr. Anil Kashyap, Rajoo, Dr. Subhashish Biswas
  10.14445/22315373/IJMTT-V66I5P510

MLA

MLA Style: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 66.4 (2020):75-81. 

APA Style: Dr. Anil Kashyap, Rajoo, Dr. Subhashish Biswas.(2020).A Two-Stage Approach and Algorithm for Single, Bi and Multi-Objective Integer Linear Programming Problems International Journal of Mathematics Trends and Technology, 75-81.

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.

Reference
[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.

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