[SCIP] advice sought on solving strategy

[Matthias Walter]

Dear James,

I agree with everything Marc said and would like to add:

1. If for some e in E most most of the subsets of e are also in E then 
(after adding the missing ones) you can get quite strong bounds using 
inequalities as described here: https://arxiv.org/abs/2405.09727

2. The functionality implemented in SCIP by means of the separator 
sepa_multilinear detects such structures and adds additional 
inequalities in order to strengthen the LP relaxation. However, nothing 
special regarding propagation is done.

3. Your described strategy sounds as if you'd like to do column 
generation, too, i.e., price in columns corresponding to some e in E. 
I'm not aware of such a type of approach, but that could be interesting, 
maybe in combination with 1.

Regarding propagation: I'm not sure how well propagation works if some 
variables are missing (or, technically, if some constraints are 
modifiable). But I guess that preprocessing techniques are still applied 
if they are applicable. Then, in your pricing plugin you should be able 
to see fixed variables in order to adapt your set E accordingly.

Best,
Matthias

On 21.11.24 15:53, Marc Pfetsch wrote:
>
>
> 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
> _______________________________________________
> Scip mailing list
> Scip at zib.de
> https://listserv.zib.de/mailman/listinfo/scip