Multiplying binary variables

Problems with syntax of GAMS
jan_gh
User
Posts: 5
Joined: 1 year ago

Multiplying binary variables

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!

User
Posts: 108
Joined: 3 years ago

Re: Multiplying binary variables

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

?

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

jan_gh
User
Posts: 5
Joined: 1 year ago

Re: Multiplying binary variables

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!

User
Posts: 108
Joined: 3 years ago

Re: Multiplying binary variables

While making out an example, I ran into the following:

What happens if

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

?

jan_gh
User
Posts: 5
Joined: 1 year ago

Re: Multiplying binary variables

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!

User
Posts: 108
Joined: 3 years ago

Re: Multiplying binary variables

jan_gh wrote:
1 year 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 )

?

User
Posts: 108
Joined: 3 years ago

Re: Multiplying binary variables

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 ?

jan_gh
User
Posts: 5
Joined: 1 year ago