CODEWITHSUNDEEP
variable-assignmentlinear-programminginteger-programmingquadratic-programming
user7125961
user7125961

Reputation: 11

Assignment optimization / Set covering

I have the following task and didn't find any working solution.

I need to find a optimal solution for network node placement. The objective is to minimize the digging cost for connecting cables. Some digging costs depending on each other. E.g. imagine you have 2 nodes in a row and dig one cable to the first then you don't have to include this digging costs to the fist node for the digging to the second node. But if you just select the second node you have to add the costs for digging to node 1 and from node 1 to node 2.

For each node there is a certain number of users which can be supplied by it. To reach a user coverage of at least e.g. 90 % of the users is the constraint.

I tried to use quadratic programming but cvx doesn't like it:

cvx_begin
variable x(n,1) binary;
minimize( x'*Q*x )
subject to
   x'*A*x >= 0.9;
cvx_end

Is there anyone having a better idea... using e.g binary linear or quadratic programming?

Thanks and BR

Upvotes: 1

Views: 110

Answers (1)

Erwin Kalvelagen
Erwin Kalvelagen

Reputation: 16724

x'Ax is a summation of a(i,j)*x(i)*x(j). The products z(i,j)=x(i)*x(j) can be linearized by:

z(i,j) <= x(i)
z(i,j) <= x(j)
z(i,j) >= x(i)+x(j)-1
z(i,j) in {0,1}

With this you have a linear MIP problem.

There are a few optimizations we can use in this formulation:

  • We can make A and Q triangular matrices by exploiting symmetry
  • The diagonals can be handled specially as x(i)^2=x(i)
  • The z(i,j)'s can be reduced to a strictly triangular structure

Upvotes: 1

Related Questions