A Novel Alternative Algorithm for Solving Linear Integer Programming Problems

Öz

In this study, a novel alternative method and a novel alternative algorithm are presented for the solution of Linear Integer Programming Problems that have a linear objective function and constraints consisting of linear equations or inequalities. Our method is based on simple algebraic operations and mathematical programming. Although there are many methods used in solving Linear Integer Programming Problems, most of these methods have some difficulties in application and computation. Our method, which does not have these difficulties, is easy to implement and less sensitive to the number of variables fo the problem than other methods. Therefore, it can also be used in solving real-life problems that have a large number of variables. It also presents all alternative solutions to the given problem to the decision maker. A numerical example showing how the proposed method is applied is given and coded in the Maple programming language.

Anahtar Kelimeler

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

Proje Numarası

FBA-2021-4032

Doğrusal Tamsayılı Programlama Problemlerinin Çözümü İçin Yeni Alternatif Bir Algoritma

Öz

Bu çalışmada doğrusal bir amaç fonksiyonuna ve doğrusal eşitlik veya eşitsizliklereden oluşan kısıtlara sahip olan Doğrusal Tamsayılı Programlama (DTP) Problemlerinin çözümü için yeni alternatif bir yöntem ve yeni alternatif bir algoritma sunulmaktadır. Yöntemimiz basit cebirsel işlemler ve matematik programlamaya dayanmaktadır. Doğrusal Tamsayılı Programlama Problemlerinin çözümünde kullanılan pek çok yöntem olmasına rağmen, bu yöntemlerin birçoğu uygulamada ve hesaplamada bazı güçlüklere sahiptir. Bu güçlüklere sahip olmayan yöntemimiz, diğer yöntemlere göre problemin sahip olduğu değişken sayısına daha az hassasdır. Bundan dolayı da çok sayıda değişkene sahip olan gerçek yaşam problemlerinin çözümünde de kullanılabilir. Ayrıca verilen problemin tüm alternatif çözümlerini de karar vericiye sunar. Önerilen yöntemin nasıl uygulandığını gösteren bir sayısal örnek verilerek Maple programlama dilinde kodlaması yapılmışıtır.

Anahtar Kelimeler

• Doğrusal tamsayılı programlama
• Doğrusal Diophantine denklemi
• Optimum değer
• Optimum çözüm
• Optimal hiperdüzlem.

Destekleyen Kurum

Yıldız Teknik Üniversitesi Bilimsel Araştırma Projeleri Koordinasyon Birimi

Proje Numarası

FBA-2021-4032

Teşekkür

Bu çalışmaya olan desteklerinden dolayı Yıldız Teknik Üniversitesi Bilimsel Araştırma Projeleri Koordinasyon Birimine teşekkür ederim.

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 fixed point 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.