[SCIP] rounding error?

[Jakob Witzig]

Hi James,

SCIP provides the possibility to define an objective limit, i.e., 
SCIPsetObjlimit(scip, objlimit). Afterwards, SCIP only declares solution 
as feasible if they are strictly better than objlimit. To avoid 
numerical issues I would recommend that you use this method instead of 
adding a constraint that is parallel to the objective function.

Just a side remark: SCIP provides two interesting parameters if a 
constraint is parallel to the objective function (e.g., an objective limit)
1) constraints/linear/detectcutoffbound
2) constraints/linear/detectlowerbound
if one is set to TRUE, SCIP will prevent that this constraints will 
enter the LP. Both are set to TRUE per default.

Nevertheless, SCIP will propagate this constraint which may cause 
numerical issues unless you have set the 'propagate' flag to FALSE.

Cheers,
Jakob


On 12.11.2016 15:44, James Cussens wrote:
> I have written a "relaxator" which is called after the LP relaxation 
> (for the current node) has been solved.
>
> It works (well, should work) by solving a combinatorial relaxation of 
> the current problem: a subscip is created by copying some but not all 
> of the main problem's constraints. An extra constraint is then added 
> to this subscip which says that the objective value of any solution 
> cannot be better (which means lower since we are working with the 
> transformed problem) than that of the LP solution which has just been 
> found: call this the "objlimit constraint". This subscip is then solved.
>
> A problem I am having is that the objective value of the solution to 
> this subscip is almost always slightly better than is allowed by the 
> "objlimit" constraint. In some cases it is equal. Here is an example 
> of that:
>
> Here is an "objlimit" constraint (the LHS is the objective, the RHS 
> the current lower bound):
> ....
> +2233.687538<t_I#36#24>[B] +3470.976165<t_I#36#22#23#25>[B] 
> +3514.739589<t_I#36#22#25#34>[B] +3600.517959<t_I#36#22#25#26>[B] 
> +3602.888251<t_I#36#22#25>[B] +4315.968312<t_I#36#23#25#26>[B] 
> +4353.360389<t_I#36#25#26#34>[B] +4364.720055<t_I#36#25#26>[B]
> ....
> +7696.24707<t_I#36#19#27>[B] +7755.844738<t_I#36#27#32>[B] 
> +7767.597019<t_I#36#21#27>[B] +7769.766551<t_I#36#27>[B] 
> +8160.498138<t_I#36#17#28>[B] +8232.30374<t_I#36#28>[B] 
> +8344.946419<t_I#36>[B] >= 97290.4565854556;
>
> And here is a solution to my relaxed problem, containing the above 
> objlimit constraint:
>
> objective value:                         97290.443308
> t_I#0#13                                            1 (obj:575.319346)
> t_I#2                                               1 (obj:1558.283114)
> t_I#3#8#15#33                                       1 (obj:708.049421)
> ....
> t_I#36#24                                           1 (obj:2233.687538)
>
> Clearly, we illegally have a solution with obj value 97290.443308 
> which is strictly lower than  97290.4565854556
>
> Am I right in thinking that this is some sort of rounding error? Is 
> there perhaps a better way of indicating that only solutions which are 
> no better than some value are allowed? The objlimit constraint 
> contains every variable (!) so perhaps it should be no surprise that 
> there are problems.
>
> I suspect that this particular relaxator approach may not be a great 
> idea, but I would still like to get to the bottom of this phenomenon.
>
> James
>
>
> -- 
> James Cussens
> Dept of Computer Science &
> York Centre for Complex Systems Analysis
> Room 326, The Hub, Deramore Lane            Tel    +44 (0)1904 325371
> University of York  Fax  +44 (0)1904 500159
> York YO10 5GE, UK http://www.cs.york.ac.uk/~jc 
> <http://www.cs.york.ac.uk/%7Ejc>
> http://www.york.ac.uk/docs/disclaimer/email.htm
>
>
> _______________________________________________
> Scip mailing list
> Scip at zib.de
> http://listserv.zib.de/mailman/listinfo/scip

-- 
Jakob Witzig

Zuse Institute Berlin (ZIB)

Division Mathematical Optimization and Scientific Information
Research Group Mathematical Optimization Methods

Takustrasse 7
14195 Berlin

Tel. : +49 (0)30 84185-416
Fax  : +49 (0)30 84185-269
email: witzig at zib.de

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://listserv.zib.de/pipermail/scip/attachments/20161112/61d93d75/attachment.html>