[SCIP] advice sought on solving strategy

[Marc Pfetsch]

Hi James,

from what I understood from email, the variables in E are products of 
multiple binary variables in Q. This is called multilinear optimization 
(or polynomial 0/1 optimization) and there is a body of work that tries 
to figure out which relaxations are good for such problems. One approach 
is to explicitly add variables for certain products and add linear 
coupling inequalities (special cases of McCormick inequalities). The 
question is which ones to choose. One example of such an approach is the 
paper by Emily Schutte and Matthias Walter

https://doi.org/10.1007/978-3-031-59835-7_29
https://arxiv.org/abs/2311.08570

As far as I know some of these techniques are already implemented in SCIP.

In general, the choice of the right products for best practical 
performance does not seem easy.

Hope this helps.

Best

Marc



On 21/11/2024 08:44, James Cussens wrote:
> Hi all,
> 
> I'm looking for some advice on how to implement a particular solving 
> strategy.
> 
> I have a problem where there are two set of (binary) variables. One set, 
> call it Q, has a quadratic number of variables, the other set,
> call it E, has an exponential number of variables. The variables in E 
> are actually products of those in Q and only variables in E
> have non-zero objective coefficient. In my current strategy all Q 
> variables and a reasonably small subset of E variables are created 
> initially and
> further E variables are priced-in later (if necessary).
> 
> In the sort of problems I'm aiming to solve, the user may well want to 
> impose constraints on the variables in Q. I would like to use these 
> constraints to
> speed up the creation of the initial set of E variables. I'm thinking of 
> an approach like this:
> 
>  1.
>     Create Q variables
>  2.
>     Read in user constraints on the Q variables, if any
>  3.
>     Propagate these constraints (perhaps with several rounds) and
>     (hopefully) produce fixings for some of the Q variables
>  4.
>     Use any fixings to speed up the creation of initial E variables.
>     (They will also be used, of course, in any future pricing.)
> 
> I'm not sure how best to implement this. I could call presolve after 
> step 2 but perhaps SCIP will just solve the problem at that point unless 
> I somehow flag
> that some E variables are on their way. I think I am looking to do 
> propagations at step 3 and nothing else.
> 
> James
> 
> James Cussens
> Room MVB 3.26
> School of Computer Science, University of Bristol
> Phone: +44 (0)117 455 8723
> https://jcussens.github.io/ <https://jcussens.github.io/>
> 
> _______________________________________________
> Scip mailing list
> Scip at zib.de
> https://listserv.zib.de/mailman/listinfo/scip