Geodesic
On the best choice of a~branching variable in the subset sum problem
Diskretnaya Matematika, Tome 29 (2017) no. 1, pp. 51-58.

Voir la notice de l'article provenant de la source Math-Net.Ru

The paper is concerned with estimating the computational complexity of the branch-and-bound method for the subset sum problem. We study the relationship between the way of decomposition of subproblems and the number of the method steps. The standard variant of the branch-and-bound method for the subset sum problem with binary branching is considered: any subproblem is decomposed into two more simple subproblems by assigning values $0$ and $1$ to a selected branching variable. It is shown that for any set of parameters of the problem the procedure of branching variables selection in the descending order of their weights is optimal.
Keywords: the branch-and-bound method, computational complexity, the subset sum problem. 
@article{DM_2017_29_1_a4,
     author = {R. M. Kolpakov and M. A. Posypkin},
     title = {On the best choice of a~branching variable in the subset sum problem},
     journal = {Diskretnaya Matematika},
     pages = {51--58},
     publisher = {mathdoc},
     volume = {29},
     number = {1},
     year = {2017},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DM_2017_29_1_a4/}
}
TY  - JOUR
AU  - R. M. Kolpakov
AU  - M. A. Posypkin
TI  - On the best choice of a~branching variable in the subset sum problem
JO  - Diskretnaya Matematika
PY  - 2017
SP  - 51
EP  - 58
VL  - 29
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DM_2017_29_1_a4/
LA  - ru
ID  - DM_2017_29_1_a4
ER  - 
%0 Journal Article
%A R. M. Kolpakov
%A M. A. Posypkin
%T On the best choice of a~branching variable in the subset sum problem
%J Diskretnaya Matematika
%D 2017
%P 51-58
%V 29
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DM_2017_29_1_a4/
%G ru
%F DM_2017_29_1_a4
R. M. Kolpakov; M. A. Posypkin. On the best choice of a~branching variable in the subset sum problem. Diskretnaya Matematika, Tome 29 (2017) no. 1, pp. 51-58. http://geodesic.mathdoc.fr/item/DM_2017_29_1_a4/

[1] Martello S., Toth P., Knapsack Problems, J. Wiley Sons Ltd, Chichester, 1990, 296 pp. | MR | Zbl

[2] Kellerer H., Pfershy U., Pisinger D., Knapsack Problems, Springer-Verlag, Berlin–Heidelberg, 2004, 548 pp. | MR | Zbl

[3] Kolpakov R. M., Posypkin M. A., “Asimptoticheskaya otsenka slozhnosti metoda vetvei i granits s vetvleniem po drobnoi peremennoi dlya zadachi o rantse”, Diskretn. analiz i issled. operatsii, 15:1 (2008), 58–81 | MR | Zbl

[4] Sigal I. Kh., Ivanova A. P., Vvedenie v prikladnoe diskretnoe programmirovanie, Fizmatlit, M., 2002, 240 pp.

[5] Lazarev A. A., “Graphic approach to combinatorial optimization”, Automation and Remote Control, 68:4 (2007), 583–592 | DOI | MR | Zbl

[6] Finkelshtein Yu. Yu., Priblizhennye metody i prikladnye zadachi diskretnogo programmirovaniya, Nauka, M., 1976, 265 pp.

[7] Grishukhin V. P., “Effektivnost metoda vetvei i granits v zadachakh s bulevymi peremennymi”: Fridman A. A., Issledovaniya po diskretnoi optimizatsii, Nauka, M., 1976, 203–230 | MR

[8] Lazarev A. A., Werner F., “A graphical realization of the dynamic programming method for solving NP-hard combinatorial problems”, Comput. Math. Appl., 58:4 (2009), 619–631 | DOI | MR | Zbl

[9] Kolpakov R. M., Posypkin M. A., “Upper and lower bounds for the complexity of the branch and bound method for the knapsack problem”, Discrete Math. Appl., 20:1 (2010), 95–112 | DOI | DOI | MR | Zbl

[10] Kolpakov R. M., Posypkin M. A., “Verkhnyaya otsenka chisla vetvlenii dlya zadachi o summe podmnozhestv”, Mat. voprosy kibernetiki, 18 (2013), 213–226