Association Problem With Weighting Coefficient


(Anthony ) #1

Hello every one, I am trying to covert this to CVX.


x_ij is a weighted factor variable to control the balance of a and b.
y_ij is the association variable, i.e., if i is associated to J, then its corresponding y_ij = 1, otherwise y_ij = 0.
m = 1 for simplicity.

a = [4,6,3,8,5]’;
b = [9,14,12,19,15]’;
c = [20,30,70,60,50];
d = [1,1,1,1,1];
n = 5;

cvx_begin
variables x(n) y(n)
minimize((sum((vec(a).*(1-x))+(vec(b).*x))).*y);
for i=1:n
x(i), y(i)
end
subject to
0 <= x <= 1
0 <= y <= 1
sum(c ) * y >= 50;
sum(d) * y <= 2;
cvx_end


(Mark L. Stone) #2

You need to linearize the product terms, x_{ij}y_{ij}, which are products of one continuous variable and one binary variable, per section 2.8 of “FICO Xpress Optimization Suite MIP formulations and linearizations Quick reference” https://www.artelys.com/uploads/pdfs/Xpress/mipformref-1.pdf


(Anthony ) #3

I have tried the suggestion in the link on product values y = x . d for one continuous variable x and one binary variable d. I don’t have a professional version of CVX, so I cannot declare a binary variable. Is this still achievable?


(Mark L. Stone) #4

No it’s not, I don’t have a professional version, so I can’t run such code either.

Note that the linearization in this case does not require the introduction of any additional binary variables. Of course, y_{ij} is already binary, which would preclude you from using the free (non-Professional, non-academic) version of CVX even if there were no product terms to linearize, unless you had a reformulation which didn’t require binary (or integer) variables; for instance, it t could be assured that y constrained to be 0 <= y <= 1 would always be driven at the optimum to either 0 or 1, without having been declared binary or integer.


(Anthony ) #5

Please, can you run a sample code implementing the linearization formulation, then hopefully I will be able to develop my model from that foundation. I will be very grateful.


(Mark L. Stone) #6

You can see an example here How to formulate a MILP in CVX