[SCIP] binary-times-linear term reformulation in quadratic consts

[Benjamin Müller]

Dear Ahmed,

during presolving SCIP tries to replace bilinear terms containing binary 
variables. E.g., one can linearize the product of a bounded continuous 
and a binary variable, or replacing products of binary variables by 
using an AND constraint.

This happens in the presolveTryAddLinearReform() function in the 
quadratic constraint handler: 
http://scip.zib.de/doc/html_devel/cons__quadratic_8c.php#a8d01446423ab326dd8fe6a2f088de671

Now, to reformulate those products SCIP uses auxiliary constraints and 
for those you can specify with the _binreforminitial _parameter if the 
LP relaxations of those constraints should be in the initial LP.

When linearizing those bilinear products you might introduce very large 
coefficients on the binary variables in the auxiliary constraints. To 
avoid those big-M constraints SCIP checks if the absolute value of the 
coefficient of the binary variable is larger than (1/feasibility 
tolerance) * binreformmaxcoef.

Hope this helps!


Best,

Benny

On 26.12.2015 23:32, Ahmed Ibrahim wrote:
> Hi SCIP community,
> I was wondering if someone can provide a precise explanation of the 
> following parameters in quadratic constraint handler:
>
>  1. _constraints/quadratic/binreformmaxcoef_
>  2. _constraints/quadratic/binreforminitial_
>
> I've read the brief explanation for these two parameters in 
> "http://scip.zib.de/doc/html/PARAMETERS.php"http://scip.zib.de/doc/html/PARAMETERS.php however 
> the explanation didn't seem completely clear for me.
>
> Regards,
> Ahmed
>
>
> _______________________________________________
> 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/pipermail/scip/attachments/20151227/e7a30180/attachment.html>