Multiplying binary variables

GAMS
1

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!

2

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

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

3

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 is an alias of . 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 into account, since only for the right and , should be one.

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

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

What happens if

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

?

5

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!

6

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 )

?

7

I get the feeling we are misunderstanding. How does a(i,t) represent a color ? Is it like

t colors /red,blue,green/

a(i,t) = 1 means that point i is colored color t ?

8

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!