"A study of the Mean Field Approach to Knapsack Problems"
M. Ohlsson and H.Pi
The mean field theory (MFT) approach to knapsack problems is extended to
multiple knapsacks and generalized assignment problems with Potts mean
field equations governing the dynamics. Numerical tests against ``state
of the art'' conventional algorithms shows good performance for the mean
field approach. The inherently parallelism of the MFT equation makes them
suitable for direct implementations in micro-chips. It is demonstrated
numerically that the performance is essentially not affected when only a
limited number of bits is used in the mean field equations.
Also, a hybrid algorithm with linear programming and mean field components
is showed to further improve the performance for the difficult homogeneous
NxM knapsack problem.
LU TP 95-07