Fixing and freeing variables o JuMP

Specific Domains Optimization (Mathematical)
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