Abonnement à la biblothèque: Guest
Journal of Automation and Information Sciences

Publication de 12  numéros par an

ISSN Imprimer: 1064-2315

ISSN En ligne: 2163-9337

SJR: 0.173 SNIP: 0.588 CiteScore™:: 2

Indexed in

Solving Knapsack Problem: Postoptimality Analysis and Branch and Bound Method

Volume 43, Numéro 11, 2011, pp. 48-56
DOI: 10.1615/JAutomatInfScien.v43.i11.50
Get accessGet access

RÉSUMÉ

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.

RÉFÉRENCES
  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.

Portail numérique Bibliothèque numérique eBooks Revues Références et comptes rendus Collections Prix et politiques d'abonnement Begell House Contactez-nous Language English 中文 Русский Português German French Spain