A Novel Alternative Algorithm for Solving Linear Integer Programming Problems with Four Variables

Abstract

In this paper, new iterative method is proposed based on parametrization for solving Integer Linear Programming (ILP) problems with four variables and an algorithm is provided. Our method, which is better than the cutting plane method and branch and bound methods in solving ILP problems with four variables, can be easily applied regardless of the number of constraints. In addition, in our method, all alternative solutions are found and presented to the decision maker. A numerical example is solved by applying the proposed method.

Keywords

• Integer linear programming
• Linear Diophantine equations
• Integer programming problems
• Optimal solution.

Dört Değişkenli Doğrusal Tamsayılı Programlama Problemlerinin Çözümü İçin Yeni Bir Alternatif Algoritma

Öz

Bu çalışmada, dört değişkenli Tamsayılı Doğrusal Programlama problemlerinin çözümü için parametrizasyona dayanan yeni iterativ bir yöntem önerilmiş ve bir algoritma sunulmuştur. Dört değişkenli DTP problemlerinin çözümünde kesme düzlemi yöntemi ve dal-sınır yöntemlerinden daha iyi olan yöntemimiz, kısıtlama sayısından bağımsız olarak kolaylıkla uygulanabilmektedir. Ayrıca yöntemimizde tüm alternatif çözümler bulunur ve karar vericiye sunulur. Önerilen yöntem uygulanarak sayısal bir örnek çözülmüştür.

Anahtar Kelimeler

• Tamsayılı doğrusal programlama
• Doğrusal Diophantine denklemleri
• Tamsayılı programlama problemleri
• Optimal çözüm.

Kaynakça

1. Bertsimas, D., Perakis, G., Tayur, S. (2000). A new algebraic geometry algorithm for integer programming. Management Science, 46(7), 999-1008.
2. Chen, D. S., Batson, R. G., Dang, Y. (2015). Applied integer programming: modeling and solution, pp. 3-4. John Wiley & Sons, New Jersey, 2011.
3. Dang, C., Y. Ye. (2015). A fixedpoint iterative approach to integer programming and its distributed computation. – Fixed Point Theory and Applications. 182, 1-15.
4. Genova, K., Guliashki, V. (2011). Linear integer programming methods and approaches–a survey. – Journal of Cybernetics and Information Technologies, 11(1), 1-23.
5. Gomory, Ralph E. (1958) Outline of an Algorithm for Integer Solutions to Linear Programs. Bull. Amer. Math. Soc. 64(5): 275-278.
6. Hossain, M. I., Hasan, M. B. (2013). A Decomposition Technique For Solving Integer Programming Problems. GANIT: Journal of Bangladesh Mathematical Society, 33, 1-11.
7. Joseph, A. (1995). Parametric formulation of the general integer linear programming problem. – Computers & operations research, 22(3), 883-892.
8. Mohamad, N. H., & Said, F. (2013). Integer linear programming approach to scheduling toll booth collectors problem. Indian Journal of Science and Technology, 6(5), 4416-4421.

9. Pandian, P., & Jayalakshmi, M. (2012). A New Approach for solving a Class of Pure Integer Linear Programming Problems. Journal of Advanced Engineering Technology, 3, 248-251.
10. Pedroso, J. P. (2002). An evolutionary solver for pure integer linear programming. International Transactions in Operational Research, 9(3), 337-352.
11. Schrijver, A. (1986). “Theory of Linear and Integer Programming”, John Wiley & Sons Ltd.
12. Shinto, K. G., & Sushama, C.M. (2013). An Algorithm for Solving Integer Linear Programming Problems. International Journal of Research in Engineering and Technology, 37-47.
13. Simsek Alan, K., Albayrak, I., M., Sivri, M., Guler, C. (2019). An Alternative Algorithm for Solving Linear Programming Problems Having Two Variables, – International Journal of Applied Information Systems. 12 (25), 6-9.
14. Simsek Alan, K. (2020). An Novel Algorithm for Solving Linear Programming Problems Having Three Variables. J. Cyber. and Inform. Technologies 20 (4), 27-35.
15. Tantawy, S. F. (2014). A new procedure for solving integer linear programming problems. – Arabian Journal for Science and Engineering. 39 (6), 5265-5269.
16. Tsai, J. F., Lin, M. H., Hu, Y. C. (2008). Finding multiple solutions to general integer linear programs. – European Journal of Operational Research, 184(2), 802-809.