[SCIP] advice sought on solving strategy

Sat Nov 23 12:40:35 CET 2024

Hello James,

in your approach, I am not sure whether disabling dual presolving is either necessary or sufficient. If you mean presolving the problem without variable contributions of E, it is probably not sufficient (since this is just a different problem). If instead you declare the incomplete constraints modifiable, it is not necessary (since SCIP will only assume that the missing columns can be represented in the modifiable constraints). However, if this is all just a heuristic for some initial subset of variables in E, then of course there are no rules to follow. Then you could try both ways (some dual presolving should also work for modifiable constraints).

Best regards,

Dominik

> On 22. Nov 2024, at 18:49, James Cussens <james.cussens at bristol.ac.uk> wrote:
> 
> Hi Marc and Matthias,
> 
> Thanks for your advice and pointers to relevant literature.
> 
> I think the way I presented my problem detracted from the main issue. I do have two sets of variables Q and E where the variables in E are products of those in
> Q (actually the products also include negations of the variables in Q, sorry I forgot to mention that). But I don't actually need the Q variables (they are convenient but I can get by without them). So let's put the problem more simply:
> 
> I have an exponentially large set (E) of variables. Since E is large I will have to resort to pricing, in general. I want to add variables in an initial subset of E prior to solving the first LP using constraints provided by the user, where these constraints (in combination) will fix some of the variables in this initial subset of E to 0 (so no need to create the variable). How best to do that? Note that sometimes it will be possible to deduce that an optimal solution is possible just using this initial subset of variables (so no need for pricing) and sometimes not (so we use pricing later).
> 
> Since I posted my question I've realised that the following should work: (1) copy the problem with just Q variables (and constraints on those variables), (2) presolve that copied problem (3) use any variable fixings thus produced in the copied problem to fix variables in the main problem and (4) use those fixings to help speed up addition of the initial E variables (and any later pricing). I think as long as I disable "dual" propagations in the copied problem this should be OK.
> 
> James
> 
> PS. Btw here's how I am linking Q and E variables, where all are binary. Suppose there were only two variables x and y in Q. Then in E we have 4 variables z1,z2,z3,z4 representing xy, x(1-y), (1-x)y and (1-x)(1-y), respectively. The linking constraints are: x = z1+z2 and y = z1+x3. We also have z1+z2+z3+z4=1. In non-toy problems all these constraints are modifiable, of course. SCIP can still do some propagation even with modifiable constraints (good work SCIP people!) if they are the right sort of constraint. To this end x=z1+z2 is actually posted as 2 set partitioning constraints: ~x+z1+z2=1 and x+z3+x4=1. Once we have a variable fixed to 1 in a set partitioning constraint then we (i.e. SCIP) can fix all the other variables to 0 irrespective of whether it's a modifiable constraint or not.
> 
> 
> 
> James Cussens
> Room MVB 3.26
> School of Computer Science, University of Bristol
> Phone: +44 (0)117 455 8723
> https://jcussens.github.io/From: Scip <scip-bounces at zib.de> on behalf of Matthias Walter <matthias at matthiaswalter.org>
> Sent: 21 November 2024 23:03
> To: scip at zib.de <scip at zib.de>
> Subject: Re: [SCIP] advice sought on solving strategy
>  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
> 
> _______________________________________________
> 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