Benders is not working on a simple example

[etiennedeg]

Describe the bug & Expected behavior I'm not sure how the decomposition work with benders, but here, I expect the d variable to be the (unconstrained) master problem. There is two subproblems S1 on variable x[1] and constraint con1 and S2 on variable x[2] and constraint con2. Depending on the value of d, exactly one x value can be set to 1. However, the returned optimal objective is 2 (where 1 is expected) and weirdly, no x is set to 1 after optimization (where one of these should be 1).

To Reproduce

using JuMP
using BlockDecomposition
using Coluna
using Gurobi

coluna = optimizer_with_attributes(
    Coluna.Optimizer,
    "params" => Coluna.Params(
        solver = Coluna.Algorithm.TreeSearchAlgorithm()
    ),
    "default_optimizer" => Gurobi.Optimizer
)

model = BlockModel(coluna)

@axis(S, 1:2)

@variable(model, d, Bin)
@variable(model, x[i in S], Bin)
@constraint(model, con1, x[S[1]] <= d)
@constraint(model,  con2, x[S[2]] <= 1-d)
@objective(model, Max, sum(x))

@benders_decomposition(model, decomposition, S)

optimize!(model)

println(value.(x))

Environment (please complete the following information):

• Julia 1.6.1
• Coluna 1.3.9

[guimarqu]

Benders decomposition is an alpha feature & the cut generation algorithm is not embeded in the TreeSearchAlgorithm at the moment. You have to use Coluna.Algorithm.BendersCutGeneration() as solver and it will solve only the root node of the branch&bound tree.

In your formulation, constraints con1 and con2 are part of the master because they are not annotated. The documentation is not clear enough on this mechanism, so I'll document this in the next few weeks. However, the final solution is incorrect.

I tried the following code :

using JuMP
using BlockDecomposition
using Coluna
using Gurobi

coluna = optimizer_with_attributes(
    Coluna.Optimizer,
    "params" => Coluna.Params(
        solver = Coluna.Algorithm.BendersCutGeneration()
    ),
    "default_optimizer" => Gurobi.Optimizer
)

model = BlockModel(coluna)

@axis(S, 1:2)

@variable(model, d, Bin)
@variable(model, x[i in S], Bin)
@constraint(model, con1[S[1]], x[S[1]] <= d)
@constraint(model,  con2[S[2]], x[S[2]] <= 1-d)
@objective(model, Max, sum(x))

@benders_decomposition(model, decomposition, S)

optimize!(model)

println(value.(x))

It doesn't work because :

• we need to define Base.length(::BlockDecomposition.AxisId) = 1 in BlockDecomposition (fixed in https://github.com/atoptima/BlockDecomposition.jl/pull/60)
• the final objective value is 2.

Looks like there are 3 bugs here.

I'll investigate as soon as possible, probably next week. Thanks for the report.

[guimarqu]

Sorry, I was wrong, con1 & con2 should be part of the master because d is a first stage variable. So your model is correct. Sorry again, these constraints are of the 2nd stage (because they involve 2nd stage variables)... So they must be in the subproblems.

If I replace the objective by @objective(model, Min, -sum(x)), I found an objective value equals to Inf -> fixed.

If I replace the objective by @objective(model, Min, -sum(x)), I found an objective value equals to -2 but it should be -1 -> fixed

If I use @objective(model, Max, sum(x)), I found an objective value equals to 2 but it should be 1

There is a bug in the reformulation & the algorithm.