[SCIP] SCIP: Iterative presolve in-between (restricted: var-fixing only) modelling?

[Marc Pfetsch]

Hi Sascha,

you can use the "probing mode" of SCIP, which allows to perform variable 
propagations which can then easily be undone:

SCIPstartProbing()

while ! done
{
    SCIPchgVarLbProbing() or SCIPchgVarUbProbing()
}
SCIPpropagateProbing()

<read out results>

SCIPendProbing()

<change SCIP>


Note that this does not perform full presolving, but only variable 
propagations. If you need a full presolving, you should probably create 
(another) copy of your SCIP instance, perform presolving on that 
instance and transform the results back.

Best

Marc

On 06/04/2023 14:53, s schnug wrote:
> Hi,
> 
> Imagine a large-neighborhood like procedure using SCIP as (MILP) solver, 
> which is basically all about partially fixing some available incumbent 
> and ask the solver to improve the problem while being able to interfere 
> with unfixed variables only.
> 
> While we could explicitly embed fixed-decisions (a set of fixed 
> variables) during modelling without SCIP even seeing those (e.g. 
> constant offset of accumulated fixed variables in some linear 
> inequality), this is probably hard to keep correct when the model gets 
> more complex.
> As an alternative, we could model the full problem and just use 
> SCIPfixVar for those selected variables. SCIPs presolve seems to be 
> quite efficient (i saw it efficiently remove 800k constraints on some 
> erroneous/incomplete "embed fixed decisions" code before).
> 
> Now at some point, it's important how to select variables to fix during 
> LNS, to get a problem which is: easy enough to be solved efficiently and 
> big enough to cover a large-neighborhood.
> Somewhat ignoring the difference between structured (exploiting 
> problem-specific knowledge) and unstructured (basically uniform over 
> variables) variable-selection, the following idea comes to mind:
> 
> - Use the number of variables as a proxy-measure for easyness / 
> neighborhood-size (it can be argued of course if that's a good idea)
> - Obviously, some variables might have many implications (like fixings) 
> on other variables while others are less "effectful"
> 
> The latter is hard to analyze and doing it will probably become a 
> maintainment-burden too with more complex models.
> 
> An idea here is:
> 
> - Select TargetVarCount
> - done = false
> - While !done
>    - Select a constant batch of variables
>    - Fix those variables (using some available incumbent)
>    - Trigger presolve
>      - Variable fixings are about to happen
>    - Read out remaining (non-presolved) variables -> RemVars
>      - If RemVars <= TargetVarCount
> done = true
> 
> Can this be achieved (easily) with SCIP?
> 
> The documentation might indicate, that it's not as easy as one would 
> hope as:
> 
> SCIPpresolve(...)
> 
> Postcondition
> After calling this method SCIP reaches one of the following stages:
> SCIP_STAGE_PRESOLVING if the presolving process was interrupted
> SCIP_STAGE_PRESOLVED if the presolving process was finished and did not 
> solve the problem
> SCIP_STAGE_SOLVED if the problem was solved during presolving
> 
> SCIPfixVar(...)
> 
> Precondition
> This method can be called if scip is in one of the following stages:
> SCIP_STAGE_PROBLEM
> SCIP_STAGE_PRESOLVING
> SCIP_STAGE_SOLVING
> 
> I expect SCIPpresolve to result in SCIP_STAGE_PRESOLVED which is not 
> allowed when calling SCIPfixVar :-/.
> 
> When not being restricted to variable-fixings, i expect some theory 
> problems due to dual-reductions (compare with incremental SAT-solving 
> where presolving away variables might be incorrect depending on future 
> changes too).
> Not sure if the restriction of variable-fixing only (without revising 
> any earlier decision) helps here (in theory) and how hard it is to 
> exploit in practice.
> 
> Greetings,
> Sascha
> 
> _______________________________________________
> Scip mailing list
> Scip at zib.de
> https://listserv.zib.de/mailman/listinfo/scip