[Scip] Numerical troubles with a set partitioning formulation
Stefan Heinz
heinz at zib.de
Fri Dec 16 22:24:05 MET 2011
Hi Sebastian,
it is hard to judge where the numerical problems come from. If you put
the attached MIP into SCIP, like you did into CPLEX, it get also solved
without any numerical problems.
One thing you could try is to change the LP solver. You could try SoPlex.
Besides that you need to get a feeling where these numerical issues come
from. Therefore, you could do:
1) turn on the debug messages in lp.c by adding
#define SCIP_DEBUG
at top of the file and recompile SCIP. That will result in a lot of
output but it should be possible to find the place where the numerical
issues arise.
2) use a debugger and stop the run at a line in lp.c where LPERROR
occurs and try the find out why SCIP thing the LP has numerical problem.
At such a point you could also dump the LP file and dopple check it with
CPLEX.
Good luck
Stefan
On 12/15/2011 02:04 PM, 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
More information about the Scip
mailing list