[Scip] Numerical troubles with a set partitioning formulation

Tobias Achterberg achterberg at zib.de
Fri Mar 23 09:11:32 MET 2012 

The solution quality looks very good, and the condition number of the optimal basis matrix 
is small. So, CPLEX does not seem to have any trouble solving this model in the 
interactive shell. I have no clue what is going on. In particular I find it strange that 
you get the "infeasibilities after unscaling" status even after disabling scaling.

Do you have ranged constraints (i.e., lhs <= a*x <= rhs with both finite lhs and rhs) in 
your model?


Tobias


Sebastian Ruther wrote:
> yes, I've tried the usual: cost perturbation, set cover instead of set partitioning
> constraints, also instead of set cover constraints use linear constraints of type 0.99999
> <= Ax <= Inf, and moving constraints around to change the A matrix. But none of it worked.
>
> I attached the cplex log file for when using 'opt' and, in case you would like to see that
> output as well, also ran it with the simplex method that was called when the .sav file was
> generated. In this case the dual simplex.
>
> Nick suggested to use different tolerances. I don't get any numerical issues if I set
> numerics/dualfeastol to 1e-7
> or
> numerics/feastol to 1e-5.
> At least I don't get any within 1h of running time.
>
>
> Sebastian
>
> On 9/03/2012 8:06 PM, Tobias Achterberg wrote:
>> Is there any hope that you can improve the numerics in your model?
>>
>> If you load the .sav file into the CPLEX interactive shell, and then enter
>>
>> disp prob stat
>> opt
>> disp sol qual
>>
>> what is the output?
>>
>>
>> Tobias
>>
>>
>> Sebastian Ruther wrote:
>>> Hello,
>>>
>>>
>>> I'm still stuck with these numerical issues.
>>> I've noted that at some point it will attempt to solve using "primal simplex without
>>> scaling". That most often works but fails in the end as well. Again CPLEX returns
>>> solstat=5, i.e. "Optimal solution is available, but with infeasibilities after unscaling."
>>> Why is it allowed to do scaling? I thought that was disabled in this run?
>>>
>>> I tried SCIPsetBoolParam(scip, "lp/scaling", FALSE)); to (hopefully) turn off scaling
>>> altogether. This time it will first solve without scaling, which still returns CPLEX
>>> solstat=5. SCIP then resolves using scaling... to no avail.
>>>
>>> I tried to set SCIPsetBoolParam(scip, "lp/checkfeas", FALSE)); in the hope that it will
>>> ignore numerical issues and just use the dual information if available. Several times it
>>> will set *lperror = TRUE; in function lpSolveStable() before exiting the function but then
>>> continue generating columns so I assume it uses the dual information it has. However, at
>>> some point it will say
>>> (node 1) unresolved numerical troubles in LP 314 -- using pseudo solution instead (loop 1)
>>> it then goes into ObjBranchGE::scip_execps.
>>> but I'm not presenting any pseudo solution so the node terminates here. I guess I can't
>>> really trust that this is indeed the last iteration at the node?
>>>
>>> Any help on this is appreciated at this point.
>>> Thanks
>>> Sebastian
>>>
>>>
>>>
>>>
>>>
>>> On 24/02/2012 5:28 PM, Sebastian Ruther wrote:
>>>> I use the correct .prm and .sav file and use the appropriate solving method. It solves
>>>> fine, without any numerical issues.
>>>> ...
>>>> Iteration: 4869 Dual objective = 138933.305623
>>>> Iteration: 4955 Dual objective = 138983.170753
>>>> Removing perturbation.
>>>> Iteration: 4976 Dual infeasibility = 0.000000
>>>> Iteration: 5003 Dual objective = 138984.598896
>>>> Removing shift (15).
>>>> Iteration: 5056 Dual infeasibility = 0.000000
>>>> Iteration: 5073 Dual objective = 138984.598896
>>>>
>>>> Maximum reduced-cost infeasibility = 1.12095e-009.
>>>>
>>>> Dual simplex - Optimal: Objective = 1.3898459890e+005
>>>> Solution time = 2.61 sec. Iterations = 5108 (44)
>>>>
>>>> The objective value is the same as reported by the last attempted solves by SCIP/CPLEX.
>>>>
>>>> The attached file is the relevant part of the SCIP/CPLEX output. It has all LP solves
>>>> before exiting.
>>>>
>>>> In the SCIP log it says CPLEX returned solstat=5, pfeas=1, dfeas=1.
>>>> A solstat of 5 is
>>>> CPX_STAT_OPTIMAL_INFEAS
>>>> "Optimal solution is available, but with infeasibilities after unscaling"
>>>>
>>>> Coefficients in the A matrix are -1,0,1, rhs: 1, 0, and 1-24 (convexity constraints),
>>>> cost coefficient: 5000 for artificial variables, 0 - 1000 for columns.
>>>>
>>>> Is there any way I can still use the solution?
>>>>
>>>> Thanks,
>>>> Sebastian
>>>>
>>>>
>>>>
>>>>
>>>>
>>>> On 24/02/2012 7:04 AM, Tobias Achterberg wrote:
>>>>> The use of the primal really comes from SCIP calling CPXprimopt(), so your test to call
>>>>> "primopt" from the CPLEX interactive is correct.
>>>>>
>>>>> Did you use the .sav file format for writing out your problem? This would be the only
>>>>> one that could save the exact state.
>>>>>
>>>>> The 1017 parameter is indeed the FASTMIP parameter. It just disappeared from the CPLEX
>>>>> docs, but its numerical value did not change.
>>>>>
>>>>> So, I think everything should be as in SCIP if you load in the parameters and the .sav
>>>>> file, and you call the appropriate optimizer method.
>>>>>
>>>>> Tobias
>>>>>
>>>>>
>>>>> Sebastian Ruther wrote:
>>>>>> Hello,
>>>>>>
>>>>>> yeah that was pretty embarrassing. Ok, it now works and I'll have a look
>>>>>> at it.
>>>>>>
>>>>>> I also tried what Tobias suggested, i.e. use
>>>>>>
>>>>>> CPXwriteprob and CPXwriteparam when an LP has numerical issues to reproduce these in
>>>>>> CPLEX.The output of CPXwriteparam is something like:
>>>>>>
>>>>>> CPLEX Parameter File Version 12.3.0.0
>>>>>> CPX_PARAM_DPRIIND 2
>>>>>> CPX_PARAM_EPOPT 1.00000000000000e-09
>>>>>> 1017 1
>>>>>> CPX_PARAM_ITLIM 10000
>>>>>> ...
>>>>>>
>>>>>> a quick search reveals that in CPLEX 9.0 parameter 1017 was used for
>>>>>> CPX_PARAM_FASTMIP. In newer versions of CPLEX this doesn't seem to exist
>>>>>> anymore - at least I can't find such a parameter in the manual.
>>>>>>
>>>>>> Reading this .prm file into CPLEX fails. I can let SCIP run a bit longer
>>>>>> and it tries several settings that all return numerical issues. At some
>>>>>> point SCIP doesn't tell CPLEX to use fastmip. I then load CPLEX with the
>>>>>> .prm and .sav file and optimize. It doesn't have any numerical issues
>>>>>> but I don't think it uses the exact parameters it uses under SCIP. For
>>>>>> example it uses the barrier method though SCIP was using the primal
>>>>>> simplex when I was printing the 2 files. CPXwriteparam writes all non
>>>>>> default parameters. Is it possible that the CPLEX default values are
>>>>>> different when using the terminal compared to as a callable library? If
>>>>>> so, is there any way to get the complete set of parameters?
>>>>>> Yes, I tried using 'primopt' instead of 'optimize'. Also no numerical
>>>>>> issues. But again, this may not be the only parameter that was not set
>>>>>> accordingly.
>>>>>>
>>>>>> Thanks
>>>>>> Sebastian
>>>>>>
>>>>>>
>>>>>> On 23/02/2012 7:12 PM, Gerald Gamrath wrote:
>>>>>>> Hi Sebastian,
>>>>>>>
>>>>>>> in order to activate the debugging output, you should define SCIP_DEBUG
>>>>>>> in the file for which you want to have the information, so in your case
>>>>>>> lp.c. You have to do this right at the beginning of the file, e.g.,
>>>>>>> before the header files are included. This way, SCIP_DEBUG is defined
>>>>>>> when message.h is included and debugging messages will be printed.
>>>>>>>
>>>>>>> Best,
>>>>>>> Gerald
>>>>>>>
>>>>>>>
>>>>>>> Am 23.02.2012 07:51, schrieb Sebastian Ruther:
>>>>>>>> Hello,
>>>>>>>>
>>>>>>>> I enable #define SCIP_DEBUG in lp.c. However, that doesn't print
>>>>>>>> anything because in pub_message.h SCIP_DEBUG is not defined and so
>>>>>>>> we get #define SCIPdebugPrintf while( FALSE ) printf.
>>>>>>>> Therefore I define SCIP_DEBUG in pub_message.h. However, then I get
>>>>>>>> compilation errors for
>>>>>>>> sepa_zerohalf.c(1498): error C2143: syntax error : missing ';' before 'type'
>>>>>>>> the offending term is the
>>>>>>>> int i;
>>>>>>>> just after the function header of debugPrintLPRowsAndCols().
>>>>>>>>
>>>>>>>>
>>>>>>>> I figured the SCIP_DEBUG from pub_message.h gets included in some other
>>>>>>>> file and we don't really want that so I don't define #define SCIP_DEBUG
>>>>>>>> in pub_message.h but just comment in a way such that I have
>>>>>>>>
>>>>>>>> /** executes command only if SCIP_DEBUG flag is set */
>>>>>>>> #define SCIPdebug(x) x
>>>>>>>>
>>>>>>>> /** prints a debugging message if SCIP_DEBUG flag is set */
>>>>>>>> #define SCIPdebugMessage printf("[%s:%d] debug: ",
>>>>>>>> __FILE__, __LINE__); printf
>>>>>>>>
>>>>>>>> /** executes printf command only if SCIP_DEBUG flag is set */
>>>>>>>> #define SCIPdebugPrintf printf
>>>>>>>>
>>>>>>>> I then get these 2 compilation errors
>>>>>>>> cons_bivariate.c(2962): error C2065: 'paramnames' : undeclared identifier
>>>>>>>> cons_varbound.c(2291): error C2198: 'SCIPprintCons' : too few arguments
>>>>>>>> for call
>>>>>>>>
>>>>>>>> when I comment out these lines I get linkage errors.
>>>>>>>>
>>>>>>>> The problem here is the #define SCIPdebug(x) x
>>>>>>>> if I use
>>>>>>>> #define SCIPdebug(x) /**/
>>>>>>>> I get output although I don't know how helpful that is since it is not
>>>>>>>> really debugging....
>>>>>>>>
>>>>>>>> Regards,
>>>>>>>> Sebastian
>>>>>>>>
>>>>>>>> On 12/01/2012 2:48 AM, Tobias Achterberg wrote:
>>>>>>>>> Hi Sebastian,
>>>>>>>>>
>>>>>>>>> in order to analyze what is going on, I would do the following:
>>>>>>>>>
>>>>>>>>> First, you can activate the LP solver logging by setting the
>>>>>>>>> "display/lpinfo" to TRUE.
>>>>>>>>>
>>>>>>>>> Then, use gdb and set a breakpoint at the end of lp.c:lpSolveStable
>>>>>>>>> where the message about unresolved numerical trouble is printed (or,
>>>>>>>>> alternatively, where the first "solve again" message is displayed).
>>>>>>>>>
>>>>>>>>> Then save the CPLEX LP into a *.sav file by calling
>>>>>>>>> CPXwriteprob(lp->lpi->cpxenv, lp->lpi->cpxlp, "nodelp.sav", 0)
>>>>>>>>> and save the current CPLEX parameters with
>>>>>>>>> CPXwriteparam(lp->lpi->cpxenv, "nodelp.prm")
>>>>>>>>>
>>>>>>>>> Now, if you load in these parameters and this *.sav file into the
>>>>>>>>> CPLEX interactive, you should be able to generate exactly the same log
>>>>>>>>> output as the one displayed from SCIP due to the "display/lpinfo"
>>>>>>>>> parameter. And you should get the same numerical trouble...
>>>>>>>>>
>>>>>>>>> Finally, you can use CPLEX to analyze the source of the numerical
>>>>>>>>> issue. For example, use "display solution quality" inthe CPLEX
>>>>>>>>> interactive to print statistics about the primal and dual feasibility
>>>>>>>>> and the condition number of the final LP basis.
>>>>>>>>>
>>>>>>>>>
>>>>>>>>> Tobias
>>>>>>>>>
>>>>>>>>>
>>>>>>>>> Sebastian Ruther wrote:
>>>>>>>>>> Hello,
>>>>>>>>>>
>>>>>>>>>> I've had numerical troubles with larger instances for a long time. So
>>>>>>>>>> far I've been able
>>>>>>>>>> to ignore them because I mostly dealt with smaller instances but I
>>>>>>>>>> now have to resolve
>>>>>>>>>> this issue.
>>>>>>>>>>
>>>>>>>>>>
>>>>>>>>>> I'm running SCIP 2.1 with CPLEX 12.3 on Windows 7. I've coded a
>>>>>>>>>> branch-and-price algorithm
>>>>>>>>>> with a pure set partitioning master LP. All coefficients are
>>>>>>>>>> integral, the objective
>>>>>>>>>> function coefficients are either 5000 (artificial variables) or
>>>>>>>>>> ranging from 400 to 1000
>>>>>>>>>> for some columns but most of them have a cost of 0. (I don't think
>>>>>>>>>> this is the issue
>>>>>>>>>> though - in earlier versions these columns did have non-zero cost and
>>>>>>>>>> I still had
>>>>>>>>>> numerical troubles). All variables are binary.
>>>>>>>>>>
>>>>>>>>>> The numerical troubles happen throughout the algorithm, but SCIP is
>>>>>>>>>> usually able to
>>>>>>>>>> recover using different tolerances, methods, etc. This can take up a
>>>>>>>>>> lot of time though.
>>>>>>>>>> However, at some point it is not able to recover and will try for
>>>>>>>>>> ObjBranchGE::scip_execps. Since I don't give it any additional
>>>>>>>>>> columns there it then will
>>>>>>>>>> finish the node. Please see the output below.
>>>>>>>>>> I dumped the Lp using SCIPwriteLP. CPLEX solves this without any
>>>>>>>>>> issues but of course it
>>>>>>>>>> may use methods that SCIP isn't allowed to use because it knows that
>>>>>>>>>> variables may not
>>>>>>>>>> have been added yet. I've attached the .lp file. This is the Lp at
>>>>>>>>>> the end of the root
>>>>>>>>>> node (or I should say it aborts the root node at this point).
>>>>>>>>>>
>>>>>>>>>> The output is:
>>>>>>>>>>
>>>>>>>>>> (node 1) numerical troubles in LP 297 -- solve again with primal
>>>>>>>>>> simplex without scaling
>>>>>>>>>> (node 1) numerical troubles in LP 298 -- solve again with primal
>>>>>>>>>> simplex without presolving
>>>>>>>>>> (node 1) numerical troubles in LP 299 -- solve again with primal
>>>>>>>>>> simplex with tighter
>>>>>>>>>> feasibility tolerance
>>>>>>>>>> (node 1) numerical troubles in LP 300 -- solve again from scratch
>>>>>>>>>> with primal simplex
>>>>>>>>>> (node 1) numerical troubles in LP 301 -- solve again from scratch
>>>>>>>>>> with dual simplex
>>>>>>>>>> (node 1) numerical troubles in LP 302 -- solve again from scratch
>>>>>>>>>> with dual simplex
>>>>>>>>>> without scaling
>>>>>>>>>> (node 1) numerical troubles in LP 303 -- solve again from scratch
>>>>>>>>>> with dual simplex
>>>>>>>>>> without presolving
>>>>>>>>>> (node 1) numerical troubles in LP 304 -- solve again from scratch
>>>>>>>>>> with dual simplex with
>>>>>>>>>> tighter feasibility tolerance
>>>>>>>>>> (node 1) unresolved numerical troubles in LP 305
>>>>>>>>>> (node 1) numerical troubles in LP 306 -- solve again with dual
>>>>>>>>>> simplex without scaling
>>>>>>>>>> (node 1) numerical troubles in LP 307 -- solve again with dual
>>>>>>>>>> simplex without presolving
>>>>>>>>>> (node 1) numerical troubles in LP 308 -- solve again with dual
>>>>>>>>>> simplex with tighter
>>>>>>>>>> feasibility tolerance
>>>>>>>>>> (node 1) numerical troubles in LP 309 -- solve again from scratch
>>>>>>>>>> with dual simplex
>>>>>>>>>> (node 1) numerical troubles in LP 310 -- solve again from scratch
>>>>>>>>>> with primal simplex
>>>>>>>>>> (node 1) numerical troubles in LP 311 -- solve again from scratch
>>>>>>>>>> with primal simplex
>>>>>>>>>> without scaling
>>>>>>>>>> (node 1) numerical troubles in LP 312 -- solve again from scratch
>>>>>>>>>> with primal simplex
>>>>>>>>>> without presolving
>>>>>>>>>> (node 1) numerical troubles in LP 313 -- solve again from scratch
>>>>>>>>>> with primal simplex with
>>>>>>>>>> tighter feasibility tolerance
>>>>>>>>>> (node 1) unresolved numerical troubles in LP 314
>>>>>>>>>> 256s| 1 | 0 |313683 | - | 14M| 0 | - |4373 |1057 |4373 |1057 | 0 | 0
>>>>>>>>>> | 0 | --
>>>>>>>>>> |2.620000e+006 |
>>>>>>>>>> 256s| 1 | 0 |313683 | - | 14M| 0 | - |4373 |1057 |4373 |1057 | 0 | 0
>>>>>>>>>> | 0 | --
>>>>>>>>>> |2.620000e+006 |
>>>>>>>>>> (node 1) unresolved numerical troubles in LP 314 -- using pseudo
>>>>>>>>>> solution instead (loop 1)
>>>>>>>>>> it then goes into ObjBranchGE::scip_execps.
>>>>>>>>>>
>>>>>>>>>> I use the following to generate the constraints:
>>>>>>>>>>
>>>>>>>>>> set partitioning constraints
>>>>>>>>>> SCIP_CALL( SCIPcreateConsSetpart(
>>>>>>>>>> scip,
>>>>>>>>>> &cons,
>>>>>>>>>> namebuf.str().c_str(), //name
>>>>>>>>>> 0, //nvars
>>>>>>>>>> 0, //vars
>>>>>>>>>> InitMPconsInitial,
>>>>>>>>>> InitMPconsSeparate,
>>>>>>>>>> InitMPconsEnforce,
>>>>>>>>>> InitMPconsCheck,
>>>>>>>>>> InitMPconsPropagate,
>>>>>>>>>> InitMPconsLocal,
>>>>>>>>>> InitMPconsModifiable,
>>>>>>>>>> InitMPconsDynamic ,
>>>>>>>>>> InitMPconsRemovable,
>>>>>>>>>> InitMPconsStickingatnode) );
>>>>>>>>>>
>>>>>>>>>> convexity constraints:
>>>>>>>>>> SCIP_CALL( SCIPcreateConsSetpack(
>>>>>>>>>> scip,
>>>>>>>>>> &cons,
>>>>>>>>>> namebuf.str().c_str(), //name
>>>>>>>>>> 0, //nvars
>>>>>>>>>> 0, //vars
>>>>>>>>>> InitMPconsInitial,
>>>>>>>>>> InitMPconsSeparate,
>>>>>>>>>> InitMPconsEnforce,
>>>>>>>>>> InitMPconsCheck,
>>>>>>>>>> InitMPconsPropagate,
>>>>>>>>>> InitMPconsLocal,
>>>>>>>>>> InitMPconsModifiable,
>>>>>>>>>> InitMPconsDynamic ,
>>>>>>>>>> InitMPconsRemovable,
>>>>>>>>>> InitMPconsStickingatnode) );
>>>>>>>>>>
>>>>>>>>>> with
>>>>>>>>>> #define InitMPconsInitial true
>>>>>>>>>> #define InitMPconsSeparate false
>>>>>>>>>> #define InitMPconsEnforce true
>>>>>>>>>> #define InitMPconsCheck true
>>>>>>>>>> #define InitMPconsPropagate true
>>>>>>>>>> #define InitMPconsLocal false
>>>>>>>>>> #define InitMPconsModifiable true
>>>>>>>>>> #define InitMPconsDynamic false
>>>>>>>>>> #define InitMPconsRemovable false
>>>>>>>>>> #define InitMPconsStickingatnode false
>>>>>>>>>>
>>>>>>>>>>
>>>>>>>>>> Any ideas what I can do? I mean the formulation is very basic and I
>>>>>>>>>> don't think the
>>>>>>>>>> coefficients are too large.
>>>>>>>>>> Thank you!
>>>>>>>>>> Sebastian
>>>>>>>>>>
>>>>>>>>>>
>>>>>>>>>>
>>>>>>>>>> _______________________________________________
>>>>>>>>>> Scip mailing list
>>>>>>>>>> Scip at zib.de
>>>>>>>>>> http://listserv.zib.de/mailman/listinfo/scip
>>>>>>>>> .
>>>>>>>>>
>>>>>>>> _______________________________________________
>>>>>>>> Scip mailing list
>>>>>>>> Scip at zib.de
>>>>>>>> http://listserv.zib.de/mailman/listinfo/scip
>>>>>>> _______________________________________________
>>>>>>> Scip mailing list
>>>>>>> Scip at zib.de
>>>>>>> http://listserv.zib.de/mailman/listinfo/scip
>>>>>>>
>>>>>>> .
>>>>>>>
>>>>>>
>>>>>> _______________________________________________
>>>>>> Scip mailing list
>>>>>> Scip at zib.de
>>>>>> http://listserv.zib.de/mailman/listinfo/scip
>>>>>
>>>>> .
>>>>>
>>
>> .
>>

More information about the Scip mailing list