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's gravatar image

David
30616
accept rate: 12%


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?

link

answered 05 Nov '10, 07:54

Geoffrey%20De%20Smet's gravatar image

Geoffrey De ... ♦
3.6k32764
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 ... ♦
Your answer
toggle preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "Title")
  • 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

Asked: 04 Nov '10, 18:11

Seen: 1,719 times

Last updated: 05 Nov '10, 07:54

OR-Exchange! Your site for questions, answers, and announcements about operations research.