A novel alternative algorithm to find all multiple solutions of general integer linear program

Abstract

Integer linear programming (ILP) is often used to model and solve real-life problems. In practice, alternative solutions are very useful as they significantly increase flexibility for the decision-maker. In this study, an alternative method based on parameterization obtained from the Diophantine equation is developed to find all alternative solutions to ILP problems, and an easy-to-implement, efficient, and reliable algorithm is presented. The proposed method was used without being affected by the number of variables and constraints in the problem. Numerical examples are presented to demonstrate the usefulness of the proposed method. In addition, these examples are coded in the MAPLE programming language according to the proposed algorithm.

Keywords

• Alternative Solutions
• Integer Linear Programming
• Multiple Solutions
• Linear Diophantine Equations
• Optimal Hyperplane
• Optimal Solution

References

1. REFERENCES
2. [1] Maayah B, Moussaoui A, Bushnaq S, Arqub OA. The multistep Laplace optimized decomposition method for solving fractional-order coronavirus disease model (COVID-19) via the Caputo fractional approach. Demonstr Math 2022;55:963977. [CrossRef]
3. [2] Momani S, Arqub OA, Maayah B. Piecewise optimal fractional reproducing kernel solution and convergence analysis for the Atangana–Baleanu–Caputo model of the Lienard’s equation. Fractals 2020;28:2040007. [CrossRef]
4. [3] Arqub OA, Rashaideh H. The RKHS method for numerical treatment for integrodifferential algebraic systems of temporal two-point BVPs. Neural Comput Appl 2018;30:25952606. [CrossRef]
5. [4] Arqub OA. Computational algorithm for solving singular Fredholm time-fractional partial integrodifferential equations with error estimates. J Appl Math Comput 2019;59:227243. [CrossRef]
6. [5] Arqub OA, Maayah B. Adaptive the Dirichlet model of mobile/immobile advection/dispersion in a time-fractional sense with the reproducing kernel computational approach: Formulations and approximations. Int J Mod Phys B 2022;18. [CrossRef]
7. [6] Djerdjour M. An enumerative algorithm framework for a class of nonlinear integer programming problems. Eur J Oper Res 1997;101:104121. [CrossRef]
8. [7] Salkin HM, Mathur K. Foundations of Integer Programming. Amsterdam: North-Holland;1989.

9. [8] Simons R. How OR improved smelter performance. MP in Action. The Newsletter of Mathematical Programming in Industry and Commerce. 1989.
10. [9] Taha HA. Operations Research. New York, US: Macmillan; 2003.
11. [10] Biegler LT, Grossmann IE. Retrospective on optimization. Comput Chem Eng 2004;28:11691192. [CrossRef]
12. [11] Mustafa D. A metaheuristic solution approach with two construction heuristics for vehicle routing problem with simultaneous linehauls and backhauls. Sigma J Eng Nat Sci 2021;39:226236.
13. [12] Gomory RE. Outline of an algorithm for integer solution to linear programs. Bull Am Math Soc 1958;64:275278. [CrossRef]
14. [13] Land AH, Doig AG. An automatic method for solving discrete programming problems. Econometrica 1960;28:497520. [CrossRef]
15. [14] Dakin RJ. A tree search algorithm for mixed integer programming problems. Comput J 1965;8:250255. [CrossRef]
16. [15] Grossmann IE, Biegler LT. Future perspective on optimization. Comput Chem Eng. 2004;28:11931218. [CrossRef]
17. [16] Joseph A. Parametric formulation of the general integer linear programming problem. Comput Oper Res 1995;22:883892. [CrossRef]
18. [17] Pandian P, Jayalakshmi MA. New approach for solving a class of pure integer linear programming problems. J Adv Eng Technol 2012;3:248251.
19. [18] Tsai JF, Lin MH, Hu YC. Finding multiple solutions to general integer linear programs. Eur J Oper Res 2008;184:802809. [CrossRef]
20. [19] Genova K, Guliashki V. Linear integer programming methods and approaches–a survey. J Cybern Inf Technol 2011;11:123.
21. [20] Shinto KG, Sushama CM. An algorithm for solving integer linear programming problems. Int J Res Eng Technol 2013;3747.
22. [21] Bertsimas D, Perakis G, Tayur S. A new algebraic geometry algorithm for integer programming. Manag Sci 2000;46:9991008. [CrossRef]
23. [22] Simsek Alan K, Albayrak I, Sivri M, Guler C. An alternative algorithm for solving linear programming problems having two variables. Int J Appl Inf Syst 2019;12:69.
24. [23] Simsek Alan K. A novel alternative algorithm for solving linear programming problems having three variables. J Cybern Inf Technol 2020;20:2735. [CrossRef]
25. [24] Simsek Alan K. A novel alternative algorithm for solving linear integer programming problems with four variables. Eur J Sci Technol 2021;29:8186. [CrossRef]
26. [25] Brimkov VE, Danchev SS. Real data—integer solution problems within the Blum–Shub–Smale computational model. J Complex 1997;13:279300. [CrossRef]
27. [26] Aardal K, Bixby RE, Cor AJ, Hurkens CAJ, Lenstra AK, Job W, et al. Market split and basis reduction: Towards a solution of the Cornuéjols-Dawande instances. Integer Program Combin Optim 7th Int IPCO Conf Graz Austria. 1999. [CrossRef]
28. [27] Esmaeili H, Amiri MN, Spedicato E. ABS solution of a class of linear integer inequalities and integer LP problems. Optim Methods Softw 2001;179192. [CrossRef]
29. [28] Aliev I, De Loera JA, Oertel T, O'Neill C. Sparse solutions of linear Diophantine equations. SIAM J Appl Algebra Geom. 2017;1:239253. [CrossRef]
30. [29] Yılmaz OF. An integer programming model for disassembly system configuration. Sigma J Eng Nat Sci. 2019;37:813825.
31. [30] Simsek Alan K. A novel alternative algorithm for solving linear integer programming problems. Eur J Sci Technol 2021;29:9398. [CrossRef]
32. [31] Alonso PF, Arellano-VJ J, Diego-Celis R. Two heuristics for the label printing problem. Int Trans Oper Res 2022;29:28412854. [CrossRef]
33. [32] Fernando HCD, Williams L, Mumey B, Tomescu AI. Efficient minimum flow decomposition via integer linear programming. J Comput Biol 2022;29:12521267. [CrossRef]
34. [33] Dehua X, Yuan S, Yu C, Limin X, Fengzhao Y, Yunzhou X. An integer linear programming model for the label printing problem. Int Trans Oper Res 2023;119.
35. [34] Auricchio G, Ferrarini L, Lanzarotto G. An integer linear programming model for tilings. J Math Music 2023;17:514530. [CrossRef]
36. [35] Chen DS, Batson RG, Dang Y. Applied Integer Programming: Modeling and Solution. John Wiley & Sons; 2011.
37. [36] Schrijver A. Theory of Linear and Integer Programming. Chichester, UK: John Wiley & Sons, Ltd; 1986.
38. [37] Andreescu T, Andrica D, Cucurezeanu I. An Introduction to Diophantine Equations. New York, US: Springer, Ltd; 2010. [CrossRef]
39. [38] Zionts S. Linear and Integer Programming. New Jersey, US: Prentice-Hall; 1974.
40. [39] LINGO. Chicago: Release 9.0. LINDO System Inc; 2004.