conditional assignment

[moati]

Hi,

Suppose I have 8 binary variables y1 up to y8 whose values depend on another 8 binary variables x1 up to x8.

For example if x1...x8 = 10010010 then y1...y8 can be one of {00110011, 0100110110, 01100110,....}

How can we model this conditional assignment?

Thanks,

[Daniel Espinoza]

If you really have up to 8 such `bits`, then you can binary encoding of the strings and use general constraints as follows:

define z0 as binary variable and z1 as integer variable and for each possible value of y1-y8, define wi as binary variable  and vi the binary expansion, then

regular constraints:

c0: x1 + 2x2 + 4 x3 + 8 x4 + 16 x5 + 32 x6 + 64 x7 + 128 x8  + z1 = 1 + 8 + 64

c1: z1 <=  255 * (1-z0)

c2: z1 >= -255 * (1-z0)

c3: sum wi = 1

indicator constraints:

g1: z0 = 1 -> y1 + 2y2 + 4y3 + 8y4 + 16y5 + 32y6 +64y7 +128y8 = sum wi * vi

In theory you can always do that trick (i.e. is a correct reformulation)... but the numerics will start to suffer at some point (for sure for 32 bits, but probably much earlier)

[moati]

I'm so sorry but I kind of lost you so can you give more details about your answer.

For example, what is the objective of each constraint? In c0, why the RHS is 1 + 8 +64? Also, when you say sum wi, what does this mean?

Thanks,

[Daniel Espinoza]

Hi Moati

When I say a `binary expansion` of a bit sequence `b_1b_2b_3b_4b_5b_6b_7b_8`, where b_i can be either 0-1, I mean

1 * b_1 + 2 * b_2 + 4 * b_3 + 8 * b_4 + 16 * b_5 + 32 * b_6 + 64 * b_7 + 128 * b_8

this is a number with values in {0,....,255} and every single bit sequence correspond to one such number and each number correspond to one bit sequence. So, the number is `representing` a unique joint encoding for all bits.

I hope this helps,

Best

Daniel

[moati]

Hi again,

It does help, thanks a lot.

What if the x1 up to x8 takes multiple values and each value corresponds to a different set of values for the Ys.

Thanks,

[moati]

What about the following:

We assign zi binary variables and ui binary expansions for the possible input values and then wj, vj for the output.

The constraints will be:

sum zi = 1
x1 + 2 x2 + 4 x3 + 8 x4 + 16 x5 + 32 x6 + 64 x7 + 128 x8 = sum zi * ui
sum wj = zj
y1 + 2 y2 + 4 y3 + 8 y4 + 16 y5 + 32 y6 + 64 y7 + 128 y8 = sum wj * vj

That should work, correct?

To complicate things more, what if the transition ij has a cost cij and the sum of the costs is my objective function which I would like to minimize!

How can I include the costs in the above equations?

Thanks

[Daniel Espinoza]

Hi Moati,

It seems right... now, if you also want to keep track of the transitions and states, you can define binary variables zi and wj and transition variables tij

and then setup network constraints zi = sum tij:j and wj = sum tij:i.

The binary expansion is only to map bits patterns with binary variables bi... why do you need these patterns?

Also, an alternative (with more equations, but might be tighter as a relaxation) would be to say

xk = sum zi *bit_ki :i  for k =1.. 8

and do the same for yk

[moati]

Well, the previous model was not correct!

I had to change the last constraint to: zi * (y1 + 2 y2 + 4 y3 + 8 y4 + 16 y5 + 32 y6 + 64 y7 + 128 y8) = sum wj * vj

which turned my constraints to quadratic constraints! Didn't test the impact on my (big) models yet!!

Any idea on how to turn them to linear constraints again?

Then, frankly speaking I did not get how to incorporate the transition costs can you give more concrete examples?

Thanks a lot for your help, much appreciated.