A software program for optimal 1D cutting suport

• Autorzy: Pacek M. , Horla D.

Warianty tytułu

PL

Program wspomagający proces optymalnego docinania 1D

• Języki publikacji: EN

Abstrakty

EN

The paper summarizes the procedure of solving 1D optimal cutting problems, giving details of coding it using dynamic programming, knapsack problem formulation and column generation approach. Finally, the software program for optimal 1D cutting support is described, which is the open code version enabling researchers to extent its capabilities. The paper ends by giving solutions to stated problems and the description of the GUI of the program. At the end of the paper, the reference to the other paper of the authors discussing the effectiveness of the proposed solution is given, tightly connected with this paper.

PL

W artykule przedstawiono procedurę rozwiązywania zadania optymalizacji docinania 1D, włączając szczegóły zakodowania algorytmu przy użyciu programowania dynamicznego, formalizmu zadania plecakowego oraz metody generowania kolumn. W końcu, opisano program wspomagania optymalnego docinania, w postaci programu w otwartym kodzie co pozwoli badaczom na jego dalsze rozwijanie. Artykuł zawiera rozwiązania przykładowych zadań optymalizacji, jak i też opis interfejsu użytkownika. Zawarto również odnośnik do drugiego artykułu autorów, przedstawiającego efektywność zastosowanych metod.

Słowa kluczowe

EN

linear programming; knapsack problem; optimization; cutting problem; column generation

PL

programowanie liniowe; problem plecakowy; optymalizacja; zadanie docinania

• Wydawca: Poznańskie Towarzystwo Przyjaciół Nauk
• Czasopismo: Studia z Automatyki i Informatyki
• Rocznik: 2018
• Tom: T. 43
• Strony: 95--107
• Opis fizyczny: Bibliogr. 14 poz., rys.

Twórcy

autor

Pacek M.

• Poznan University of Technology, Faculty of Electrical Engineering, Institute of Control, Robotics and Information Engineering, ul. Piotrowo 3a, 60-965 Poznan, Poland

autor

Horla D.

• Poznan University of Technology, Faculty of Electrical Engineering, Institute of Control, Robotics and Information Engineering, ul. Piotrowo 3a, 60-965 Poznan, Poland

Bibliografia

• [1] J. Arora. Introduction to optimum design. Elsevier, 2nd edition, 2004.
• [2] J. Carhalho. LP models for bin-packing and cutting stock problems. European Journal of Operational Research, 141(2):253–273, 2002.
• [3] J. Carvalho. Exact solution of cutting stock problems using column generation and branch-andbound. International transactions in Operational Research, 5(1):35–44, 1998.
• [4] E. Chong and S. Zak. An introduction to optimization. Wiley, 2nd edition, 2001.
• [5] P. Debrah. Cutting stock problem based on the linear programming approach. Master’s thesis, University of Science and Technology, Kumasi, 2011.
• [6] D. Horla. Computational burden analysis for integer knapsack problems solved with dynamic programming. In Proceedings of the 14th International Conference on Informatics in Control, Automation and Robotics – Volume 1, pages 215–220, 2017.
• [7] M. Hristakeva and D. Shrestha. Different approaches to solve the 0/1 knapsack problem. In Proceedings of the 38th Midwest Instruction and Computing Symposium, pages 1–14. University of Wisconsin-Eau Claire, Eau Claire, WI, 2005.
• [8] P. Kaden and D. Horla. Performance evaluation of minimization methods for binary and integer LP problems. Studia z automatyki i informatyki, 39:7–31, 2014.
• [9] C. Kazunga, M. Lillian, and M. Jabulani. A carpentry cutting sstudy for planks cutting in Zimbabwe. Journal of Sustaiable Development in Africa, 13(4):18–29, 2011.
• [10] H. Kellerer, U. Pferschy, and D. Pisinger. Knapsack Problems. Springer, 2004.
• [11] R. Morabito and V. Garcia. The cutting stock problem in hardboadd industry: a case study. Computers and Operations research, 25(6):469–485, 1998.
• [12] L. D. S. Moura. An efficient dynamic programming algorithm for the unbounded knapsack problem. Technical report, Universidade de federal de Rio Grande do Sul, Porto Alegre, 2012.
• [13] J. Nocedal and S. Wright. Numerical Optimization. Springer, 1999.
• [14] A. Randvidran, K. Ragsdell, and G. Reklaitis. Engineering optimization. Methods and applications. Wiley, 2nd edition, 2006.

Uwagi

Opracowanie rekordu w ramach umowy 509/P-DUN/2018 ze środków MNiSW przeznaczonych na działalność upowszechniającą naukę (2018).