-
Notifications
You must be signed in to change notification settings - Fork 250
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
No dual solution available for constraint in LP with presolve disabled. #136
Comments
Could you please try disabling heuristics and propagation as well:
We had a similar problem where SCIP modified the problem internally and then the LP solver couldn't provide the dual solution anymore. On your example model, it is already enough to disable propagation to get the correct result. |
Hello @mattmilten, I can confirm that this fixes the problem with my small example. Unfortunately, just like with the fix that was proposed in #137, I am now getting For |
These are SCIP's default values for propagation:
Can't you call |
Here's my other example:
The output is:
Solving the same problem with Gurobi I get the same duals for For completeness, here is the original test case written for PICOS. Both primal and dual tests pass for all of CPLEX, CVXOPT, GLPK, Gurobi, MOSEK and SMCP while for my work in progress reimplementation of SCIP only the primal test passes (the old SCIP implementation did not retrieve any duals):
|
Sorry, I somehow lost track of this. Is this issue still relevant? |
Tested again on current c317270. I get the same infeasible dual solution as before. Unfortunately this is still the only reproducible example that I have; if you are having trouble debugging it I could write a couple more basic LP test cases for PICOS, which I should do eventually anyway, and see if another one breaks. |
I see, a basic LP test case would be much appreciated. |
Sorry for the delay. I did find a smaller example where duals returned are incorrect:
The output is:
SCIP claims that |
Thank you for providing such a small example for reproducing the error! |
oh so the problem in our code was that we always assumed that in the constraints representing bounds the coefficient was one? |
Yes, exactly. |
I can confirm that the small example works now, but I'm still not getting what I'm expecting with my larger test case. SCIP now returns the following duals:
CVXOPT, SMCP, GLPK, MOSEK and ECOS all produce the following duals (up to signs of near-zeros):
My test puts these values into the dual problem, and concludes that the dual solution given by SCIP is indeed infeasible. EDIT: I have yet to extract the constraints from the test case such that the same output as above is produced when fed to SCIP directly. This is not so easy because the test case uses a higher level representation of the problem. I'll add a script when I have one. |
OK, have this fancy script:
Right now the output is:
|
ok so the problem is to compute the dual multiplier of a constraint of the form l <= a x <= u, where l, u, and are real numbers, assuming a >0, and x is just a single variable, at an optimal solution If the reduced cost of the variable x is c > 0, then x must be at its lower bound. The reduced cost should measure the change in the objective when changing by 1 the lower bound of x, while the dual multiplier of a constraint should measure the change in the objective by changing in 1 the active side of the constraint. So, the lower bound is actually l/a <= x and the reduced costs measure the change when the bound is l/a - 1. So, if the reduced cost is c > 0, then c/a should be the change in the objective when the side changes. Let us apply it to the example above:
So, the code should also divide by the absolute value of val when computing the dual multiplier from the reduced cost. However, @mattmilten, I think there is a deeper problem. If a constraint appears many times, we will compute the same dual multiplier for the constraint, but this is wrong. So I guess we can't really fix this at the scip nor pyscipopt level, right? |
I don't have a proof or clear argument that the dual value produced by other solvers for c5 is the unique correct value (it does not help that the dual problem used by the test case is just a dual), but dividing SCIP's -4 by an absolute value alone won't yield a positive 2, so maybe another operation is necessary? |
i think that is no problem, because you are printing minus the value, right?
…On Wed, Sep 12, 2018, 19:08 Viech ***@***.***> wrote:
I don't have a proof or clear argument that the dual value produced by
other solvers for c5 is the unique correct value (it does not help that the
dual problem used by the test case is just *a* dual), but dividing SCIP's
-4 by an *absolute* value alone won't yield a positive 2, so maybe
another operation is necessary?
—
You are receiving this because you modified the open/close state.
Reply to this email directly, view it on GitHub
<#136 (comment)>,
or mute the thread
<https://github.com/notifications/unsubscribe-auth/AFNG9ocV3Lk6_-eMRFR5LKgAC62MN1tbks5uaU2RgaJpZM4StH5j>
.
|
The other solver's values are also brought into a form where they pose a solution to PICOS' dual problem formulation, i.e. they are also negated if necessary (in particular if the primal objective was maximize). In any case, if 1 and 2 are indeed the only correct duals for c3 and c5 (modulo negation), then your values of -2 and 4 (as SCIP outputs them before I negate them) will not both become positive (resp. negative) by dividing each by some absolute value, and thus remain incorrect. Again, I wish I had a smaller example that I fully understand and where uniqueness is clear. Maybe @gsagnol can shed some light on the test case as he must have been the original author. Since |
Up to a change of variables, the dual problem asks to find the largest So, to check if the dual solution is unique, we need to identify the face of the polytope with vertices +/- ai where c/14 lies. The solution is unique iff this face is a simplex (i.e., if it has 5 vertices). By looking at the solution, we see that it works with the 5 vertices {-a1,a2,-a4,a6,a7}, but we must make sure that we cannot express c/14 as a convex combination of other vertices. |
Although this is not a solution, I just added a note to the README to avoid bound constraints when dual values are desired. |
On PICOS end, I introduced support levels:
So SCIP won't be automatically selected for LPs unless duals are disabled by the user (and even less so for other conic problems were it does not return duals at all). Once this is fixed, it'll take precedence over the fallback solver again. |
@mattmilten may I ask if this is an ongoing issue with the latest version (apparently it is still the case). is it only affect single variable bound constraints? i.e. something like 0 <= x+y <= 1 should be ok? thanks |
As far as I know, not much has changed in this regard. Sorry! |
@mattmilten thanks for the reply, may I say that as long as we don't use bound constraints (i.e. we make sure we have at least 2 variable in each constraint), we should be fine? or you think there is still a bit of risk having wrong dual value? |
I assume you should be good as long as you don't have bound constraints in your problem. |
@mattmilten thanks, may I ask if this (wrong dual value for bound constraint) is an issue with scip or the linear solver (soplex) itself? so that I know if using the soplex (c++) directly would be an option. thank you very much! |
This is really an issue with how SCIP works. SCIP relies completely on the LP solver for dual values. It's definitely better to the LP solver directly for working with dual values. |
@mattmilten got you, thank you very much! |
Just to be sure, this needs to be fixed in SCIP, not PySCIPOpt? |
In the readme there are some recommendations to get correct dual values. Does that not work? I know it is annoying because of the "no bound constraints" condition. For sure, a clean implementation of this should be done in SCIP and not in PySCIPOpt. However, I don't think this is going to get fixed. |
This does not solve the inherent issue, but if we create a variable
At least the script yields matches for all cases when it does not without the y variable. This workaround also solved an issue I was having with my own code. @Viech, does this solve your issue? |
That's a good catch! I will keep this in mind as a workaround for when I find some time to revisit solver implementations. Though, on PySCIPOpt's end, I suggest to return |
I'm having issues with LP duals (with presolve disabled). Some constraints yield the correct duals, other constraints in the same problem and during the same optimization pass throw
no dual solution available for constraint
warnings. Setting the affected dual values to0.0
is not correct; some of the affected constraints are supposed to have non-zero duals.Unfortunately my example where some duals of tight constraints are returned while some are not is too involved for a bug report. However, here is an example with a single constraint where retrieving its dual fails even though the constraint is tight (and its dual value should be
1.0
):Output on
v1.2.0
:Output on current f5956e0:
Python is
3.6.4
, scipoptsuite is5.0.1
.The text was updated successfully, but these errors were encountered: