Difference between ismember and integer

[gretzteam]

Hi,

I'm a newbie in optimization and trying to use YALMIP to solve some integer programming problem (finding quantized coefficients for an FIR filter).

I'm trying to understand the difference between using:

b = intvar(8,1);

sol = solvesdp(Constraints,Objective);

for which the solution is found in less than 10 seconds, and the values of b are all between -1024 and 1024.

Now, for the exact same problem, I tried to declare b as:

b = sdpvar(8,1);

constraint= ismember(b, [-1024:1:1024]);

for which the solver keeps running for hours. I would think that internally those two are identical problems. I'd like to understand this better as I was wanting to constrain 'b' to be from a much more restrained set and want to make sure I can trust the result...if it can't solve it with the current set above, which I know contains the best possible result, something is wrong with my understanding of 'ismember'.

Thanks!

David

[Johan Löfberg]

It represents the same things, but the models are vastly different

A model with
x = intvar(1), -1024<=x<=1024 will be communicated to a solver as a variable, with two variable bounds, constrained to be integer

x = sdpvar(1), ismember(x,-1024:1024) will generate a binary variable z=binvar(2049,1), and the constraints x == [-1024:2024]*z, sum(z)==1. If you know x is integer, you should always tell this to the solver (of course, cplex probably figures this out in the slow model anyway, but it doesn't hurt to say it explicitly).

[gretzteam]

Thanks I understand better.

Of course the use of ismember in this case is not very useful. However, as soon as I would like to constrain 'x' to be from a set of value that is not so trivial, seems like I'll run into huge run time (this problem never finished running after two days...). I was looking into set of values that require say less than 2 adders to calculate in hardware so it would look more like [1 2 3 4 5 6 7 8 9 10 12 14 15...] - (11 and 13 aren't there since they require 3 adders). Basically the set has 'wholes'.

I now wonder if 'ismember()' is the correct way to approach this, of if I should myself try to convert this into a standard constraint...

Thanks!

[Johan Löfberg]

There are numerous ways to model this, and as almost always in integer programming, you have no idea of knowing which one will work best, so try different approaches

Here is one alternative

solvesdp([1 <= x <= 15, x ~= 11, x~= 13],abs(x-11))

Note, the ~= will introduce two binaries, modelling the two cases x>=12 and x <= 10, etc.

[Johan Löfberg]

And just for fun, here is another, very contrived model (your number written as a number between 0 and 10, and if that number is 10, possibly an added even term, or simply the number 15)

intvar x
intvar y
intvar z
binvar w

solvesdp([1 <= x <= 15,
          0 <= y <= 10,
          0 <= z <= 2,
          implies(y<=9, z==0),
          x == y + 2*z+15*w],abs(x-11))

[gretzteam]

Hi,

I'm starting to understand the whole idea of converting those constraints into the integer programming context. I'm also seeing how enormous those problems might become even for what seems like a simple constraint!

Thanks for the help!

David