Jump.jl: Feature request: solve relaxation

[mlubin]

Like 0.18's relaxation=True flag to solve().

[chriscoey]

Make sure it's clear this means integer relaxation

[mlubin]

For reference, here's a version of code to relax integrality that handles the most typical cases.

```julia

model is a JuMP.Model

for v in all_variables(model)
if is_integer(v)
unset_integer(v)
# If applicable, also round the lower and upper bounds if they're not integer.
elseif is_binary(v)
unset_binary(v)
if has_lower_bound(v) && and lower_bound(v) > 0
set_lower_bound(v, 1)
else
set_lower_bound(v, 0)
end
if has_upper_bound(v) && and upper_bound(v) < 1
set_upper_bound(v, 0)
else
set_upper_bound(v, 1)
end
set_upper_bound(v, 1)
end
# If applicable, also handle semi-integer and semicontinuous.
end

[vtjeng]

I'd really like to use this in one of my projects (and it's one of the things that's preventing me from rolling out a JuMP==0.19 compatible version). What can I do to help this get in to the next release? (Is the change that @mlubin described above enough? I can write code to handle the semi-integer and semicontinuous cases if you could point me to examples of where else this is handled in the code).

[odow]

A better approach is a relax_integrality function that relaxes integrality constraints in a model, and a corresponding enforce_integrality function. (The reason is that JuMP no longer caches the solution, so re-applying the integrality constraints immediately after solve will cause solvers such as Gurobi to throw away the solution.)

You could have something like (in JuMP):

struct IntegralityCache
    # anything that is needed
end

function relax_integrality(model::Model)::IntegralityCache
    # things here
end

function enforce_integrality(model::Model, integrality_cache::IntegralityCache)
    # things here
end

Then, in user-code, it would look like

integrality_cache= relax_integrality(model)
optimize!(model)
@show objective_value(model)
enforce_integrality(model, integrality_cache)

See here for inspiration:
https://github.com/odow/SDDP.jl/blob/a33786a24c33d6c0a0232432c80659c99788f2b0/src/plugins/integrality_handlers.jl#L93-L125
https://github.com/odow/SDDP.jl/blob/a33786a24c33d6c0a0232432c80659c99788f2b0/src/plugins/integrality_handlers.jl#L10-L39

That code doesn't handle semi-continuous/integer variables, or special ordered sets though.

You will probably need something like:

for (F, S) in list_of_constraint_types(model)
    if S <: MOI.Seminteger
        for constraint_index in  all_constraints(model, F, S)
            # relax semi-integer integrality
        end
    end
end

To begin with, there is no need to write these functions inside JuMP. It's probably easier to develop in a separate script. Once you have something working, make a pull request, and we can workshop the tests and documentation :)

[mlubin]

I wouldn't mind if the initial version throws an error on semi-integer, semi-continuous and SOS (but is structured in a way that makes it possible to support them later). These these sets are used relatively rarely.

[henriquebecker91]

I am very late for this, but I used exactly this workaround on my code. If there is interest this code can copied to inside a JuMP/MOI utility or spawn a very small package.

[mlubin]

This is on the milestone for 1.0, we'd like it in JuMP. PR welcome!

[vtjeng]

For those following along, I've extracted a permalink to (what I think is) the code @henriquebecker91 is pointing to. See restore! and relax! here.

[henriquebecker91]

Oh sorry, I often remember to point to a specific repository/tree state, so what the link points does not change when I change the file. If my code is of any use for you, please make use of it, it is Unlicensed (Public Domain declaration), and so compatible with whatever license you use (even proprietary/commercial use).

Unfortunately, I am late with my PhD stuff, and probably will be in a hurry until this year's end. After I finish my PhD, I would like to contribute more, but for now patching bugs in Gurobi.jl is all I can do.

[mtanneau]

For reference, here's a version of code to relax integrality that handles the most typical cases.

# model is a JuMP.Model
for v in all_variables(model)
  if is_integer(v)
    unset_integer(v)
    # If applicable, also round the lower and upper bounds if they're not integer.
  elseif is_binary(v)
    unset_binary(v)
    if has_lower_bound(v) && and lower_bound(v) > 0
      set_lower_bound(v, 1)
    else
      set_lower_bound(v, 0)
    end
    if has_upper_bound(v) && and upper_bound(v) < 1
      set_upper_bound(v, 0)
    else
      set_upper_bound(v, 1)
    end
    set_upper_bound(v, 1)
  end
  # If applicable, also handle semi-integer and semicontinuous.
end

"Continuous relaxation" should only mean that constraints of the form x integer are dropped from the model (at least that's how it is understood in most OR papers I've read).
That means no bounds strengthening such as rounding bounds for integer variables.

throws an error on semi-integer, semi-continuous and SOS (but is structured in a way that makes it possible to support them later).

+1: IMO the "continuous relaxation" of such constraints is not always well-defined

[mlubin]

"Continuous relaxation" should only mean that constraints of the form x integer are dropped from the model
That means no bounds strengthening such as rounding bounds for integer variables.

Try telling that to the stream of users we'll get asking why the relaxation of @variable(m, x, Bin) gives an unbounded variable :). I agree that touching the bounds is probably not needed for integer variables.

[mtanneau]

the relaxation of @variable(m, x, Bin) gives an unbounded variable

That depends on what we mean by "relaxation", right?
For "continuous relaxation", x in {0, 1} gets replaced by 0 <= x <= 1.

[mlubin]

Which part of the code snippet were you objecting to?

[mtanneau]

Which part of the code snippet were you objecting to?

I was objecting to

# If applicable, also round the lower and upper bounds if they're not integer.

and to

elseif is_binary(v)
    unset_binary(v)
    if has_lower_bound(v) && and lower_bound(v) > 0
      set_lower_bound(v, 1)
    else
      set_lower_bound(v, 0)
    end
    if has_upper_bound(v) && and upper_bound(v) < 1
      set_upper_bound(v, 0)
    else
      set_upper_bound(v, 1)
    end
    set_upper_bound(v, 1)
  end

which would strengthen, e.g., x Binary and 0.5 <= x to 1 <= x <= 1.

For the binary case, since JuMP allows users to specify bounds on top of the Bin flag, I would argue for

if is_binary(v)
    unset_binary(v)
    lb = has_lower_bound(v) ? lower_bound(v) : -Inf
    ub = has_upper_bound(v) ? upper_bound(v) : Inf
    set_lower_bound(v, max(0.0, lb))
    set_upper_bound(v, min(1.0, ub))
end