Computer Science and Information Technologies, Computer Science and Information Technologies 2016

Font Size: 
The local search algorithm in polynomial neighborhoods for the linear packing problem
A. R. Usmanova, A. P. Zemlyanov

Last modified: 2020-12-20


The Bin Packing Problem can be found widely indifferent branches of industry and technique. The conception of solutions neighborhoods and the ways of its construction are considered. The undetermined algorithm of local search in the proposed neighborhoods is offered. The computing experiment performed on the difficult benchmark problems taken from the OR-library is proved theeffectivity of the proposed way.


local search algorithm; polynomial neighborhoods; linear packing problem


1. Garey M.R. and Johnson D.S. Computers andIntractability: A Guide to the Theory of NP-Completeness. W.H. Frecman, San Francisco. 1979.

2. Martello S.,Toth P. Knapsack Problems, Algorithmsand Computer Implemetations. John Wiley and SonsLtd.- England, 1990.

3. Kochetov Y.A., Usmanova A.R. Probabilistic searchwith exclusions for the packing problem incontainers.- Proceedings of the XII InternationalConference Baikal, 2001, pp. 22-27.

4. Usmanova A.R. The probabilistic greedy heuristics forthe packing problem n containers.- Proceedings of theOptim 2001. First All-Russian scientific-practicalconference on solving optimization problems in theindustry. St. Petersburg, 2001, pp.141-145.

5. Falkenauer E. A hybrid Grouping Genetic Algorithmfor Bin Packing. Journal of Heuristics, Vol.2, No1,1996.- pp.5-30.

6. Usmanova A.R. Search in exponential neighborhoodsolutions for linear packing problem. Proceedings ofthe international conference "InformationTechnologies for Intelligent Decision MakingSupport", May 21-25, Ufa, Russia, 2013. Vol.2.pp.189-194

7. Usmanova A.R. Structures of prohibitions list in themethod TS for packing task. Proceedings of theinternational conference "Information Technologiesfor Intelligent Decision Making Support", May 21-25,Ufa, Russia, 2013. Vol.2. pp. 208-211

Full Text: PDF