Fixing and freeing variables o JuMP

Specific Domains Optimization (Mathematical)
1

I am studying a combinatorial optimization problem with JuMP and Gurobi. I need to fix some decision variables for a given number of iterations or a given time limit. After that, I would like to unfix these variables previously fixed and to fix another subset of variables. Iteratively, I would like to perform this process of fix and unfix decision variables in the same run. Is this possible?

1 Like
2

I am not so sure of how the state of wrapper is currently, but in my personal experience:

This is kinda simple. You can fix with JuMP.fix and unfix with JuMP.unfix (just keep in mind this doing this will erase any previous bounds in the variable, so you may need to save them before and recover them after). And you can control the time or number of iterations by giving it as a limit to the solver.

This is much harder. It depends on the solver callbacks available (and what the solver allows you to do inside a callback), and how is the state of JuMP, MOI, and the solver wrapper (i.e., Gurobi.jl, CPLEX.jl, etc…). If the number of iterations or the time limit are sufficiently large, i.e., some seconds, then there should not be much overhead by starting and stopping the optimization process after the fix-unfix.

1 Like
3

Dear Henrique,

Thank you very much for your support.

I am using Gurobi, a state-of-the-art solver. I will investigate this issue.

Cheers,
Bruno

4

I also use Gurobi and I have to say that in my experience it is more limited in terms of callbacks and what you can do inside them than CPLEX. Even so, I am not sure if it is possible to do this in CPLEX. I think what you should search for is if Gurobi allows changing variables bounds inside a callback (or, more generally, adding and removing constraints). If this is possible then you probably can do what you want (you can use a callback that is called every node and then increment a counter or check the time, the question is if you can do what you want inside a callback).

5

Dear Henrique,
Thank you very much for your feedback. I am trying to find these issues.
Cheers,
Bruno

6

Don’t fix and free variables inside a callback. Just do something like the following

model = Model(Gurobi.Optimizer)
@variable(model, x)
# ... other stuff
optimize!(model)
fix(x, 1.0)
optimize!(model)
fix(x, 2.0)
optimize!(model)
unfix(x)
optimize!(model)
7

Complementing what @odow said, if you want to do things inside a callback often you need to use special functions, so JuMP.fix and JuMP.unfix serve to the purpose of fixing-unfixing variables when the solver is stopped (i.e., outside of an optimize! call), but if you find a way to do so inside a callback you probably will need to use low-level solver-specific methods which the solver documentation makes clear that can be called inside a callback (the vast majority of the solver methods, specially the ones related to model building, cannot be called inside a callback).

If you give up on the idea of using a callback, I just recommend you save variable bounds before the fix and restore after the unfix (as fix-unfix will disappear with the previous bounds), and you will probably call optimize! on a loop with the calls restricted by time/iterations and will want to check the termination status after the call (to know if a primal solution was generated).

8

Just to clarify, you cannot modify variable bounds in a Gurobi callback.

Perhaps it would help if you explained why you want to do this.

9

I think it is safe to guess that bounds on callbacks is something one would want because of performance.

Also, technically, you can add constraints on a single variable with Lazy constraints, but this only solves the fix part not the unfix one.

10

Dear Oscar,

Thank you very much for your help.

I had already this idea and this is an interesting possiblity. However, in this way we would have multiple starts and with preprocessing of the solver, we would lost some computational effort. I will test your suggestion, thank you for your time.

Cheers,
Bruno

1 Like
11

You can disable preprocessing but depending in your problem it may be better to keep it.

12

There are restrictions to what you can/cannot do with a MIP solver like CPLEX/Gurobi/Xpress, etc.
These limitations exists whether you access the solvers from a their C API, Julia, JuMP, etc.

Long story short, fixing/unfixing variables multiple times during the optimization is one such thing that is not supported.
The main reason is that doing so may invalidate a lot of the techniques used by MIP solvers, e.g., it may invalidate presolve reductions, render cuts invalid, etc. It would be a mathematical and software nightmare to support it.

That being said, there are ways around this.

  • As @odow has suggested, you can fix some variables, optimize, unfix them and re-optimize (within a loop if you want to). This is the most straightforward way.
    It is fair to expect major solvers like Gurobi to be able to take advantage of this (e.g., by re-using feasible MIP solutions). However, a lot of work needs to be re-done: un-fixing variables means dual bounds & cuts are unlikely to still be valid.

  • You can tighten (but never enlarge) a model’s feasible set by adding extra constraints within a callback (in your case, these would be lazy constraints). For instance, you can add the constraint x == 0 to fix the variable x to value 0. However, you cannot un-fix it later (unless you re-solve from scratch).

  • Fixing and un-fixing variables can be seen as an elaborate variable branching / node selection policy. Solvers like CPLEX and Xpress allow you to take control of these components, but:

    • These functionalities are not exposed in JuMP (not that I know of at least)
    • You would be responsible for branching (something MIP solvers are very good at).

    Unless you really, really, really know what you’re doing, this approach is unlikely to deliver computational benefits, and is much, much, much mode complex than the first suggestion above.

  • Finally, you may want to consider a hybrid approach, where you consider multiple MIP models. The rational for doing so is that fixing-unfixing variables is akin to a local search step. It helps with finding good solutions, but will not give dual bounds (which are needed for proving optimality). A good example of such strategy is local branching.
    In practice, you would work with a “master” MIP problem, and auxiliary “sub-problems” that would (most likely) be solved within a callback. In your case, such sub-problems would be obtained from the original model by fixing some variables.

2 Likes
13

Dear Henrique,

Thanks a lot again.

Bruno

2 Likes
14

Dear mtanneau,

Thank you very much for your attention. I am studying your suggestions in details. Thank you for your time.

Bruno

3 Likes