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

[s schnug]

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
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://listserv.zib.de/pipermail/scip/attachments/20230406/b62519ac/attachment.html>