Changing variable bounds during reoptimization

[cdanielmachado]

I am trying to solve an LP problem multiple times, where both the objective coefficients and the bounds of the variables may get modified between iterations. Something of the form:

for iteration i in {1,2,3... }:

solve:
    max c(i) * x
    where
        A * x = b
        lb(i) < x < ub(i)

I start with enableReoptimization() before populating the model with variables and constraints. After solving the problem in each iteration, I free the problem with freeReoptSolve(), and then modify the objective coefficients and the variable bounds.

Changing the objective coefficients is successful, however something strange happens with the variable bounds. I am able to change them (if I retrieve the bounds from the variables, i see they have been updated), but the model is still solved with the original values (and if I write the problem to a file, I see that the old values are still there).

1. Is this an issue or is it expected behavior?

2. How can I (properly) modify variable bounds using re-optimization?

[cdanielmachado]

Small correction to what i said above: changing the bounds after freeReoptSolve() (stage moves to PRESOLVED) updates the "global" bounds but not "local" or "original".

This is likely a result of this:

    switch( scip->set->stage )
    {
    case SCIP_STAGE_PROBLEM:
       assert(!SCIPvarIsTransformed(var));
       SCIP_CALL( SCIPvarChgLbGlobal(var, scip->mem->probmem, scip->set, scip->stat, scip->lp,
             scip->branchcand, scip->eventqueue, scip->cliquetable, newbound) );
       SCIP_CALL( SCIPvarChgLbLocal(var, scip->mem->probmem, scip->set, scip->stat, scip->lp,
             scip->branchcand, scip->eventqueue, newbound) );
       SCIP_CALL( SCIPvarChgLbOriginal(var, scip->set, newbound) );
       break;
 
    case SCIP_STAGE_TRANSFORMING:
    case SCIP_STAGE_PRESOLVED:
       SCIP_CALL( SCIPvarChgLbGlobal(var, scip->mem->probmem, scip->set, scip->stat, scip->lp,
             scip->branchcand, scip->eventqueue, scip->cliquetable, newbound) );
       break;

And somehow changing only the global bounds does not affect the next optimization, since they are somehow ignored.

According to the documentation https://www.scipopt.org/doc-8.0.3/html/REOPT.php it should be possible to change variable bounds between P(i) and P(i+1)...

[svigerske]

It is not related directly to the issue raised here, but I doubt that the reoptimization feature of SCIP is useful to solve a sequence of similar LPs. For LPs, you would want that at least the basis solution of one solve is somehow used as a starting point for the next solve. However, that won't happen here. SCIP's reoptimization is for solving a sequence of MIPs (with changing objective or shrinking feasible region) and focuses on reusing some information from the branch-and-bound tree of one solve for the next one. When solving LPs with SCIP, there is no branch-and-bound.

You may want to look into using LP solvers directly instead, e.g., SoPlex.

[cdanielmachado]

Thanks for the clarification. Although my code is mostly meant to solve LPs, I sometimes need to solve MILPs, and would like to keep the code generic enough to cover both cases. It's ok with me if there is no advantage of reoptimization for LPs. I mostly want to avoid the time overhead of re-creating the whole problem object in memory when I need to solve thousands of variations of the same problem. In theory, using `freeProblem()` instead of `freeReOptSolve()` to discard all information after solving should be enough for I want to do. But this is not working either. It brings the problem back to stage PROBLEM, but refuses to be solved a second time (throws an error if `solve()` is called again).

…

On Fri, 5 Jul 2024, 17:39 Stefan Vigerske, ***@***.***> wrote: It is not related directly to the issue raised here, but I doubt that the reoptimization feature of SCIP is useful to solve a sequence of similar LPs. For LPs, you would want that at least the basis solution of one solve is somehow used as a starting point for the next solve. However, that won't happen here. SCIP's reoptimization is for solving a sequence of MIPs (with changing objective or shrinking feasible region) and focuses on reusing some information from the branch-and-bound tree of one solve for the next one. When solving LPs with SCIP, there is no branch-and-bound. You may want to look into using LP solvers directly instead, e.g., SoPlex <https://soplex.zib.de/>. — Reply to this email directly, view it on GitHub <#95 (comment)>, or unsubscribe <https://github.com/notifications/unsubscribe-auth/AATX4VLLZ5DO6I5G5QMMLIDZK24ZTAVCNFSM6AAAAABKNAUP2GVHI2DSMVQWIX3LMV43OSLTON2WKQ3PNVWWK3TUHMZDEMJRGA4DGOJYGU> . You are receiving this because you authored the thread.Message ID: ***@***.***>

[svigerske]

It should not throw an error when solved again from PROBLEM stage. Can you include more information on this error?

[cdanielmachado]

Sure, here is what happens if I try to solve a second time (by the way, I'm using PySCIPOpt API, but i don't think it is a problem with the python API):

[svigerske]

This seems like a bug, but I have problems to reproduce.
I tried this:

   SCIP* scip;
   SCIPcreate(&scip);
   SCIPincludeDefaultPlugins(scip);
   SCIPprintVersion(scip, NULL);
   SCIPreadProb(scip, "/path/to/some/lp.mps", NULL);
   SCIPsolve(scip);
   SCIPfreeTransform(scip);
   SCIPsolve(scip);

There was no error.

Since you pointed to the SCIP 8 docu before, can you check that you use the latest SCIP version (9.1.0). If so, can you provide some full example code to reproduce this?

[cdanielmachado]

I am using the latest PySCIPOpt, which according to the documentation, comes pre-packaged with SCIP 9.1.

You can reproduce the error with:

#!/usr/bin/python

from pyscipopt import Model
problem = Model()
problem.enableReoptimization()
X = problem.addVar("X", lb=0, ub=1)
problem.chgReoptObjective(X, sense='minimize')
problem.optimize()
problem.freeTransform()
problem.optimize()

But actually, I just realized that the problem disappears if i don't enable re-optimization.

In fact, it seems I can re-use the problem instance and re-optimize multiple times as long as I don't enable reoptimization... Even the problem I reported initially (variable bounds not changing) seems to disappear if I don't enable reoptimization...

[svigerske]

Ah ok, I didn't realize you still tried reoptimization. Then I can reproduce the issue also with the following C code:

int main() {
   SCIP* scip;
   SCIPcreate(&scip);
   SCIPincludeDefaultPlugins(scip);
   SCIPenableReoptimization(scip, TRUE);
   SCIPreadProb(scip, "/path/to/some/lp.mps", NULL);
   SCIPsolve(scip);
   SCIPfreeTransform(scip);
   SCIPsolve(scip);
   
   return 0;
}

The docu suggests to use SCIPfreeReoptSolve() instead of SCIPfreeTransform(). If I do that, it runs through without an issue.

I suppose a better error message could be nice.

@sbolusani You were looking into reoptimization recently. :) Could you take a look into this?

[cdanielmachado]

Unfortunately with freeReOptSolve() we get back to the original issue that changing variable bounds has no effect.

[DominikKamp]

The problem can only be restricted, so relaxing variable bounds is not supported by reoptimization, as explained in the documentation, does this explain the trouble?

[cdanielmachado]

That makes sense, I didn't realize the documentation mentioned that the solution space can only be restricted between iterations.