Linprog - How define lb and ub as interval containing zero

I'm using the function linprog of the optimization toolbox. I have defined an interval by use of lb and ub: 0 <= x <= 90.

But actually I would like 'x' getting values between 15 <= x <= 90 AND containing zero. I don't want 'x' getting values between 0 and 15.

The reason is that there's a power station and it's not useful when the power station charges with power less than 15 MW. But it should be possible that the power station has power 0 MW when it's off (not charging).

The background is that I want to charge a power station while the electricity costs are cheap.

Is there any solution?

[Matt J]

How many x(i) are involved?

[Lare]

About 2000. Any idea? :)

Answer 1

[Matt J]

I think you can rewrite this as a mixed integer linear programming (and solve with intlinprog). Make the following substitution everywhere for x(i),

    x(i)=15*b(i)+y(i)

where b(i) is a binary variable and y(i) is continuous-valued variable obeying the additional linear constraints

      0<=y(i)<=75
    y(i)<=75*b(i)

When b(i)=0, the constraints on y(i) reduce to y(i)=0 and hence x(i) can equal 0. Conversley, when b(i)=1, the constraints on y(i) reduce to 0<=y(i)<=75 and hence x(i) will then span the range 15 to 90.

[Matt J]

To make this numerically, robust, however, I think you will have to modify the second constraint to

     y(i)<=75*b(i) +(1-bi)*delta

where 0<delta<15 is a small positive number. This is a relaxed version in which x(i) can occupy either the interval [0,delta] or [15,90].

However, if intlinprog gives you a relaxed solution which has some x(i)<=delta, then you will know that that x(i) is trying to be close to 0. You can then re-solve the problem with linprog, setting those x(i)=0 rigorously.

My concern with setting delta=0 exactly is that, when b(i)=0, the constraints on y(i) reduce to

   y(i)<=0
   y(i)>=0

In perfect math, these inequalities are equivalent to y(i)=0, of course, but processing an equality as two inequalities is an unstable thing numerically for optimization software.

[Lare]

Thanks for your help, Matt.

But I m not sure how to formulate it when I assume the function as it's defined by x=intlinprog(f,intcon,A,b,Aeq,beq,lb,ub).

You said that b(i) is the binary variable. But I can only choose x(i) to be the binary variable by setting intcon. And there's no variable y(i) or delta. And how can I set

x(i)=15*b(i)+y(i)

as input. There's no x-input in function intlinprog.

Thanks a lot

[Matt J]

No, you have to perform a change of variables and rewrite your entire problem in terms of the new vector of unknowns z=[y(:);b(:)]. This will lead to new contraint matrices, different from the A,Aeq that you originally had , that you have to pass to intlinprog . In matrix form, the change of variables is,

    x=[15*speye(N), speye(N)]*z

where N=length(x) is the original number of unknowns that you had. So, if you originally had

   min. f*x

    A_old*x<=b
    Aeq_old=beq

then after the change of variables, you will now have

    min f_new*z

    A_new*z <= b
    Aeq_new*z =beq

where,

   M=[15*speye(N), speye(N)]

   f_new=f*M;
   A_new=A_old*M
   Aeq_new=Aeq*M

You also you have to append the additional constraints on y and b that I mentioned, as well as 0<=b(i)<=1. Once you've done all this, your call to intlinprog will look like

   z = intlinprog(f_new,N+1:2*N,A_new,b_new,Aeq_new,beq,lb_new,ub_new)

[Matt J]

Lare Commented:

You wrote 'b_new' and 'beq' in:

z = intlinprog(f_new,N+1:2*N,A_new,b_new,Aeq_new,beq,lb_new,ub_new)

Does it mean that 'b' changes and 'beq' stays the same as before? I assume that both 'b' and 'beq' stays the same as before.

Additionally I created 'lb_new' and 'ub_new' by :

lb_new= [0 0 ... 0 0;  0 0 ... 0 0]; %to restrict b(i) and y(i)
ub_new= [1 1 ... 1 1;  75 75 ... 75 75]; %to restrict (bi) and y(i)

But what about the second constraint:

y(i)<=75*b(i) +(1-bi)*delta

I have not used it. Where do I have to append it?

Thanks a lot for helping.

[Matt J]

Does it mean that 'b' changes and 'beq' stays the same as before?

b will have to change, because after you've transformed your original inequality constraints,

    A_new=A_old*M

you still have to add the additional inequality constraints,

   y(i)<=75*b(i) +(1-bi)*delta

These must be added to A_new and b as additional rows,

        newrowsA=[speye(N),  (delta-75)*speye(N)];
        newrowsb= ones(N,1)*delta;

        A_new=[A_new; newrowsA];
        b_new=[b; newrowsb];

[Lare]

Ok, thanks. So I can just define/set delta as a small positive number for example just like

delta= 0.5;

?

[Matt J]

Yes. I thought you might go even smaller (e.g., delta=1e-4), but you'll have to experiment.

[Duc Le]

Hi, I have the same problem but I want only define lb = 0 and range intervall for the first and fifth variable x(1) x(5) and the other variables have got different lb and ub. How could I define it? Could you help me?

[Matt J]

Hi Duc,

I'm not sure what to add to the above. I think the same technique should apply. Just do it only for i=1 and i=5.