# flow-cover separation using local search

 2 Hello I'm designing a separator for flow-cover inequalities coming from fixed-charge network structure of my problem Since the separation problem is based on a pretty simple non-linear 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 306●1●6 accept rate: 12%

 2 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 ... ♦ 3.6k●4●27●65 accept rate: 6% 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)*(1-B[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 non-linearity (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 ... ♦
 toggle preview community wiki

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "Title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported

Tags:

×23