[Scip] Numerical troubles with a set partitioning formulation
Sebastian Ruther
Sebastian.Ruther at uon.edu.au
Fri Feb 24 07:28:49 MET 2012
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
>
> .
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://listserv.zib.de/mailman/private/scip/attachments/20120224/080e6939/attachment.html
-------------- next part --------------
An embedded and charset-unspecified text was scrubbed...
Name: output.log
Url: http://listserv.zib.de/mailman/private/scip/attachments/20120224/080e6939/output.ksh
More information about the Scip
mailing list