[SCIP] Issue with tolerance
Mueller, Benjamin
benjamin.mueller at zib.de
Fri Mar 27 07:59:12 CET 2020
Hi Oliver,
if you add a column with negative reduced costs, then your multipliers
need to change in the next iteration. This should hold independent of
existing symmetries. I would guess that the column that you generate
doesn't have negative reduced costs, so there might be an issue in the
pricing problem that you solve or with how you add the coefficients of
the newly generated column. Are there upper bounds on variables that you
have forgotten to take into account in your pricing problem? How large
are the reduced costs of your generated column?
Can you maybe write out the transformed problem (as *.cip) before and
after you have added the column and send me those two files? Thank you!
Best,
Benjamin
On 13.03.20 09:14, Oliver Zier wrote:
> 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
>>
>
> _______________________________________________
> Scip mailing list
> Scip at zib.de
> https://listserv.zib.de/mailman/listinfo/scip
More information about the Scip
mailing list