Inscrição na biblioteca: Guest
Portal Digital Begell Biblioteca digital da Begell eBooks Diários Referências e Anais Coleções de pesquisa
Journal of Automation and Information Sciences
SJR: 0.275 SNIP: 0.59 CiteScore™: 0.8

ISSN Imprimir: 1064-2315
ISSN On-line: 2163-9337

Volume 52, 2020 Volume 51, 2019 Volume 50, 2018 Volume 49, 2017 Volume 48, 2016 Volume 47, 2015 Volume 46, 2014 Volume 45, 2013 Volume 44, 2012 Volume 43, 2011 Volume 42, 2010 Volume 41, 2009 Volume 40, 2008 Volume 39, 2007 Volume 38, 2006 Volume 37, 2005 Volume 36, 2004 Volume 35, 2003 Volume 34, 2002 Volume 33, 2001 Volume 32, 2000 Volume 31, 1999 Volume 30, 1998 Volume 29, 1997 Volume 28, 1996

Journal of Automation and Information Sciences

DOI: 10.1615/JAutomatInfScien.v43.i11.50
pages 48-56

Solving Knapsack Problem: Postoptimality Analysis and Branch and Bound Method

Victor A. Mikhailyuk
V.M. Glushkov Institute of Cybernetics of National Academy of Sciences of Ukraine, Kiev


The algorithm of postoptimality analysis is proposed for determining exact solutions of family of knapsack problems including an initial problem. The computational experiment shows that the average time of solving the family problem is at least 10 times less than the time of solving the initial problem by branch and bound method.


  1. Kozeratskaya L.N., Lebedeva T.T., Sergienko I.V., Stability matters, parametric and postoptimal analysis of discrete optimization problems.

  2. Sergienko I.V., Shilo V.P., Discrete optimization problems. Problems, solution methods, investigations.

  3. Geoffrion A.M., Nauss R., Parametric and postoptimality analysis in integer linear programming.

  4. Roodman G.M., Postoptimality analysis in zero one programming by implicit enumeration.

  5. Greenberg H.J., An annotated bibliography for post-solution analysis in mixed integer programming and combinatorial optimization.

  6. Woodruff D.L., Advances in computational and stochastic optimization, logic programming and heuristic search.

  7. Sigal I.H., Ivanova A.P., Introduction to applied discrete programming: models and computation algorithms.

  8. Garey M., Johnson D.S., Computers and intractability.

  9. Martello S., Toth P., Knapsack problems. Algorithms and computer implementations.

  10. Mikhailyuk V.A., General approach to estimating the complexity of postoptimality analysis for discrete optimization problems.

Articles with similar content:

Analytical and Numerical Solution for One-Dimensional Two-Phase Flow in Homogeneous Porous Medium
Journal of Porous Media, Vol.12, 2009, issue 12
Jiri Mikyska, Radek Fucik, Michal Benes, Tissa H. Illangasekare
Algorithms for Constructing the Guaranteed Solution and Guaranteed Approximate Solution of Multidimensional Knapsack Problem
Journal of Automation and Information Sciences, Vol.46, 2014, issue 9
Nazim Nariman oglu Mamedov , Knyaz Shuraslan oglu Mamedov
The Statement and Solution of the Knapsack Problem with Fuzzy Data
Journal of Automation and Information Sciences, Vol.41, 2009, issue 9
Georgiy A. Donets, Alexandra O. Yemets
Perturbation Method in Problems of Linear Matrix Regression
Journal of Automation and Information Sciences, Vol.52, 2020, issue 1
Petr N. Zinko , Taras P. Zinko , Alexander G. Nakonechnyi, Grigoriy I. Kudin
Uniform Approximations of Functions of Lipschitz Class by Threeharmonic Poisson Integrals
Journal of Automation and Information Sciences, Vol.49, 2017, issue 12
Ulyana Z. Hrabova