Translation between SCS status and MOI status #1
Comments
|
IIRC, the "Inaccurate" states can also occur when an iteration limit is hit, without any guarantees on the quality of the solution. This doesn't count as |
|
For if s in (-3, 1, 2)
MOI.FeasiblePointThe SCS status In elseif s in (-6, -1)
MOI.InfeasibilityCertificate
else
MOI.InfeasiblePoint
endand elseif s in (-7, -2)
MOI.InfeasibilityCertificate
else
MOI.InfeasiblePoint
endI'm not sure what the difference between these InfeasibilityCertificate and InfeasiblePoint are, but for SCS Other than that it looks right. One small note - I think it's hard to talk about the difference between feasible and nearly feasible, unless it is up to some defined tolerance. Even just solving a set of linear equations will have some numerical error, e.g. I just ran this python code: >>> import numpy as np
>>> A = np.random.randn(100, 100)
>>> b = np.random.randn(100)
>>> x = np.linalg.solve(A, b)
>>> np.linalg.norm(A.dot(x) - b)
1.2380685665598168e-12So the point |
|
|
|
@bodono, feasibility and near feasibility are all defined with respect to tolerances. A solver should call a point (primal/dual) feasible if it satisfies the pre-defined (primal/dual) feasibility tolerances. Some solvers have a second level of relaxed feasibility tolerances, so if the solution satisfies these relaxed tolerances then it can be called near feasible. |
|
@bodono Note that SCS has some trouble solving |
|
Ok, good to know. I can't find that test anywhere, can you point me to it? SCS 2.0 is an improvement (in terms of wall clock time) for most problems, but undoubtedly some will do worse. If you want you can switch back to the old behavior for that test by setting |
|
I found the test (I think) https://github.com/JuliaOpt/MathOptInterfaceSCS.jl/blob/master/test/runtests.jl#L13 I'll dig into and see what's happening. |
|
The test is here. You can execute it by replacing the line |
|
I put this into cvxpy in python (easier for me access), and SCS can solve it very easily, both SCS 1 and SCS 2, here is the code: x = cvxpy.Variable(1)
y = cvxpy.Variable(1)
objective = cvxpy.Maximize(1000 * x + 350 * y)
constraints = [x >= 30, y>=0, x - 1.5 * y >=0, 12 * x + 8 * y <= 1000, 1000*x + 300 * y <= 70000]
prob = cvxpy.Problem(objective, constraints)
prob.solve(solver='SCS', verbose=True)and the resulting output: I was cribbing from the comment in the code you linked, which suggests that SCS is getting the right answer basically # maximize 1000 x + 350 y
#
# s.t. x >= 30
# y >= 0
# x - 1.5 y >= 0
# 12 x + 8 y <= 1000
# 1000 x + 300 y <= 70000
#
# solution: (59.0909, 36.3636)
# objv: 71818.1818
#@test MOI.supportsproblem(solver, MOI.ScalarAffineFunction{Float64},
# [
# (MOI.ScalarAffineFunction{Float64},MOI.GreaterThan{Float64}),
# (MOI.ScalarAffineFunction{Float64},MOI.LessThan{Float64}),
# (MOI.SingleVariable,MOI.GreaterThan{Float64})
# ]
#)I'm not sure what the difference is, but it could be that the input layer to SCS is doing a weird problem transformation that is making it harder to solve. |
|
It's getting |
|
I am getting The output I get is and the input is (with A both in sparse and dense format) m = 5
n = 2
A = 5×2 SparseMatrixCSC{Float64,Int64} with 8 stored entries:
[2, 1] = -1.0
[3, 1] = 1.5
[4, 1] = 8.0
[5, 1] = 300.0
[1, 2] = -1.0
[3, 2] = -1.0
[4, 2] = 12.0
[5, 2] = 1000.0
A = 5×2 Array{Float64,2}:
0.0 -1.0
-1.0 0.0
1.5 -1.0
8.0 12.0
300.0 1000.0
b = [-30.0, 0.0, 0.0, 1000.0, 70000.0]
c = [-350.0, -1000.0]
f = 0
l = 5If I scale the problem to I still get the same status but I get |
|
Here is what SCS is getting from cvxpy: almost exactly the same, just with the columns of A and c flipped, which shouldn't make a difference. I'll keep investigating. |
|
Something fishy is going on, because if I manually put in the input values you have, I get the following: |
|
Ah, I found it, it's the |
|
By the way, the alpha term is just a type of overstep parameter, so the update takes a larger step by that factor and in theory it should converge for all choices of |
|
In the helper function here, it the comment it is written 1.8 but you say that the default is 1.5 and 1.8 is only used in SCS.jl. Am I missing something ? |
|
The comment is out of date, those defaults are set here. |
|
I just updated the comments. |
@bodono Could you help me determine the mapping between SCS status and MOI status ?
The termination statuses are described here and result statuses here.
It is especially not easy to determine which of SlowProgress, AlmostSuccess, NumericalError or one of the limit is the reason the solver stopped.
For the result status, it is important to distinguish between FeasiblePoint and NearlyFeasiblePoint. Even if the solution is not optimal, it could be guaranteed to be feasible. Same for infeasibility certificates.
I have a first draft here: https://github.com/JuliaOpt/MathOptInterfaceSCS.jl/blob/master/src/attributes.jl
I have done it quickly and only based it on the names of the C constants so feel free to change it completely :-P
The text was updated successfully, but these errors were encountered: