File Exchange

image thumbnail

Multi-Knapsack solver

version 1.2 (54.8 KB) by

Multi-Knapsack solver by two stochastic optimizer : CEM & BK algorithms

8 Downloads

Updated

View License

Multi-Knapsack solver by two stochastic solvers : i) by Cross-Entropy Method and ii) by Botev-Kroese Method for the following problem

max S(X)=(p^{t}X)
st. WX <= c

Please run the demo files :

test_ce_knapsack.m
test_cemcmc_knapsack.m

NB. You may need to recompile mex-files. Please open run "mexme_mks" to compile on your own platform.

Comments and Ratings (13)

Yang Yang

Where is the file database about the test?

Example provided in the documentation gives the following errors.

>> load weish01.mat
>> out = ce_knapsack(p , W , c);
>> disp(sprintf('\nS_CE = %5.1f, S_opt = %5.1f' , out.S_opt , S_opt))

Error using binornd (line 25)
Requires at least two input arguments.

Error in ce_knapsack (line 149)
X = binornd(T);

Sebastien PARIS

Daniel,

I will say multiple-knapsack containers.

Daniel Kerry

Hi,
I would like to know if the knapsack program is meant for multiple-constraint or multiple-knapsack containers or both?
thanks

Sebastien PARIS

Merve : I think so, please build a Matrix W from your sole weight w by W = w(ones(m , 1 , :)).

Regards

Merve

Merve (view profile)

I'm looking for multiple choice knapsack problem where there is only one single weight on the RHS in stead of having weights(i).

Is there any easy way to modify your algorithm for multiple choice knapsack?

Sebastien PARIS

Yes it should

Garrett

I'm looking for a 0/1 knapsack solver that can deal with multiple constraints. Can this program do that?

Sebastien PARIS

Yes it should

dhuan Du

Is this knapsack solver able to deal with coninuous cost value?

Thanks

liudaohai liudaohai

Thank you very much!!!

Sebastien PARIS

You probably use the LCC compiler.
Please add

#define min(a , b) ((a) <= (b) ? (a) : (b))

on the top of the *.c file.

liudaohai liudaohai

1. mex -f mexopts_intel10amd.bat -output gibbsampler_knapsack.dll gibbsampler_knapsack.c

D:\MATLAB\BIN\WIN32\MEX.PL: Error: Could not find specified options file
'mexopts_intel10amd.bat'.

??? Error using ==> mex
Unable to complete successfully
2. mex -g -output gibbsampler_knapsack.dll gibbsampler_knapsack.c
Error GIBBSAMPLER_KNAPSACK.C 478 undefined reference to _min

D:\MATLAB\BIN\WIN32\MEX.PL: Error: Link of 'gibbsampler_knapsack.dll.dll' failed.

??? Error using ==> mex
Unable to complete successfully

Updates

1.2

-Compatible with Lunix64 & GCC
-Add mexme_mks

1.1

-Should compile on non-C99 compiler
-Add mexme_knapsack function

-Fixed database (W matrix were not in the correct form)
-Add injection procedure in BK algorithm

MATLAB Release
MATLAB 7.5 (R2007b)

Download apps, toolboxes, and other File Exchange content using Add-On Explorer in MATLAB.

» Watch video