MISOCP solves returning status "Unknown" (different from #100)

[chriscoey]

We also get Unknown from a large number of MISOCPs we attempt to solve. What we observe is that MOSEK gets to the time limit AND has a feasible solution, but apparently the optimality gap is not yet satisfied. Then Mosek.jl fails to handle the status properly and returns Unknown (perhaps it should be Suboptimal).

In another case where no feasible solution was found by the time limit, MOSEK finished and Mosek.jl returned (correctly) the UserLimit status. The only difference here was that no feasible solution was found, whereas in the Unknown cases, we had both upper and lower bounds.

Here is the end of a printout (the lines with ## are our printings, not MOSEK's):

1179079  1176550  335532   30       5.0076984618e+05     5.0052105644e+05     0.05        3599.5
1179105  1176576  335540   24       5.0076984618e+05     5.0052105735e+05     0.05        3599.5
1179131  1176602  335546   45       5.0076984618e+05     5.0052105779e+05     0.05        3599.6
1179157  1176628  335550   24       5.0076984618e+05     5.0052105879e+05     0.05        3599.7
1179183  1176654  335560   36       5.0076984618e+05     5.0052106168e+05     0.05        3599.8
1179209  1176680  335566   39       5.0076984618e+05     5.0052106190e+05     0.05        3599.8
1179235  1176706  335570   35       5.0076984618e+05     5.0052106307e+05     0.05        3599.9
1179261  1176732  335576   29       5.0076984618e+05     5.0052106463e+05     0.05        3600.0
Maximum amount of time 3600.00 (=dpar_optimizer_max_time) is reached.

Objective of best integer solution : 5.007698461827e+05      
Best objective bound               : 5.005210646327e+05      
Construct solution objective       : Not employed
Construct solution # roundings     : 0
User objective cut value           : 0
Number of cuts generated           : 0
Number of branches                 : 1179261
Number of relaxations solved       : 1176732
Number of interior point iterations: 21020134
Number of simplex iterations       : 0
Time spend presolving the root     : 0.00
Time spend in the heuristic        : 0.00
Time spend in the sub optimizers   : 0.00
  Time spend optimizing the root   : 0.00
Mixed integer optimizer terminated. Time: 3601.02

Optimizer terminated. Time: 3601.03 
#STATUS# Unknown
#OBJVAL# 500769.8461827041
#OBJBOUND# 500521.06463272555
#TIMESOLVER# 3601.032301902771

@mlubin @ulfworsoe

[erling-d-andersen]

There is almost surely a bug in Julia interface.

Btw getting the Julia interface to print the MOSEK solution summary after each optimization as default would help debugging so much.

[mlubin]

@ulfworsoe, looks like the fix to #89 was incomplete

[ulfworsoe]

The issue is at least partially fixed now. A feasible solution should now produce Suboptimal status.

[mlubin]

@ulfworsoe, that doesn't follow the MPB convention. If the solver stops because of a time limit, it should return :UserLimit regardless of whether it has found a primal solution so far.

[ulfworsoe]

Fair enough. The status function is a mess since it mixes Mosek's response code, problem status and solution status into one value. Do you have a description of MPB conventions somewhere?

[ulfworsoe]

Basically the relevant questions:

• Does UserLimit take precedence over an optimal solution or only a feasible one?
• Does Stall take precedence over an optimal solution or a feasible one?

[mlubin]

The statuses are currently documented at http://mathprogbasejl.readthedocs.io/en/latest/solverinterface.html#status. I agree that they could use a revamp, that's something I'm open to considering.

Does UserLimit take precedence over an optimal solution or only a feasible one?

I don't understand how the solver could terminate because of the time limit if it already has an optimal solution.

Does Stall take precedence over an optimal solution or a feasible one?

Stall is not a standard status. Error maybe?

You should consider the statuses, as they're currently defined, as an explanation of why the solver stopped. :Optimal is not really about the solution itself but more explaining that the solver stopped because it found a solution that it was happy with. @ccoffrin has pointed out that :Optimal should really be called :Success or something similar.

[mlubin]

Btw getting the Julia interface to print the MOSEK solution summary after each optimization as default would help debugging so much.

Agreed. @ulfworsoe, could we do that?

[ulfworsoe]

Done.

[mlubin]

@ulfworsoe, Mosek seems to be returning :Stall on some problems where it used to return :Optimal and is therefore failing JuMP's tests.

[ulfworsoe]

Yes. If the solver stalls and stops, but finds that the solution after post-solve happens to be optimal, it will produce an optimal solution but still return the actual reason for stopping.

[mlubin]

Fair enough

[erling-d-andersen]

Unless you are doing something special in the interface then this not correct explenation. Postsolve cannot fix a broken solution. What can happen on linear problems is that the interior-point optimizer stalls but the subsequent basis identification succeeds. 2016-12-28 9:28 GMT+01:00 Ulf Worsøe <notifications@github.com>:

…

Yes. If the solver stalls and stops, but finds that the solution after post-solve happens to be optimal, it will produce an optimal solution but still return the actual reason for stopping. — You are receiving this because you commented. Reply to this email directly, view it on GitHub <#101 (comment)>, or mute the thread <https://github.com/notifications/unsubscribe-auth/AJwCcSYDB14HHvUYIw4d7j2ALETn6G0Iks5rMh2rgaJpZM4LLcy8> .

[ulfworsoe]

That is possible.

The problem here is: It is possible that the MOSEK solver terminates with a non-ok status and produces an optimal solution anyway. In this case it is my understanding (from the above discussion) that MathProgBase.status() should return the solver response rather than the solution status if the solver response is not ok

[mlubin]

The offending test is an SDP:

using JuMP, Base.Test, Mosek
m = Model(solver=MosekSolver())
@variable(m, y)
@variable(m, z)
c = @SDconstraint(m, [0 y; z 0] <= [1 0; 0 0])
@objective(m, Max, y/2+z/2)
status = solve(m)

@test status == :Optimal
@test isapprox(getobjectivevalue(m), 0, atol=1e-5)
@test isapprox(getvalue(y), 0, atol=1e-5)
@test isapprox(getvalue(z), 0, atol=1e-5)

X = getdual(c)
@test isapprox(X[1,1], 0, atol=1e-5)
@test isapprox(X[1,2], 1/2, atol=1e-5)
@test isapprox(X[2,1], 1/2, atol=1e-5)
@test isapprox(getdual(y), 0, atol=1e-5)
@test isapprox(getdual(z), 0, atol=1e-5)

Ulf is correct that MathProgBase.status() should return the solver response. It's a bit confusing that the solver can stall and still return an optimal solution though. Why is it called a stall if the optimality tolerances are satisfied?

[erling-d-andersen]

MOSEK does things a bit differently than normal. I hope I can covince that what we do is rational. As far I understand Jump has one return code. It is used to signal optimizer failures e.g. out space, infeasibility and a lot other stuff. Well, at least that is what many codes does but MOSEK has a richer way of reporting what is going on. In MOSEK we distinguish a. Optimizer status e.g. out of space, out of time. b. Problem status. c. Solution status. So if the MIP optimizer runs because out of time but has a feasible solution, then we set Return code = E.g. ok or out of space Optimizer status = out of time (This is not failure of the system if the user set time limit) Problem status = feasible Solution status = feasible Using that method we can report any situations that appear accurately. I do not see how you can reduce it much without loosing info. In my opinion you cannot just have single number representing solver status, solution status etc. accurately. Now in http://docs.mosek.com/8.0/capi/tutorial-response.html we explain how you should deal with termination. It can be summarized as follows using pseudo code. if solution I am interested is has the right status e.g. optimal do what ever you had planned to do else /* Something went wrong */ You can for instance use the response code of the optimizer to obtain information about went wrong. Do what ever is appropriate in this case. I hope this make sense. Also given this information it should possible to map the MOSEK info. to Jump info. Feel free to explain when that is not case and why. 2016-12-29 16:14 GMT+01:00 Miles Lubin <notifications@github.com>:

…

The offending test is an SDP: using JuMP, Base.Test, Mosek m = ***@***.***(m, ***@***.***(m, z) c = @SDconstraint(m, [0 y; z 0] <= [1 0; 0 ***@***.***(m, Max, y/2+z/2) status = solve(m) @test status == ***@***.*** isapprox(getobjectivevalue(m), 0, ***@***.*** isapprox(getvalue(y), 0, ***@***.*** isapprox(getvalue(z), 0, atol=1e-5) X = ***@***.*** isapprox(X[1,1], 0, ***@***.*** isapprox(X[1,2], 1/2, ***@***.*** isapprox(X[2,1], 1/2, ***@***.*** isapprox(getdual(y), 0, ***@***.*** isapprox(getdual(z), 0, atol=1e-5) Ulf is correct that MathProgBase.status() should return the solver response. It's a bit confusing that the solver can stall and still return an optimal solution though. Why is it called a stall if the optimality tolerances are satisfied? — You are receiving this because you commented. Reply to this email directly, view it on GitHub <#101 (comment)>, or mute the thread <https://github.com/notifications/unsubscribe-auth/AJwCcbad1IKRfebQ3NRKLQcxFGGvAmIXks5rM84_gaJpZM4LLcy8> .

[mlubin]

No need to convince me, I'm already convinced that the status API in MathProgBase needs to be redone.

[ccoffrin]

I find the idea of having 4 values, i.e. return code, optimizer status, problem status, and solution status, quite interesting.

[erling-d-andersen]

I not saying we have the ideal answer. Some users thinks we overdoing it but my opinion is that solution status and optimizer status has to be separated as a minimum. On other hand you could have separate solution statuses for the primal and dual solutions. Ulf does that in Fusion. Maybe the right way to start is to think about the possible scenarios that can occur * Out of time but a with feasible solution. * Optimal * Almost optimal but stalled. [We use that in MOSEK in the interior-point optimizer.] * Out space * Out space but with a feasible solution * Certificates of infeasibility * Terminated on an objective cut. * User break with possible a feasible solution ...... Some other things to think about. Is a user break or out of time an error? Is an infeasible problem an error? Is out of space an error? My reply is: No, No, Yes. 2017-01-02 15:49 GMT+01:00 Carleton Coffrin <notifications@github.com>:

…

I find the idea of having 4 values, i.e. return code, optimizer status, problem status, and solution status, quite interesting. — You are receiving this because you commented. Reply to this email directly, view it on GitHub <#101 (comment)>, or mute the thread <https://github.com/notifications/unsubscribe-auth/AJwCcUG28SwwhumS5a_aCfmWErjaBhO7ks5rOQ5ngaJpZM4LLcy8> .

[erling-d-andersen]

Btw on the problems MOSEK fails it computes a near optimal solution. Ulf used to report them as optimal. But changed that in the interface based on what you told him so now tests fails. It might not be possible to resolve this unless you change the interface. On another note when MOSEK says near optimal on a smallish problem it might not be an ideal problem for a unit test. So the tests MOSEK starts failing on is likely to be somewhat strange in the sense it is hard to compute an optimal solution. 2017-01-02 19:41 GMT+01:00 Erling Andersen <erling@andersens.name>:

…

I not saying we have the ideal answer. Some users thinks we overdoing it but my opinion is that solution status and optimizer status has to be separated as a minimum. On other hand you could have separate solution statuses for the primal and dual solutions. Ulf does that in Fusion. Maybe the right way to start is to think about the possible scenarios that can occur * Out of time but a with feasible solution. * Optimal * Almost optimal but stalled. [We use that in MOSEK in the interior-point optimizer.] * Out space * Out space but with a feasible solution * Certificates of infeasibility * Terminated on an objective cut. * User break with possible a feasible solution ...... Some other things to think about. Is a user break or out of time an error? Is an infeasible problem an error? Is out of space an error? My reply is: No, No, Yes. 2017-01-02 15:49 GMT+01:00 Carleton Coffrin ***@***.***>: > I find the idea of having 4 values, i.e. return code, optimizer status, > problem status, and solution status, quite interesting. > > — > You are receiving this because you commented. > Reply to this email directly, view it on GitHub > <#101 (comment)>, > or mute the thread > <https://github.com/notifications/unsubscribe-auth/AJwCcUG28SwwhumS5a_aCfmWErjaBhO7ks5rOQ5ngaJpZM4LLcy8> > . >

[ulfworsoe]

Closing ancient issues.