Suscripción a Biblioteca: Guest
Portal Digitalde Biblioteca Digital eLibros Revistas Referencias y Libros de Ponencias Colecciones
Journal of Automation and Information Sciences
SJR: 0.275 SNIP: 0.59 CiteScore™: 0.8

ISSN Imprimir: 1064-2315
ISSN En Línea: 2163-9337

Volumes:
Volumen 52, 2020 Volumen 51, 2019 Volumen 50, 2018 Volumen 49, 2017 Volumen 48, 2016 Volumen 47, 2015 Volumen 46, 2014 Volumen 45, 2013 Volumen 44, 2012 Volumen 43, 2011 Volumen 42, 2010 Volumen 41, 2009 Volumen 40, 2008 Volumen 39, 2007 Volumen 38, 2006 Volumen 37, 2005 Volumen 36, 2004 Volumen 35, 2003 Volumen 34, 2002 Volumen 33, 2001 Volumen 32, 2000 Volumen 31, 1999 Volumen 30, 1998 Volumen 29, 1997 Volumen 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

SINOPSIS

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.

REFERENCIAS

  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:

Optimization of Periodic Systems with Singular Weight Matrix which defines the Quadratic Form of Control Actions
Journal of Automation and Information Sciences, Vol.31, 1999, issue 1-3
Vladimir B. Larin
CHARACTERIZATION OF UNSTABLE MODES IN PARTITIONED CAVITIES
International Heat Transfer Conference 11, Vol.8, 1998, issue
Emilie Gadoin, Patrick Le Quere
APPROXIMATE ANALYTIC DETERMINATION OF THE AVERAGE VALUES OF POTENTIAL FUNCTIONS OCCURRING IN CHEMICAL TRANSPORT PHENOMENA
International Heat Transfer Conference 5, Vol.2, 1974, issue
K. Polinszky, J. Fulop, E. Vasanits
GENERALIZATION OF THE GODUNOV METHOD TO THE PROBLEMS OF COMPUTATIONAL AEROACOUSTICS
TsAGI Science Journal, Vol.41, 2010, issue 1
Igor Stanislavovich Menshov
ONE-DIMENSIONAL APPROXIMATE ANALYTICAL SOLUTIONS OF HEAT CONDUCTION IN SEMI-INFINITE SOLIDS WITH TEMPERATURE-DEPENDENT PROPERTIES
Hybrid Methods in Engineering, Vol.3, 2001, issue 4
Gaetano Barbaro, Nicola Bianco, Oronzio Manca