[SCIP] Issue with tolerance
Oliver Zier
ozier at MPA-Garching.MPG.DE
Fri Mar 13 09:14:29 CET 2020
Hi,
I saw in the mailing list that SCIP stops the LP solver once primal bound
is reached
so I tried to turn this feature off with lp/disablecutoff but SCIP will
still go to
Farkas again. Is there a way to force it to ignore the bound and go to
redcost?
I read a bit more and implemented Farkas in my program. Since the objective
coefficient does not affect my redcost pricer objective function, my Farkas
objective function is the same as redcost but uses SCIPgetDualfarkasLinear
instead
of SCIPgetDualsolLinear if I understand things correctly. However, the
columns added
by my Farkas pricing does not seem to affect the MP somehow. I doublecheck
the
objective values of subproblems using SCIPgetVarFarkasCoef and they look
correct but
in the next iteration the same columns appear again and Farkas multipliers
do not
change. Could this be because of symmetry as most of the duals are 0? But
I think
even if this is the case, the multipliers should not stay the same, aren't
they? Do
you know what I could look further into?
Thank you for your patience.
Best,
Oliver
> Hi,
>
> Thank you for your reply. SCIPlpiIsOptimal returns 0 which is not optimal
> I think.
> I am using a heuristic to add more columns to the model in scip_farkas and
> exporting
> the LP file using SCIPwriteTransProblem I checked again the LP optimal
> solution from
> scip and it is actually higher than the primal bound (current primal bound
> is
> 41.0857 but it is not optimal yet). But I thought that in this case it
> would try to
> run scip_redcost again? Can I use SCIPlpiGetInternalStatus to detect these
> cases? I
> can't find any documentation about the internal status.
> Here is the log I got from lpinfo
>
> CPXPARAM_Simplex_DGradient 2
> CPXPARAM_Simplex_PGradient 2
> CPXPARAM_Read_Scale 1
> CPXPARAM_Simplex_Tolerances_Feasibility 1.0000000000000001e-05
> CPXPARAM_TimeLimit 6987.626158
> CPXPARAM_Barrier_ConvergeTol 1e-10
> CPXPARAM_Simplex_DGradient 2
> CPXPARAM_Simplex_PGradient 2
> CPXPARAM_Read_Scale 1
> CPXPARAM_Simplex_Tolerances_Feasibility 1.0000000000000001e-05
> CPXPARAM_TimeLimit 6987.6253960000004
> CPXPARAM_Barrier_ConvergeTol 1e-10
> CPXPARAM_Simplex_DGradient 2
> CPXPARAM_Simplex_PGradient 2
> CPXPARAM_Read_Scale 1
> CPXPARAM_Simplex_Tolerances_Feasibility 1.0000000000000001e-05
> CPXPARAM_TimeLimit 6987.6248720000003
> CPXPARAM_Barrier_ConvergeTol 1e-10
> Reinitializing dual norms . . .
>
> Iteration log . . .
> Iteration: 1 Scaled dual infeas = 0.000000
> Iteration: 2 Dual objective = -979.591133
> Markowitz threshold set to 0.1
> Iteration: 24 Dual objective = 50.110505
> Removing shift (1).
> CPXPARAM_Simplex_DGradient 2
> CPXPARAM_Simplex_PGradient 2
> CPXPARAM_Read_Scale 1
> CPXPARAM_Simplex_Tolerances_Feasibility 1.0000000000000001e-05
> CPXPARAM_TimeLimit 6987.6225100000001
> CPXPARAM_Barrier_ConvergeTol 1e-10
> Initializing dual steep norms . . .
>
>
> In case if there is no way to force scip to start redcost again with my
> heuristic
> solution, I have been looking at the Farkas pricing. In the documentation,
> it is
> said that "PRICERFARKAS callback would call this function with a zero
> objective
> function and the Farkas vector" but shouldn't we try to maximize the
> Farkas vector
> and cut off if this is <= 0? I tried to implement Farkas with the max obj
> function
> but it doesn't seem to resolve the issue so I think my understanding of
> this is
> wrong.
>
> Best,
> Oliver
>
>
>
>> Dear Oliver,
>>
>> it's really hard to say what is happening without more details. In
>> general, the solving process in CPLEX when solving the LP within SCIP
>> can be different to when running CPLEX alone, because within SCIP, CPLEX
>> will restart from the basis of the last LP / LP at the parent node,
>> tolerances might be different, some settings (presolving and scaling)
>> might be different and so forth.
>>
>>
>>> I am using SCIPlpiIsOptimal and SCIPlpiGetInternalStatus to check the
>>> LP
>>> solver status when SCIP returns infeasible and I got sometimes
>>>
>>> for SCIPlpiIsOptimal and 1566399830 for SCIPlpiGetInternalStatus.
>>> What
>>> is
>>> SCIPlpiGetInternalStatus?
>>
>> SCIPlpiGetInternalStatus is the internal status code that the LP solver
>> returned. What do you sometimes get for SCIPlpiIsoptimal? Is the LP
>> really infeasible or was the cutoff bound reached, i.e., the LP was was
>> above the primal bound, if you already found a solution? This is of
>> course different to a stand-alone solve of the LP with CPLEX.
>>
>>
>>> I am turning off these plugin in SCIP
>>>
>>> SCIP_CALL( SCIPsetIntParam(scip,"presolving/maxrestarts",0) );
>>> SCIP_CALL( SCIPsetIntParam(scip,"propagating/rootredcost/freq",-1)
>>> );
>>> SCIP_CALL( SCIPsetIntParam(scip, "propagating/maxroundsroot", 0) );
>>> SCIP_CALL( SCIPsetIntParam(scip, "separating/maxroundsroot", 0) );
>>> SCIP_CALL( SCIPsetIntParam(scip, "separating/maxrounds", 0) );
>>> SCIP_CALL( SCIPsetIntParam(scip, "presolving/maxrounds", 0) );
>>> Is it enough or should I turn off something else? It would be great if
>>> you
>>> give me some idea how to debug this as CPLEX Studio returns an optimal
>>> solution so I don't really have any idea what I should check? Thank you
>>> in
>>> advance
>>
>> That should be ok. In general, if you problem is numerically
>> challenging, it may happen that you get different results with slightly
>> different starting conditions or paramters. You could check the Farkas
>> coefficients within PRICERFARKAS (which you will need to implement,
>> anyway), which should give you a linear combination of the constraints
>> that prove the infeasibility. So you might be able to verify the
>> infeasibility or see whether the combination of constraints is perhaps
>> slightly infeasible, so that you could claim both results within
>> tolerances.
>>
>> By the way: How did you write the problem to an LP file?
>>
>> I would not turn off the primal and dual feasibility checks. They should
>> make SCIP numerically more stable, because an LP solution that does not
>> pass these checks is not accepted, but the LP is optimized again with
>> different settings.
>>
>> By the way, to get some more info of what is happening within CPLEX, you
>> might want to set display/lpinfo to TRUE and send the output to the list
>> if it is not too long.
>>
>> Best,
>> Gerald
>>
>>
>>>
>>> Best,
>>>
>>> Oliver
>>>
>>>
>>>> Hi all,
>>>>
>>>> I am implementing branch and price using SCIP with Cplex as the LP
>>>> solver.
>>>> During pricing, I saw some instances in which SCIP returns that the
>>>> problem is infeasible and enters Farkas. However when I exported the
>>>> problem to an lp file and solved it with CPLEX studio, I got a
>>>> feasible
>>>> solution. I guessed this is because of tolerance so I was playing
>>>> around
>>>> with it but I can't find any numbers that work for all. I have some
>>>> constraints with big M in model. Do you have any suggestions about
>>>> what
>>>> I
>>>> should pay attention to? I am currently using
>>>> SCIP_CALL( SCIPsetRealParam(scip, "numerics/feastol", 1e-5) );
>>>> SCIP_CALL( SCIPsetRealParam(scip, "numerics/lpfeastol", 1e-6) );
>>>> SCIP_CALL( SCIPsetRealParam(scip, "numerics/dualfeastol", 1e-5) );
>>>> Also I tried to turn off lp/checkprimfeas and lp/checkdualfeas and it
>>>> helps in some cases but I am not sure if it would cause any other
>>>> issue.
>>>> Would you recommend to use the feasibility check or not in this case?
>>>>
>>>> Best wishes,
>>>> Oliver
>>>>
>>>>
>>>>
>>>> _______________________________________________
>>>> Scip mailing list
>>>> Scip at zib.de
>>>> https://listserv.zib.de/mailman/listinfo/scip
>>>>
>>>
>>> _______________________________________________
>>> Scip mailing list
>>> Scip at zib.de
>>> https://listserv.zib.de/mailman/listinfo/scip
>>
>
>
> _______________________________________________
> Scip mailing list
> Scip at zib.de
> https://listserv.zib.de/mailman/listinfo/scip
>
More information about the Scip
mailing list