Hello I'm designing a separator for flowcover inequalities coming from fixedcharge network structure of my problem Since the separation problem is based on a pretty simple nonlinear binary knapsack problem, I'm wondering whether a local search approach to solve this problem has already been tried ? The litterature I read so far mentions approximation and parametrization of (linear) binary knapsacks but nothing on local search David asked 04 Nov '10, 18:11 David 
I used local search (tabu search actually) on a 3 dimensional knapsack problem recently: planning processes in the cloud and added an extra soft constraint (minimize the cost, not shown in the screenshots). the source code of the score calculation (= fitness function) is here. It took me a few hours, it works but I 'd like to improve the move generation (= neighborhood selection) to deal more efficiently with local optima. Could you explain what the nonlinear aspect means to your knapsack problem? answered 05 Nov '10, 07:54 Geoffrey De ... ♦ Given coefficients A=[a1,a2,a3,...,aN] B=[b1,b2,...,bN] phi=[phi1,phi2,...,phiN] rhs A cover is defined as a subset C of 1..N such as : sum(s in C) A[s] > rhs We note lambda = sum(s in C) A[s]  rhs the cover separation problem is to find the maximal "violated" cover, e.g the one that maximize the expression : sum(s in C) phi[s]+max(0,A[s]lambda)*(1B[s])  brhs when lambda is fixed, this is a linear binary knapsack problem (a binary variable being introduced to say that we choose or not the index s in the cover) Otherwise the expression max(0,A[s]lambda) brings nonlinearity
(05 Nov '10, 15:19)
David
I don't know what a flow cover are (is there any layman explanation out there?), but if I understand it correctly (probably not), you're adding a positive score ocurrence of max(0,(A[s]  lamdba)), for example something like "add a positive soft score (at least 0) per CloudProcess with the value of cloudProcess.extraPoints minus the count of the number of processes on the same cloudComputer as that cloudProcess". That's pretty easy in for example the DRL I linked :)
(05 Nov '10, 15:57)
Geoffrey De ... ♦
