Re: ”Model is infeasible or unbounded“ caused by implies

[Johan Löfberg]

like before?...

[Johan Löfberg]

and that nasty copy-paste code can be simplified to  implies(pos, l == 0) (for consistent vector arguments, it is interpreted element by element)

[Johan Löfberg]

and it looks trivially infeasible to me

There are exactly two zeros in the vector pos

F=F+[sum(pos)==38];

Either pos1 or pos2 is zero

F=F+[pos(1)+pos(2)==1

Either pos3 or pos4 is zero

, pos(3)+pos(4)==1, 

Either pos5 or pos6 is zero

pos(5)+pos(6)==1

you've already forced 3 zeros...

[bin sun]

Ok. Thank you. But when I add the code like: F=F+[pos(1)+pos(2)==1, pos(3)+pos(4)==1, pos(5)+pos(6)==1, pos(7)+pos(8)==1, pos(9)+pos(10)==1];

F=F+[pos(11)+pos(12)==1, pos(13)+pos(14)==1, pos(15)+pos(16)==1, pos(17)+pos(18)==1, pos(19)+pos(20)==1];

F=F+[pos(21)+pos(22)==1, pos(23)+pos(24)==1, pos(25)+pos(26)==1, pos(27)+pos(28)==1, pos(29)+pos(30)==1]; 

F=F+[pos(31)+pos(32)==1, pos(33)+pos(34)==1, pos(35)+pos(36)==1, pos(37)+pos(38)==1, pos(39)+pos(40)==1];

MATLAB will say it is unbounded. I want to use this code to tell yalmip that nearby two positions can only choose one.

[Johan Löfberg]

the copy-paste comment was for the first part.

the second part would be sum(reshape(pos,[],2),2)==1 or pos(1:2:39) + pos(2:2:40) == 1

[bin sun]

So the code should be:

d=[1*40 matrix];

c=[40*40 matrix];

I=intvar(1,40);  

pos=binvar(1,40);  

f=-sum(I);

F=[implies(pos,I== 0)]; 

F=F+[sum(pos)==18];     % according to your second reply, do you mean I force too many zeros? so not 40-2, but 20-2?

F=F+[pos(1:2:39) + pos(2:2:40) == 1];

F=F+[(c*(I.^2)')./d' <= 1];

sol=optimize(F,f);

I=value(I)   

pos=value(pos)

But MATLAB still say that it is unbounded.

Thank you very much for your time to reply.

[bin sun]

Oh. I understand this part. These constraints can't be use together.

What I mean about this part of code is that nearby two can only choose one. So 1 and 2 can't choose together, but maybe none of them choose. Could you tell me how to write constraints like this?

[Johan Löfberg]

From you constraint [pos(1:2:39) + pos(2:2:40) == 1] is trivially holds that sum(pos)=20. How do you figure there could be anything else?

The problem is not unbounded but infeasible (of course, according to above), which you see if you try to solve without any objective

[Johan Löfberg]

so they should sum to less than or equal to 1.

[bin sun]

Ok. Thank you very much. I understand this part now. But this code can only get sum(pos)=20. what I want is sum(pos) could be any value like 18 or 15. 

Like I choose 15 positions from 40 available, but nearby two can only choose one.

I am trying to write code like this:

d=[1*40 matrix];

c=[40*40 matrix];

I=intvar(1,40);  

pos=binvar(1,40);  

f=-sum(I);

F=[implies(pos(1),I(1) == 0 && pos(2)=0), implies(pos(2),I(2) == 0 && pos(1)=0), implies(pos(3),I(3) == 0 && pos(4)=0), implies(pos(4),I(4) == 0 && pos(3)=0), implies(pos(5),I(5) == 0 && pos(6)=0)]; 

F=F+[implies(pos(6),I(6) == 0 && pos(5)=0), implies(pos(7),I(7) == 0 && pos(8)=0), implies(pos(8),I(8) == 0 && pos(7)=0), implies(pos(9),I(9) == 0 && pos(10)=0), implies(pos(10),I(10) == 0 && pos(9)=0)];

do you think this will be work?

[bin sun]

If I use [pos(1:2:39) + pos(2:2:40) <= 1] I can't decide how many I want to choose, right? like I want to choose 15 positions from 40 available, but nearby two can only choose one.

[Johan Löfberg]

 I choose 15 positions from 40 available

So sum(pos) == 15

but nearby two can only choose one.

Depends on what you mean by nearby. It looks like you mean pairs when partioned, which we already showed is

pos(1:2:39) + pos(2:2:40) == 1

I have no idea why you starting to mix the different logics now

[Johan Löfberg]

You introduce constraint for every logical constraint. Don't try to combine them.

 [pos(1:2:39) + pos(2:2:40) <= 1]  says that at most 1 of every partioned pair is non-zero

[Johan Löfberg]

it's probably want you want

[bin sun]

Thank you so much for your patient reply. My mistake to combine the logic together. Have a perfect day.

Best Regards,

Bin

[bin sun]

Dear Johan,

One last question,

If I want to write something like:

F=F+[pos(2)+pos(4)+pos(6)+pos(8)+pos(10)+pos(12)+pos(14)+pos(16)+pos(18)+pos(20)+pos(22)+pos(24)+pos(26)+pos(28)+pos(30)+pos(32)+pos(34)+pos(36)+pos(38)+pos(40)==9];

How should I write? I tried sum(pos(2:2:40))==9 is not ok.

Thank you very much,

Bin

[Johan Löfberg]

that's exactly what you should write, i.e it is equivalent

[Johan Löfberg]

you have to add explicit bounds on I. as it is now, yalmip will add the bounds -1e4 <=I <=1e4 to make a big-m model

you will have to play with solver algorithmic settings to see if anything improves

[bin sun]

Oh, Thank you very much. I will add [0<=I<=350].

About "play with solver algorithmic settings", you mean I need to use some other methods? like genetic algorithm. Or you mean I can use yalmip setting options to speed it up?

[Johan Löfberg]

all the various options your solver has 

[bin sun]

Oh. Thank you so much. So this part I should go to Gurobi’s website to study the detail about them.

Will you happen to know how to speed it up if I am using Gurobi? I am a new to optimization. I will learn more harder.

Thank you very much for your help.

Thank you very much,

Best Regards,

Bin

[Johan Löfberg]

there is no single trick.

https://yalmip.github.io/slowmilp/