Inscrição na biblioteca: Guest
Journal of Automation and Information Sciences

Publicou 12 edições por ano

ISSN Imprimir: 1064-2315

ISSN On-line: 2163-9337

SJR: 0.173 SNIP: 0.588 CiteScore™:: 2

Indexed in

Solving Knapsack Problem: Postoptimality Analysis and Branch and Bound Method

Volume 43, Edição 11, 2011, pp. 48-56
DOI: 10.1615/JAutomatInfScien.v43.i11.50
Get accessGet access

RESUMO

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.

Referências
  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.

Portal Digital Begell Biblioteca digital da Begell eBooks Diários Referências e Anais Coleções de pesquisa Políticas de preços e assinaturas Begell House Contato Language English 中文 Русский Português German French Spain