Getting feasible solutions from the MIP solver

[Nikola Besinovic]

Dear all,

I am new to YALMIP toolbox. I have managed to set up a few simple MIP models, so the work is going in the positive direction. I have tried out CPLEX and gurobi as solvers so far, and since I cannot set the CPLEX parameters (cause Im using an older CPLEX version, v12.2) I have continued with Gurobi. The problems I am solving are relatively small, so I get optimal or nearly optimal solutions (where MIPgap < 2%) within tens of seconds. 

Now I have a question. Once I get the optimal solution, I would also like to get a certain number of feasible solutions computed during the optimization. Is this possible? If yes, then how to get these out?

Thanks a lot in advance.

Best regards,

Nikola

[Johan Löfberg]

There is no way to get multiple solutions directly

The only approach is to resolve the problem with a constraint that you are not interested in a particular solution (i.e., the last optimal solution)

 A = randn(30,15);
  b = 25*rand(30,1);
  c = randn(15,1);
  x = binvar(15,1);
  Model = A*x <= b;
  sol = optimize(Model,c'*x);
  while sol.problem == 0
     Model = [Model, exclude(x,value(x))];
     sol = optimize(Model,c'*x);
  end

[Nikola Besinovic]

Dear Johan,

Thanks a lot for the prompt reply. 

I really appreciate it. 

Ok, I'll try that. 

Best,

Nikola

[Morgan]

Dear Johan,

I have met the exact same question as Nikola, and I have tried your solution.

It seems that this solution works not so well, after a few iterations, my Matlab throws out an error like below:

And all my .m file and data sheet have been uploaded (include the exclude.m in my Matlab library).
BTW, the version of my Matlab is 2017a, is there any possible that this problem has something to do with the version? Thanks a lot in advance.
Best regards,Morgan

[Johan Löfberg]

First, double is obsolete. The function is called value now.

The only way I can see this to happen is that the solver has returned error code 0, but still returns NaN in the solution. Hence you have to tell us more about which solver you are using, and what happened in the last succesful run.

It runs without issues here returning 8 solutions

[Johan Löfberg]

I can reproduce this with bnb (it returns a non-integer solution due to some bug). Hence, my guess is that you haven't installed a real MILP solver.

[Morgan]

Sorry about being late and thanks again for your thoroughly explanation.

I've also tried function value, which didn't work either. 

The solver I use called LPSOLVE and I saw it on the list of MILP on this site: https://yalmip.github.io/allsolvers/.

Actually I don't have a successful run during the time when I tried to get all the feasible solutions.

The use case I uploaded only came up with 5 feasible solutions as below:

But if I add the objective in the optimize function like this:And I'll get the only optimal solution correctly as below:

[Johan Löfberg]

If lpsolve only leads to 5 solutions  then lpsolve has a bug. There are nine feasible solution, and one of them has objective 21.99. Install a better MILP solver such as gurobi or mosek, possibly scip.

Your display says you are using intlinprog though, so your claim that you use lpsolve is confusing.

Feasible = [];

sol = optimize(F);
while sol.problem == 0

    Feasible=[Feasible [value(func);value(varx)]];

    F = [F, exclude(varx,round(value(varx)))];

    sol = optimize(F);

end

Feasible

Feasible =

   48.0000   30.8900   67.9000   54.9000   54.9000   59.0000   21.9900   67.9000   30.8900

         0         0    1.0000         0         0    1.0000         0    1.0000         0

         0    1.0000         0         0         0         0    1.0000         0    1.0000

         0         0         0         0         0         0         0         0         0

    1.0000         0         0    1.0000    1.0000         0         0         0         0

         0    1.0000         0         0         0         0         0    1.0000         0

         0         0         0         0         0         0         0         0         0

         0         0    1.0000         0         0         0         0         0    1.0000

         0         0         0    1.0000         0         0         0         0         0

         0         0         0         0    1.0000         0         0         0         0

[Morgan]

Er...Well, may be I misunderstood some of the tutorial I've read.

Because I only install an external solver, which is lpsolve, and I've read that if there isn't other available solvers, yalmip will automatically choose the one I installed already.

I didn't take those built-in solvers into consideration. So I double check the manual, add two lines of code:

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

ops.verbose = 0;

sol=optimize(F,func,ops);

Feasible=[];

while sol.problem == 0

     Feasible=[Feasible [value(func);value(varx)]];

     F = [F, exclude(varx,round(value(varx)))];

     sol = optimize(F);

end

Feasible

And I finally get the right solutions!!!

Thanks very very much for your kindness~

Have a good day!

Best regards,

Morgan

[Johan Löfberg]

You have intlinprog installed (comes with optimization toolbox) and it is used before lpsolve is used.

When I used intlinprog, YALMIP crashed in the exclude command, as you reported the first post. The reason is that intlinprog returned a slightly non-integer solution while claiming feasibility. That's why I added the round operator in the loop. I can not reproduce a case where I only get 5 solutions (unless you perhaps ran the code and it crashed after 5 iterations on your installation)

[Johan Löfberg]

not that you only use lpsolve in the first solve, the calls in the for-loop all use intlinprog as you don't use the options structure

[Morgan]

Oh, I see. 

I'm new to  YALMIP as well as MATLAB, just want to use the tool to solve a LP problem, so I don't know about the round operator, maybe it's similar to the pow function in the C++ library, which will produce little error when giving the result.

Anyway, thanks for your explanation!

Best regards,

Morgan

[Johan Löfberg]

round rounds to nearest integer. Solvers can return slightly non-integer solutions (within its tolerance for declaring integer), but if that value is sent to exclude, an error will be issued (as it doesn't make sense to exclude a binary variable from being, say, 0.999)