[SCIP] Linearization of product of two variables

[Stefan Vigerske]

Hi,

most basically, it would introduce a new variable for each product and 
then under- and overestimate it with linear cutting planes (McCormick: 
https://optimization.cbe.cornell.edu/index.php?title=McCormick_envelopes). 
These depend on the bounds on x and y, so to close the gap introduced by 
estimating the product, SCIP may choose to branch on some x or y. The 
reduced domain in the children means that tighter cutting planes can be 
generated.
But then there are additional techniques, in particular RLT, that aim to 
deal with these nonlinearities.

For an overview on the MINLP capabilities in SCIP, see 
https://arxiv.org/abs/2301.00587
<self-promotion>The slides from 
https://www.gams.com/~svigerske/2023_minlp.pdf may also be useful, in 
particular the example from page 80 (slide 25) on.</self-promotion>

Stefan

On 09/07/2023 14:06, Abbas Omidi wrote:
> Dear support team,
> 
> I am working on an MINLP model that in one of the constraints contains a
> non-linear term as follows:
> 
> (\sum_{i} x_{i,j}*y_{j} \leq b_{j};    \forall j \in J)
> 
> where, the variable x[i,j] is an integer with a positive domain and the
> variable y[j] is a positive variable. I would like to know how SCIP can
> deal with this non-linear term? and how it would be linearized by SCIP?
> 
> 
> Thanks in advance
> Regards
> Abbas
> 
> 
> _______________________________________________
> Scip mailing list
> Scip at zib.de
> https://listserv.zib.de/mailman/listinfo/scip