Multiplying binary variables

Problems with syntax of GAMS
Post Reply
jan_gh
User
User
Posts: 4
Joined: 1 month ago

Multiplying binary variables

Post by jan_gh » 1 month ago

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!

cladelpino
User
User
Posts: 108
Joined: 1 year ago

Re: Multiplying binary variables

Post by cladelpino » 1 month ago

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

jan_gh
User
User
Posts: 4
Joined: 1 month ago

Re: Multiplying binary variables

Post by jan_gh » 1 month ago

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!

cladelpino
User
User
Posts: 108
Joined: 1 year ago

Re: Multiplying binary variables

Post by cladelpino » 1 month ago

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

What happens if

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

?

jan_gh
User
User
Posts: 4
Joined: 1 month ago

Re: Multiplying binary variables

Post by jan_gh » 1 month 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.

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!

cladelpino
User
User
Posts: 108
Joined: 1 year ago

Re: Multiplying binary variables

Post by cladelpino » 1 month ago

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

?

cladelpino
User
User
Posts: 108
Joined: 1 year ago

Re: Multiplying binary variables

Post by cladelpino » 1 month ago

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
User
Posts: 4
Joined: 1 month ago

Re: Multiplying binary variables

Post by jan_gh » 1 month ago

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!

Post Reply