Page 1 of 1

Multiplying binary variables

Posted: Mon Jun 04, 2018 5:00 pm
by jan_gh
Hi all! I'm new with Gams, I thing that problem is easy to solve. Could you please help me?

1) I try to avoid to multiply binary variables. But if I'm doing so and using the MINLP solver, the results are not binary anymore. How can that be? So the equations are met, but the binary variables are integer in the results.

2) Can you please give me a hint with the following mathematical problem?

a) I have a binary matrix b(i,j) where i and j are alias.
b) Whenever b(i,j) =1 , a(i,t) should also be 1, but for both alias

sets i, t ; alias (i,j);
Binary Variables b(i,j), a(i,t);

eq(i,j).. b(i,j) =e= sum(t, a(i,t) * a(j,t));

In the results I have the problem from 1), that all the binary variables are not binary anymore (0.22 or something between 0 and 1). Is there a possibility to avoid using the MINLP?

Thank you very much!

Re: Multiplying binary variables

Posted: Tue Jun 05, 2018 12:46 am
by cladelpino
Hi:

My intuition is that your problem can be written as a MIP, but I wasn't able to understand the logic.
Whenever b(i,j) =1 , a(i,t) should also be 1, but for both alias
Are you saying that

b(i,j) = 1 if and only if a(i,t) = 1 for all t
b(i,j) = 1 if and only if a(t,j) = 1 for all t

?

If you could formalize your constraint a bit I am sure somebody can help you.

The part I don't get about your formulation is: it is obvious that

Code: Select all

sum(t, a(i,t) * a(j,t));
will be (in feasible integer solutions) an integer between 0 and card(t). b(i,j) being declared as binary, this may be why the solver is "forcing" this constraint into feasibility by relaxing integer tolerances.

How do you feel this algebraic constraint represents your logical constraint ? It may help us understand it.

Best
Claudio

Re: Multiplying binary variables

Posted: Wed Jun 06, 2018 9:48 am
by jan_gh
Hi Claudio, thank you very much for your reply! I'm sorry for not exactly described the problem, I will clarify.

I have <b(i,j)> which is a (nxn) binary variable, whereas <j> is an alias of <i>. Then I have <a(i,t)> which is a (nxm) binary variable.

I want to set, that whenever <b(i,j)> is 1, <a(i,t)> and <a(j,t) should be 1 as well. So it's very much the same what you described. The problem is, how I take <t> into account, since only for the right <i> and <j>, <t> should be one.

Problem described in another way: <i> are points which should be connected among each other (so <j> describes the same points) . <t> is a characteristic of a point, e.g. colour. Whenever point <i> is connected to point <j> (Means <b(i,j)> =1), they should have the same colour <t> (means <a(i,t)> = <a(j,t)> =1) .

Actually this was my very first post in such a forum, next time I will more think about the problem describing.

Thank you for also answering the second question! So that means, that a solution solved with binary variables is not possible in this case.

Thank you!

Re: Multiplying binary variables

Posted: Wed Jun 06, 2018 2:55 pm
by cladelpino
While making out an example, I ran into the following:

What happens if

b(i1,i2) = 1
b(i2,i1) = 0

?

Re: Multiplying binary variables

Posted: Wed Jun 06, 2018 3:11 pm
by jan_gh
Point i and j will still have the same color. If points are not connected they might have the same color, only if they are connected they must have.

Circles ( like < b(i1,i2) = 1 > and < b(i2,i1)=1 > ) are even not allowed. To avoid them the constraint < b(i,j)+b(j,i) <=1 is implemented.

Thank you!

Re: Multiplying binary variables

Posted: Wed Jun 06, 2018 4:42 pm
by cladelpino
jan_gh wrote: 5 years ago Point i and j will still have the same color. If points are not connected they might have the same color, only if they are connected they must have.
So, the logical condition is

b(i,j) = 1 ==> a(i,t) = 1 for all t
b(i,j) = 1 ==> a(j,t) = 1 for all t

( Notice that this allows a(i,t) = 1 and b(i,j) = 0 )

?

Re: Multiplying binary variables

Posted: Wed Jun 06, 2018 4:45 pm
by cladelpino
I get the feeling we are misunderstanding. How does a(i,t) represent a color ? Is it like

Code: Select all

t colors /red,blue,green/
a(i,t) = 1 means that point i is colored color t ?

Re: Multiplying binary variables

Posted: Thu Jun 07, 2018 4:44 pm
by jan_gh
Hi Cladepino,

yes exactly! If a(i1,t1)= 1 , the point i1 will have the colour t1.

Colours are just used as an example. But its: t colors /1,2,3 ... T/

Best and thank you!