-
-
Notifications
You must be signed in to change notification settings - Fork 5k
New issue
Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.
By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.
Already on GitHub? Sign in to your account
A numerical bug in scipy.optimize.linprog #12954
Comments
Interesting. I confirmed that this still happens in the latest version of SciPy. Revised simplex solves this one if you reduce the tolerance:
I'll try to check whether gh-12043 fixes it at some point. |
Note that in the example case here, as written,
a solution is obtained in Scipy 1.5.2. But maybe the property holds close to FP precision in the real example case. The report above says version 1.2.1 was used --- it would be useful to know if the problem still occurs in newer versions, given that IIRC fixes to the redundancy handling were done since then. |
Even the HiGHS solvers are reporting infeasibility on this one. @jajhall @mckib2 thought you might be interested in this.
Yes, I think it does still occur, and the new RR methods in gh-11249 don't fare any better. I can't dig much deeper right now. |
@mdhaber: did you correct for the rounding error in the ref/matA matrices as typed --- it works for me if that's done? Or, is the problem expected to be feasible even if this is not done? |
Well, ideally it would solve the problem even if that's not done, because even with the matrix as typed, the @mn-on-github's But you're right, this seems to be a tolerance issue, because when you correct the rounding error as described, redundancy removal kicks in and the problem is solved successfully. One thought for a while has been to expose the redundancy detection tolerance as an option. That might help here. |
I'd be interested in looking at this problem. Do you have it as a .lp or .mps file? |
@jajhall I can make an MPS file later this evening for HiGHS testing |
@jajhall Here is an MPS file generated for the above file. HiGHS reports infeasible but I'm not sure if tolerances could be adjusted to resolve it as above. |
I appreciate for quick replies @mdhaber @jajhall. It is interesting to see that the analysis is going in a decentralized way by people living in a different region. The Earth is indeed round.
|
Thanks, but this LP is infeasible, and not marginally so, as all columns are fixed at zero, and the constraints are equations with nonzero RHS [and nonzero coefficients]. If the columns are allowed to be [0, inf] then it's still infeasible. With free columns HiGHS finds an optimal (ie feasible) solution. Perhaps with more digits the optimal basis matrix is closer to being singular, and that causes trouble, but there's no issue with the 6-digit coefficients. @mn-on-github @pv @mckib2 @mdhaber |
@jajhall @pv Reproducing code:
Now I get a SATisfiable assignment successfully in this case and some other similar cases. Message:
Thanks to this, I got peace of mind and I resumed combining scipy to my main algo and re-testing further. (But I am caught by a different assertion error in my algo...) It would take some time until I verify other cases having a larger matrix size which even IPOPT sometimes fails. Q. I set an assertion to the constraint violations for validating an output x from scipy. In this case, the final search iterate stopped at a point x = array([0.70514251, 0.10725385...]) where constraint violations is larger than it should be supposedly; con = array([-1.69741633, -0.25037501,...]). I don't use simplex method because this property does not hold when the LP is infeasible. p.s. |
Re:global convergence, please see here for the algorithm on which the interior point implementation is based. Re: constraint violations larger than they should be, can you post that example? You can close the issue, and GitHub will allow you to reopen if need be. |
Good morning? I learned MOSEK is inside scipy.linprog and included in GAMS solver library.. Two good properties of an interior point method using a variety of penalty/barrier functions is that (1) it can start from an initially infeasible point and that (2) drives the search iterate x toward a final point where KKT conditions hold. The property (2) drives x toward minimizing primal feasibility of equality constraints and max|| {(A_eq*x-vec_b}_i || decreases even the LP is infeasible (and go to 0 if feasible). Perhaps I may be addicted with a particular primal-dual IP, but I expect that the small constraint violation || residual || = O(9.9293934e-7) in the original post where residual = [-9.9293934e-07, -5.2687482e-07, ...] means that an actual satisfiable assignment is close to the final search iterate ans_x = [0.04934082, 0, 0, 0.00702774...] with a bound || matA_inans_x-veb_in || <O(9.9293934e-7)~=O(1e-6). So I can judge a precise satisfiable assignment is near ans_x within a small bound inv(A_eq)(1e-6...1e-6) (abusively using!) Eventually, ans_x1 = [0.04934082244280857, 0, 0, 0.00702774001205814...]) is close to the original ans_x. But I got an error message from scipy with a final search iterate x = [0.70514251, 0.10725385...] that is nowhere close to a potential satisfiable assignment in a sense that the constraint violations con = matA_in*x-vecb_in = [-1.69741633, -0.25037501, ...] and max|| con[i] ||= 2.57498303 is not small at all. This motivated me to post here. |
The next one is this. I am not abusively using scipy.optimize.linprog, but... Reproducing code example:
scipy.optimize.linprog reports the following UNSAT decision. Error message:
Scipy/Numpy/Python version information:The same as the original environment.
Is this UNSAT decision due to a conservative filtering at presolve step, perhaps? |
Yes, it's presolve. I'm not sure why it's erroneously detecting infeasibility; that tolerance is actually pretty loose. I can't dig into it right now, but if you turn presolve off it solves (despite warnings). |
@mdhaber Then I will continue with presolve disabled. I know well that haste debugging of a numerical algorithm often ends up in adding a new bug. |
The third one is this. scipy.linprog reports [ValueError] and my algo stalled. Reproducing code example:
scipy.optimize.linprog reports the following broken report. Error message:
@mdhaber |
You are still using 1.2? I get:
The branch of the code this goes into was created based on observed behavior of the simplex method. There is a condition after the solver terminates:
Apparently, it occurs for all three methods on this problem, not just simplex.
but it has a relatively loose tolerance of 0.00031622776601683794 (np.sqrt(1e-9) * 10). Since all three solvers - and actually both of the HiGHS solvers - conclude that the problem is infeasible ( The tolerance it uses to check feasibility has been tuned over time, but mostly to check for a different case - when the solver reports an optimal solution that turns to be infeasible. I suppose we could use a different tolerance for this case so you get a more conclusive result, but choosing the perfect level for infeasibility edge-cases like this is tricky. So perhaps the best thing to do here would be to clarify the output message. The solution returned is not likely to be "nearly optimal", though, at least not for the simplex solvers, since they didn't even make it into phase 2. Maybe I should mention that, too? Suggestions? |
@jajhall My apologies, I generated the wrong MPS file for the problem described. The bounds should not be fixed -- they should be upper bounded. This was due to a bug in the bounds processing for scikit-glpk that was recently corrected. I'll upload the corrected MPS file although it still turns out to be infeasible. |
Thanks: I did actually try that fix, and recall that the LP needs some negative values to be feasible. Interesting problems - I've never seen them before. |
Indeed, it's hard, but it's one of the goals of HiGHS! Thanks for your recent near-feasible LP. I've not seen your class of LP before. If the LP is classed as infeasible, are you still interested in the "best" point that the solver can find, or just the statement of infeasibility [to within the tolerance used]? I'm developing the HiGHS solvers and am keen to understand what users want. Currently in HiGHS, if an LP is found to be infeasible, no point is returned. This is because the main solver is dual simplex, so identifies primal infeasibility as a consequence of dual unboundedness. There is an associated (primal) solution, but it isn't "best" in any clear sense. However, it has an interior point (IPM) solver [that I didn't write] that should identify a "best" infeasible (primal) point, and I'm currently developing a primal simplex solver that will also determine a "best" infeasible (primal) point, so these could be returned. Note that "best" is not the same in the two cases. Sorry if this is something you're aware of (or TMI), but the IPM solver yields a point that is feasible with respect to bounds on variables, but will have minimized the constraint violations. [I get the impression that this is what you're after.] For an LP with n variables and m constraints, primal simplex yields a point for which n of the variable and constraints will satisfy their bounds, but (up to) m will be violated in a sense that is minimal, but not so clear. Neither solution method will find a point for which violations of variable and constraint bounds are minimized - arguably the "best" solution to the problem. In passing, I see that you've had problems with presolve declaring infeasibility incorrectly. Apparently this is due to an equation being identified as being linearly dependent on other rows, but inconsistent. Given your matrix coefficients, I can see that this could be difficult to asses, due to inexact arithmetic. I guess that this presolve technique is used to make life easier for an IMP solver. However, the HiGHS presolve is designed as a precursor to a simplex solver - that isn't troubled by near-deficient equations - so the presolve doesn't try to identify them. It would seem as if the HiGHS IMP solver isn't troubled by them, either. This is interesting, and something that I'll check up on. The HiGHS IPM solver has some unusual features that make it particularly reliable and accurate. If you're looking for a reliable IPM solver for your problems, HiGHS might well be what you need. [It's got a direct Python interface.] Julian |
@mdhaber As column vectors of matA_in are linearly dependent, I want to test satisfiability of the bound constraint 0-1e-5<ans_x[i]<=1+1e-5 while keeping |matA_in*ans_x-vecb_in|<1e-12 (strictly satisfied). @jajhall Although I cannot explain anything about my specific algo that generates the particular matA, I can elaborate many applications that root in the single motivation.
a) Formal verification of a numerical program, A generalized setting is known as model checking. For this I use NLP solver. b) A component of a general-purpose satisfiability solver c) (traditional AI) scheduling problem d) reasoning/estimation problem e) fault handling procedure f) model-based estimation problem
I wrote too much.. but I hope these fascinate developers/readers of this lengthy thread. |
Oops, maybe it was a development version I was testing with? Maybe we changed that? New release will come out later this year, I think. Under the hood there are only two kinds of constraints, equality and non-negativity, so you can't independently adjust tolerances on bounds vs inequality in the existing interface. That said, linprog is not, by default, very smart about problem scale, so you might be able to get the effect you want by rescaling things. Maybe try reducing the upper bounds on decision variables by a few orders of magnitude and multiplying your constraint matrix coefficients by the same factor? It also might be worthwhile for you to install a development version of the code so you can modify it. |
You would also be able to use HiGHS through it without changing your code. We added HiGHS simplex and IPM as |
I switched to HiGHS-1.0 (C++ API) and it does not fail in the cases that I reported above. Now the matA grows up >5 rows*800 columns. Excellent! (though nobody know if I could report a bug next month...) I appreciate for @mdhaber, @pv @jajhall and @mckib2 for these fast, sincere and interactive debugging. |
Thanks. Sorry the existing |
Hi. I appreciate for contributors to scipy and extended communities. I learned the history of scipy on wikipedia and confirmed why this library is one of the highest quality OSS.
But unfortunately, I found apparently a bug in scipy.optimize.linprog. As I run the following test.py, the LP solver incorrectly reports that LP is infeasible.
Reproducing code example:
Error message:
scipy.optimize.linprog reports the following UNSAT decision.
Scipy/Numpy/Python version information:
Here is a version info. Perhaps little bit old?
Can you reproduce this? I don't have much time to look into the implementation of this library, but
I can generate "MANY" similar class of incorrect reports having the same property orz.
A special property of ref and matA is that all row vectors satisfies the following constraint;
[1,1,1,1,1,-1].ref=0
[1,1,1,1,1,-1].matA[i]=0, for any i, 0<=i<9
Here ref and matA[i] are on the same hyper-plane which share the same normal vector [1,1,1,1,1,-1].
So my initial guess is that the bug might result from inadequately solving a matrix equation.
If a constraint matrix matA is rank-deficient. A matrix inversion could break a solution to
Given_matrix*vecX=Given_vecB. In Eigen3 which I use, there are three QR decompositions with such
rank-deficiency in mind.
eigen.tuxfamily.org/dox/classEigen_1_1FullPivHouseholderQR.html
eigen.tuxfamily.org/dox/classEigen_1_1ColPivHouseholderQR.html
eigen.tuxfamily.org/dox/classEigen_1_1HouseholderQR.html
IPOPT also fails to figure out a SATsifiable assignment and instead converge incorrectly in a similar setting. But it happens less frequently than scipy.optimize.linprog showed.
Another guess is that it counld result from a difficulty of solving an LP using the current floating point arithmetic IEEE754-FP that causes a rounding-error. A similar technical issue might be in scipy.optimize.linprog/interior-point. But not for sure.
Best regards,
Masataka Nishi
The text was updated successfully, but these errors were encountered: