Performance evaluation of basic optimization methods for polynomial binary problems

• Autorzy: Ignaczak, M. , Horla, D.

Warianty tytułu

PL

Ocena efektywności metod optymalizacji dla zadań programowania 0-1 z funkcjami wielomianowymi

• Języki publikacji: EN

Abstrakty

EN

The paper considers performance issues of a class of iterative minimization methods of binary programs with polynomial functions. 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 optymalizacji dla zadań z wielomianową funkcją celu i 0-1 zmiennymi decyzyjnymi. 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

PL

zadania z wielomianową funkcją; optymalizacja; złożoność obliczeniowa

EN

binary polynomial problems; optimization; computational complexity

• Czasopismo: Studia z Automatyki i Informatyki
• Rocznik: 2016
• Tom: T. 41
• Strony: 7--34
• Opis fizyczny: Bibliogr. 7 poz., rys., tab.

Twórcy

autor

Ignaczak, M.

• 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] J. Arora. Introduction to Optimum Design. Elsevier Academic Press, 2nd edition, 2004.
• [2] D. Bertsimas, D. Iancu, and D. Katz. A general purpose local search algorithm for binary optimization (manuscript). 2008.
• [3] D. Granot and D. Granot. Generalized covering relaxation for 0-1 programs. Operations Research, 28(6):1442-1450, 1980.
• [4] D. Li and S. Xiaoling. Nonlinear Integer Programming. USA, Springer, 2006.
• [5] D. Pisinger, A. Rasmussen, and R. Sandvik. Solution of large-sized quadratic knapsack problems through aggressive reduction. Technical Report 2004/11, University of Copenhagen, 2004.
• [6] M. Syslo, N. Deo, and J. Kowalik. Algorytmy optymalizacji dyskretnej z programami w jezyku Pascal. Wydawnictwo Naukowe PWN, Warszawa, 1995.
• [7] P. Venkataraman. Applied Optimization with Matlab Programming. Wiley, 2009.

Uwagi

Opracowanie ze środków MNiSW w ramach umowy 812/P-DUN/2016 na działalność upowszechniającą naukę (zadania 2017).