Problem with integer programming

[Ignacio]

Hello,

 

I have written a simplified problem of my actual problem in the file attached to this message. It is a mixed integer(binary) programming.

 

I have two questions, first of them is why I cannot solve it with gurobi (eve when I say to do so) and it is solved with the YALMIP integer branch & bound instead.

 

And the second question is why I am getting better solutions in the examples 2 and 3 that in the 4 when it does not make sense as 2 and 3 are more restricted?

 

I am pretty sure that the answer of both questions is because I am doing something wrong.

 

Thanks in advance,

Ignacio

[Johan Löfberg]

You write "I have thought to do it is with integer programming". I suspect you missed the fact that your first model already requires MILP. Your constraint on the absolute value is nonconvex and YALMIP handles that by creating a MILP model.

I get (all problems solved with gurobi)

solutions =

    0.4267    1.9207    1.9207    1.9207

[Ignacio]

Ok,

The absolute value can be removed in order to make it convex, my actual problem is not like that, I only selected the objective function and the constraint in order to have a simple example to explain my problem.
But yes, I totally missed that I was making the problem non convex.

The point of my question is the relationship between the values of the solution.

[Johan Löfberg]

But I don't get better solutions. 2,3,4 are all the same.

[Johan Löfberg]

...and I can use gurobi on all models, so clearly you have simplified the model way too much to make it relevant to your actual problem

[Ignacio]

I do not know why If I wrote:

ops=sdpsettings('solver','gurobi');

in every example, gurobi is used in the first three but in the last one it says:

Warning: Solver not applicable (gurobi)

ans =

   NaN

[Johan Löfberg]

Runs without problems here. Please show me the output from

>> which gurobi

>> yalmip('ver')

[Ignacio]

>> which gurobi

yalmip('ver')

C:\Program Files (x86)\Gurobi\win32\matlab\gurobi.mexw32

ans =

20120830

>> 

[Johan Löfberg]

Start by installing a recent version of YALMIP. I would not be surprised if your gurobi version is outdated too. What does this show

dir('C:\Program Files (x86)\Gurobi\win32\bin')

[Ignacio]

I have installed the newest versions of yalmip and gurobi and I still have the same problem.
The command:

dir('D:\Librerias\gurobi\win32\bin')

.                 GurobiJni56.dll   grbgetkey.exe     gurobi.env        

..                grb_cs.exe        grbprobe.exe      gurobi56.dll      

Gurobi56.NET.XML  grb_csw.exe       grbtune.exe       gurobi_cl.exe     

Gurobi56.NET.dll  grb_ts.exe        gurobi.bat        pysetup.bat     

And the command:

>> which gurobi

yalmip('ver')

D:\Librerias\gurobi\win32\matlab\gurobi.mexw32

ans =

20140915

[Johan Löfberg]

Show me everything displayed when you change the last call to

cons
max((A_f*e))
solvesdp(cons,max((A_f*e)),ops)

[Johan Löfberg]

Sorry, I've been using a develop version of YALMIP which had a bug.

Yes, Gurobi should not be applicable on your last problem. You have max(A*e) where both A and e are decision variables, hence, it is not MILP-representable directly without some massaging. One way is binary-continuous linearization using binmodel. Alternatively, use the implies operator to encode you different cases

implies(delta(1), e(1)==e(2)), implies(delta(2), e(1)==1.5*e(2)), implies(delta(3), e(2)==1.5*e(1)) where delta is binary and sums up to 1.

[Ignacio]

Thanks Johan, it works now.

I am getting a solution that is violating the constraints. 

How can I get a solution with no constraints violation(or lower at least) even if the objective is not as good as the value that I am getting now?

I get the following message:

Warning: max constraint violation (8.8906e-06) exceeds tolerance

Than

[Johan Löfberg]

You would have to look at the available solver options, there are options for these tolerances.

However, it could be an indication of an ill-conditioned problem. Are all your variables included in the logic stuff explicitly bounded? Otherwise the big-M relaxation will be crap.

[Ignacio]

Yes, the variables are bounded.

The actual tolerance of the max constraint violation is being exceeded, so I do not know if modifying this value  better results will be obtained.

I attached an example

Thanks again.

[Johan Löfberg]

I think you are creating something else than you want

Vector1*w is a complex vector, hence, per MATLAB syntax, abs(Vector1*w) is a scalar (the Euclidean norm of the complex vector), hence the max operator is redundant, and you are simply minimizing norm(Vector1*w)

[Johan Löfberg]

Why are you destroying readability by vectorizing w? With w a matrix, you simply have

 cons=[cons implies(delta(ii,1), [w(1,ii) == w(2,ii), etc]),
             etc]

[Johan Löfberg]

I guess you want to minimize max((Vector1*w).*conj(Vector1*w)).

Regarding options,, simply study the gurobi field (or which ever solver you are using) in the options structure from sdpsettings

http://users.isy.liu.se/johanl/yalmip/pmwiki.php?n=Commands.sdpsettings

[Ignacio]

Vector1 is actually a matrix (inappropiiate name), I want to minimize the maximum norm of the resulting vetor of multiplying (Vector1*w).

Yes, it is much easy to read if w is a matrix (it is a vector because of previous stuff)