Adding cuts iteratively

Specific Domains Optimization (Mathematical)
, ,
1

I am attempting to incorporate perspective cuts into a non-linear model for linearization using the JuMP package. My aim is to utilize the SCIP solver and introduce a cut every 5 seconds, utilizing a feasible point to add a cut. However, I have discovered that I am unable to employ the callback functions. Is there an alternative approach to achieve this?

2

I have discovered that I am unable to employ the callback functions

Correct. SCIP does not support adding lazy constraints via JuMP.

Is there an alternative approach to achieve this?

Use an iterative process

julia> using JuMP, Ipopt

julia> model = Model(Ipopt.Optimizer)
A JuMP Model
Feasibility problem with:
Variables: 0
Model mode: AUTOMATIC
CachingOptimizer state: EMPTY_OPTIMIZER
Solver name: Ipopt

julia> set_silent(model)

julia> @variable(model, 1 <= x <= 10)
x

julia> @variable(model, t >= 0)
t

julia> @objective(model, Min, t)
t

julia> # @NLconstraint(model, t >= exp(x))
       while true
           optimize!(model)
           v_t, v_x = value(t), value(x)
           if v_t >= exp(v_x) - 1e-6
               break
           end
           @constraint(model, t >= exp(v_x) + exp(v_x)  * (x - v_x))
       end

julia> value(t), value(x)
(2.718281796283739, 0.9999999909231221)

julia> print(model)
Min t
Subject to
 -4.553023229112991 x + t ≥ -2.3484104909053922
 -2.718281802771446 x + t ≥ 2.5687599158885632e-8
 x ≥ 1.0
 t ≥ 0.0
 x ≤ 10.0
2 Likes
3

For example I want to solve this very simple problem:

using JuMP, GAMS

# Define the model
model = Model(GAMS.Optimizer)
I = [1, 2]
J = [1, 2, 3]
a = [2 3 4; 3 2 1]
b = [10 12 20]
c = 35
l = [2, 1]
u = [4, 5]
x_1 = [3 1] 

@variable(model, x[i in I] >= 0)
@variable(model, y[i in I], binary = true)

@objective(model, Min, sum(x[i] for i in I))
@constraint(model, [j in J], b[j] <= sum(a[i,j] * x[i] for i in I))
@constraint(model, [i in I], l[i] * y[i] <= x[i])
@constraint(model, [i in I], x[i] <= u[i] * y[i])

# Solve the model to get the initial objective value
best_primal_bound = Inf
cut_counter = 0

while true
    # Solve the model
    set_optimizer_attribute(model, GAMS.MIP(), "SCIP")
    set_optimizer_attribute(model, GAMS.ResLim(), 0.003)
    optimize!(model)
    best_primal_bound = objective_value(model)
    
    # Update the best dual bound
    best_dual_bound = dual_objective_value(model)
    
    # Calculate the optimality gap
    optimality_gap =  (best_primal_bound - best_dual_bound) / best_primal_bound
    
    # Check the termination condition
    if optimality_gap <= 0.01
        break
    end
    
    # Extract the solution
    x_bar = value.(x)
    
    # Generate new linear cuts based on the solution
    
    # Add the new linear cuts to the model
    @constraint(model,  2 * sum(x_bar[i] * x[i] for i in I) - (sum(x_bar[i]^2 for i in I) + 35) * y[1] <= 0)
    @constraint(model,  2 * sum(x_bar[i] * x[i] for i in I) - (sum(x_bar[i]^2 for i in I) + 35) * y[2] <= 0)
    
    # Increment the cut counter
    cut_counter += 1
    println("x_bar:", value.(x_bar))
end

but the following error appeared:

ERROR: LoadError: MethodError: no method matching 
constant(::MathOptInterface.ZeroOne)
caused by: MathOptInterface.GetAttributeNotAllowed{MathOptInterface.DualObjectiveValue}: Getting attribute MathOptInterface.DualObjectiveValue(1) cannot be performed: GAMS.Optimizer does not support getting the attribute MathOptInterface.DualObjectiveValue(1). You may want to use a `CachingOptimizer` in `AUTOMATIC` mode or you may need to call `reset_optimizer` before doing this operation if the `CachingOptimizer` is in `MANUAL` mode.
4

You’re asking for dual_objective_value, but the problem has binary variables so it doesn’t have a dual objective.

What is the gap that you’re trying to compute?

1 Like
5

like the option that we have in GAMS Optcr, or primal bound - dual bound / primal bound. My aim is to adding cuts during the solving process until we reach to 1 percent optimality gap. And find out how many cuts we need.

6

Try objective_bound(model).

7

But note that you’re not adding cuts during one solve. You’re repeatedly resolving the model with new constraints

8

How can I add cuts during the solving process? I need to use new feasible point that finds during the solving process and add the related cut and so on until the model reaches to 1 percent optimality gap.

9

You must use a solver-specific callback or a MOI.LazyConstraintCallback: Solver-independent Callbacks · JuMP

But only a few packages support such callbacks: Solver-independent Callbacks · JuMP

GAMS.jl and SCIP.jl do not support LazyConstraintCallback.

You could try Gurobi.jl instead: jump-dev/Gurobi.jl · JuMP

1 Like