How to write this optimization prolem in CVX?


(Dipak Narayanan) #1

I am trying to solve the problem below. Here, A is a binary integer matrix, F is a matrix with elements between 0 and 1.

I am getting some error for S, which is an element-wise multiplication among three matrices A, F and R. A, F, and R are of the same dimension. R is known. A and F are variables. Vector D is also known.

    cvx_begin quiet

         variable P(N,M) integer
         variable Q(N,M)
         variable t

         S=sum(P.*Q);

         maximize t
         subject to
         S>=t.*L;
         sum(A)>=2;
         Q>=0;
         Q<=1;
   cvx_end

(Mark L. Stone) #2

The error is due to multiplying CVX variables, A.*F

Is A really binary, not general integer. If so, declare it binary..

If A is binary, believe this can be reformulated as a mixed-integer convex problem using Big M logic to express S >= t.*D as a constraint conditional on the relevant element of A being one…To do this, please read and follow the guidance in the recommendations I provided you in Can this optimization problem be modeled in CVX? .

I’ll let you look at " MIP formulations and linearizations Quick reference" by FICO https://www.artelys.com/uploads/pdfs/Xpress/mipformref-1.pdf to figure it out.

A great resource for conic optimization modeling,which has some some integer material, is the “MOSEK Modeling Cookbook” https://docs.mosek.com/modeling-cookbook/index.html , which will greatly help you use CVX (even if you don’t use Mosek, but please don’t tell @Erling I said that).

You’ll probably benefit from putting in the effort to work through “Model Building in Mathematical Programming”, 5th Edition by H. Paul Williams https://www.wiley.com/en-us/Model+Building+in+Mathematical+Programming%2C+5th+Edition-p-9781118443330 . This ought to really help you do effective integer modeling and formulation.

If you have read these, you do not seem to have fully grasped them yet.