Programmatically fixing variables with near-zero coefficients to zero in JuMP

Specific Domains Optimization (Mathematical)
1

In JuMP, is there a way to programmatically fix the variables, that have zero or near-zero multiplicative coefficients, to zero? A simple toy example (where it is very easy to compute the coefficients) that shows what I want to do would be:

n = 10
m = Model(Gurobi.Optimizer)
coeff = [rand(0:1) for i in 1:n]
@variable(m, x[1:n] >= 0)
@objective(m, Max, sum(x[i] for i in 1:n))
@constraint(m, sum(x[i] * coeff[i] for i in 1:n) <= 1)
# fix the x[i] which have coefficient zero or near 0
for i in 1:n
    if abs(coeff[i]) <= 1e-6
        @info "Fixing x[$i] to 0"
        fix(x[i], 0.0; force = true)
    end
end
optimize!(m)
@show value.(x)

I have an optimization problem, where the model has many constraints and the model is fairly complex. I would like fix the variables, which have zero or near-zero multiplicative coefficients to zero in the final JuMP model, to 0, e.g.,

fix(x[i], 0.0; force = true) # x[i] has coefficient 0 or near-zero in all the constraints

before optimizing the objective. Is there a way to do it programmatically in JuMP?

1 Like
2

Hey Shuvo,

You’ll need something like:

using JuMP

function fix_if_small_coefficient(model; atol)
    to_check = Set(all_variables(model))
    for (F, S) in list_of_constraint_types(model)
        if F != AffExpr
            continue  # Check only the affine constraints
        end
        for ci in all_constraints(model, F, S) 
            object = constraint_object(ci)
            for xi in to_check
                if abs(coefficient(object.func, xi)) >= atol
                    pop!(to_check, xi)
                end
            end
        end
    end
    for xi in to_check
        println("Fixing $xi")
        fix(xi, 0.0; force = true)
    end
    return
end

n = 10
coeff = rand(n)
model = Model()
@variable(model, x[1:n] >= 0)
@objective(model, Max, sum(x))
@constraint(model, coeff' * x <= 1)
fix_if_small_coefficient(model; atol = 0.2)
3

You could use a semi-continous variable, that is fixed to allow zero plus say 1e-6 and greater

It does make the optimization problem much harder but gurobi IIRC has specific support for it

2 Likes
4

Thanks @odow! Essentially, what I want is to fix those variables which have near-zero coefficients in all the constraints (loosely speaking, fix those variables to zero that do not participate in the model), but it seems that the code sometimes also sets variables that do not have zero coefficients in all the constraint to zero as well. Working example:

using JuMP, Gurobi
n = 10
my_tol = 0.2
coeff = [0.16557266662150705, 0.9658411317234747, 0.0024468455279631485, 0.8886233490516873, 0.46965833440253946, 0.4549252840587207, 0.011980761056146094, 0.9961512126831391, 0.3737326710328216, 0.08191931477002423]
model = Model(Gurobi.Optimizer)
@variable(model, x[1:n] >= 0)
@variable(model, y >= 0)    
@objective(model, Max, sum(x) + y^2)
@constraint(model, coeff' * x <= 1)
@constraint(model, x[1] + y^2  <= 1)
fix_if_small_coefficient(model; atol = my_tol)
@show fix_value(y)
optimize!(model)
# print solution
println("Objective value: ", objective_value(model))

This fixes:

Fixing x[1]
Fixing x[7]
Fixing x[10]
Fixing y
Fixing x[3]

Note that, x[1] has coefficients 1 in the second constraints, so it should not be fixed to 0. Same goes for y, it has coefficient 0 in the first constraint but coefficient 1 in the second constraint, so should not be fixed to 0. Please let me know how to get the intended behavior, where only the variables that have near-zero coefficients over all the constraints are fixed to 0.

5

Well sure, your second constraint is quadratic, and I have

        if F != AffExpr
            continue  # Check only the affine constraints
        end

You’d need to relax this to also check quadratic.

6

Okay I think I understand what you meant, let me try it.

1 Like
7

@odow, it works as you suggested, thanks very much!

1 Like