Multiplication of variables in "intlinprog" for mixed integer linear programming

Hi,

I want to minimize the objective function like y*(x1*c1+x2*c2) where y,x1 and x2 are decision variables and c1,c2 are constants. Here y would be a binary result that is either 1 or 0 and x1 and x2 are real numbers. I was trying to use 'intlinprog' for this problem bus was facing difficulty to fit these variables in the objective function and the constraints as well since the variables are in multiplied form.I want to know whether I can solve this type of problem using 'intlinprog' function or I should go to other dirrection? If 'intlinprog' can be used then how can this be implemented?

Answer 1

[Matt J]

Since y is binary, just solve 2 separate problems corresponding to the cases y=0 and y=1, which will be standard linear programs. Then take the solution which gives the lowest value of the original objective.

[Md Tanvir Rahman]

Thanks for your answer Matts. But the way you told would be difficult to implement here as there are 3 variables of binary numbers in the main objective function. I am describing the total objective function here.

I want to minimize the objective function like {y1*(x1*c1+x2*c2)+y2*(x3*c3+x4*c4)+y3*(x5*c5+x6*c6)+y1*C7+y2*C8+y3*C9} where y1,y2,y3,x1,x2,x3,x4,x5 and x6 are decision variables and c1,c2,c3,c4,c5,c6,C7,C8 and C9 are constants. Here y1,y2,y3 would be a binary result that is either 1 or 0 and x1,x2,x3,x4,x5 and x6 are real numbers. I was trying to use 'intlinprog' for this problem bus was facing difficulty to fit these variables in the objective function and the constraints as well since the variables are in multiplied form.I want to know whether I can solve this type of problem using 'intlinprog' function or I should go to other direction? If 'intlinprog' can be used then how can this be implemented?

[Matt J]

Even now that you have 3 binary variables, my proposal is still reasonable. There are only 8 possible combinations of values of y1,y2,y3 to loop over.

More generally, the answer to your question is no. The multiplicative forms break the linearity of the problem, so intlinprog does not directly apply. You could use ga(), if you have the Global Optimization Toolbox.

[Md Tanvir Rahman]

Thanks to you...

Answer 2

[Matt J]

Come to think of it, I think there is a way to rewrite the problem in standard intlinprog form, assuming the x variables have known bounds xmin(i)<=x(i)<=xmax(i). To simplify, I'll consider a version of the problem with only one y term,

     y*(c1*x1+c2*x2) + c3*y

but the generalization to additional y's is straightfoward.

First, let us assume with no loss of generality that all bounds xmin(i)=0 and all xmax(i)=1. You can always normalize the x(i) so that this holds by rescaling the constants c1, c2, c3. Now define new non-binary variables z1=y*x1, z2=y*x2 so that the objective function can be rewritten in the linear form,

    f(x1,x2,y,z1,z2) = c1*z1+c2*z2+c3*y

However, we also need to add linear constraints on z1 and z2 so that they have the correct relationship with y,x1,x2. The first set of constraints needed are,

    0<=z1<=y
    0<=z2<=y

This ensures that z1=z2=0 when y=0 and conversely that y=1 whever z1>0 or z2>0. A further set of constraints needed is

     0<=x1-z1<=1-y
     0<=x2-z2<=1-y

This ensures that, when y=1, we have z1=x1 and z2=x2. Obviously also, you must include whatever other constraints you already had on x1,x2, and y.

[Md Tanvir Rahman]

Thank a lot bro.