Branch and Bound method for binary problems with the procedure that reduces dimension of problems

• Autorzy: Chudy M.

Warianty tytułu

PL

Metoda podziału i oszacowań dla zadań binarnych z procedurą, która redukuje wymiar zadań

• Języki publikacji: EN

Abstrakty

EN

The relationships between elements of coefficient matrix, elements of vector and elements of vector in general binary problem are considered. Some of them allow us to establish the values of selected elements of feasible or optimal vector . This procedure reduces the dimension of basic problem and can be install in branch and bound method. It gives positive effects.

PL

Przedstawiono kilka własności problemów binarnych, które pozwalają redukować wymiar zadania poprzez wyszukiwanie i ustalanie wartości niektórych zmiennych. W dopuszczalnych wektorach binarnych danego zadania wartości te muszą być przyjęte. Procedurę wykorzystującą te własności wmontowano w metodę podziału i oszacowań, w szczególności do algorytmu przeglądu pośredniego dla zadań binarnych.

Słowa kluczowe

EN

binary problem; branch and bound method; reducing dimension

PL

problem binarny; metoda podziału i oszacowań; redukcja wymiaru

• Wydawca: Institute of Computer and Information Systems, Faculty of Cybernetics, Military University of Technology
• Czasopismo: Computer Science and Mathematical Modelling
• Rocznik: 2016
• Tom: No. 4
• Strony: 13--18
• Opis fizyczny: Bibliogr. 6 poz.

Twórcy

autor

Chudy M.

• Military University of Technology, Faculty of Cybernetics Institute of Computer and Information Systems Kaliskiego Str. 2, 00-908 Warsaw, Poland

Bibliografia

• 1. Chudy M., Wybrane algorytmy optymalizacji, EXIT, Warszawa, 2014.
• 2. Garfinkel R.S., Nemhauser G.L. Programowanie całkowitoliczbowe, PWN, Warszawa, 1978.
• 3. Hromkovic J., Algorithmics for Hard Problems. Introduction to Combinatorial Optimization, Randomization, Approximation and Heuristics, Springer-Verlag, Berlin, Heidelberg, 2001.
• 4. Martello S., Toth P., An exact algorithm for the two-constraint 0-1 knapsack problem, Operations Research, No. 5, 826–835(2003).
• 5. Nemhauser G.L.,Wolsey L.A., Integer and Combinatorial Optimization, John Wiley & Sons, 1999.
• 6. Sierksma G., Linear and Integer Programming. Theory and Practice, Marcel Dekker, Inc. New York, 1996.

Uwagi

PL

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