Performance evaluation of minimization methods for binary and integer LP problems

• Autorzy: Kaden P. , Horla D.

Warianty tytułu

PL

Ocena szybkości działania metod minimalizacji dla zadań programowania liniowego w zbiorach dyskretnych

• Języki publikacji: EN

Abstrakty

EN

The paper considers performance issues of a class of iterative minimization methods of binary and linear programs. Problem structures that assure superior performance of a specific method have been stipulated with appropriate conclusions drawn.

PL

W artykule poruszono zagadnienie szybkości działania metod minimalizacji w zbiorach dyskretnych (binarne i całkowitoliczbowe) dla zadań programowania liniowego. Wskazano przypadki, dla których konkretna metoda działa szybciej niż pozostałe oraz wyciągnięto wnioski odnośnie takiego stanu rzeczy.

Słowa kluczowe

EN

linear programming; minimization methods; discrete sets; integer LP problems; optimization; computational complexity

PL

programowanie liniowe; metody minimalizacji; zbiory dyskretne

• Wydawca: Poznańskie Towarzystwo Przyjaciół Nauk
• Czasopismo: Studia z Automatyki i Informatyki
• Rocznik: 2014
• Tom: T. 39
• Strony: 7--31
• Opis fizyczny: Bibliogr. 10 poz., rys., tab.

Twórcy

autor

Kaden P.

• Poznan University of Technology, Institute of Control and Information Engineering, Department of Control and Robotics, Piotrowo 3a Str., 60-965 Poznan

autor

Horla D.

• Poznan University of Technology, Institute of Control and Information Engineering, Department of Control and Robotics, Piotrowo 3a Str., 60-965 Poznan

Bibliografia

• [1] Balas E., An Additive Algorithm for Solving Linear Programs with Zero-one Variables, Operations Research, Vol. 13(4), 1965, pp. 517-546.
• [2] Bazaraa M.S., Sherali H.D., Shetty C.M., Nonlinear Programming: Theory and Algorithms, 3rd ed., New Jersey, Wiley 2006.
• [3] Dantzig G.B., Thapa M.N., Linear Programming 1: Introduction, Springer Verlag 1997.
• [4] Dantzig G.B., Thapa M.N., Linear Programming 2: Theory and Extensions, Springer 2003.
• [5] Horla D., Metody obliczeniowe optymalizacji w zadaniach, Poznań, Wydawnictwo Politechniki Poznańskiej, 2008 (in Polish).
• [6] Pedregal P., Introduction to Optimization, New York, Springer-Verlag 2004.
• [7] Stadnicki J., Teoria i praktyka rozwiązywania zadań optymalizacji z przykładami zastosowań technicznych, Warszawa, Wydawnictwa Naukowo-Techniczne 2006 (in Polish).
• [8] Sysło M.M., Deo N., Kowalik J.S., Algorytmy optymalizacji dyskretnej z programami w języku Pascal, Warszawa, Wydawnictwo Naukowe PWN 1995 (in Polish).
• [9] Vanderbei R.J., Linear Programming: Foundations and Extensions, 2nd ed, Springer 2001.
• [10] Venkataraman P., Applied Optimization with Matlab Programming, Wiley 2009.