Code covered by the BSD License

### Highlights from Multi-Knapsack solver

Be the first to rate this file! 29 Downloads (last 30 days) File Size: 54.8 KB File ID: #20436

# Multi-Knapsack solver

### Sebastien PARIS (view profile)

25 Jun 2008 (Updated )

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

File Information
Description

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.

MATLAB release MATLAB 7.5 (R2007b)
Other requirements A C compiler.
12 Mar 2015 Naveen Manikandan Periasamy

### Naveen Manikandan Periasamy (view profile)

Example provided in the documentation gives the following errors.

>> 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);

Comment only
23 Feb 2011 Sebastien PARIS

### Sebastien PARIS (view profile)

Daniel,

I will say multiple-knapsack containers.

Comment only
15 Feb 2011 Daniel Kerry

### Daniel Kerry (view profile)

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

Comment only
02 Nov 2010 Sebastien PARIS

### Sebastien PARIS (view profile)

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

Regards

Comment only
28 Oct 2010 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?

Comment only
25 Jul 2009 Sebastien PARIS

### Sebastien PARIS (view profile)

Yes it should

Comment only
07 Jul 2009 Garrett

### Garrett (view profile)

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

Comment only
19 Jun 2009 Sebastien PARIS

### Sebastien PARIS (view profile)

Yes it should

Comment only
18 Jun 2009 dhuan Du

### dhuan Du (view profile)

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

Thanks

Comment only
25 Jul 2008 liudaohai liudaohai

Thank you very much!!!

Comment only
25 Jul 2008 Sebastien PARIS

You probably use the LCC compiler.

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

on the top of the *.c file.

Comment only
25 Jul 2008 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

Comment only
19 Aug 2008

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

08 Jun 2009

-Should compile on non-C99 compiler