[Scip] Numerical troubles with a set partitioning formulation

[Stefan Vigerske]

Hi,

Tobias Achterberg wrote:
 > [...]
> 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.

The estimated condition number that CPLEX computes you can also get in 
SCIP as a display column by setting
display/lpcond/active = TRUE

Stefan

>
>
> 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
>


-- 
Stefan Vigerske
Humboldt University Berlin, Numerical Mathematics
http://www.math.hu-berlin.de/~stefan