atoptima
Continuous variables in GeneralizedAssignment demo
Describe the bug
The solution is not correct when using continuous variables x instead of binary variables in the Generalized Assignment demo.
To Reproduce
using Coluna, ColunaDemos, GLPK, JuMP, BlockDecomposition
data = ColunaDemos.GeneralizedAssignment.data("play2.txt")
coluna = JuMP.optimizer_with_attributes(
Coluna.Optimizer,
"params" => Coluna.Params(solver = Coluna.Algorithm.BranchCutAndPriceAlgorithm()),
"default_optimizer" => GLPK.Optimizer
)
model = BlockModel(coluna, direct_model = true)
@axis(M, data.machines)
@variable(model, x[m in M, j in data.jobs])
@constraint(model, cov[j in data.jobs], sum(x[m,j] for m in M) >= 1)
@constraint(model, knp[m in M], sum(data.weight[j,m]*x[m,j] for j in data.jobs) <= data.capacity[m])
@objective(model, Min, sum(data.cost[j,m]*x[m,j] for m in M, j in data.jobs))
@dantzig_wolfe_decomposition(model, dec, M)
subproblems = BlockDecomposition.getsubproblems(dec)
specify!.(subproblems, lower_multiplicity = 0)
BlockDecomposition.objectiveprimalbound!(model, 100)
BlockDecomposition.objectivedualbound!(model, 0)
JuMP.optimize!(model)
for m in data.machines
w = 0.0
for j in data.jobs
if JuMP.value(x[m,j]) > 0.9999
println("x[$m,$j] = ", JuMP.value(x[m,j]))
end
end
end
in GeneralizedAssignment demo and run the first Coluna test ("toy instance" inside "GeneralizedAssignment")
Expected behavior Terminates with dual bound = primal bound = 100, which not normal as the optimal solution with binary variables x is 75.
Environment (please complete the following information):
- Julia version 1.6.2
- master branch of Coluna
- OS: MacOs
x variables are unbounded. So when x variables have negative costs in the subproblem, the subproblem objective is unbounded and no column is generated. Col gen ends up by saying the whole problem is infeasible.
Here is the log without the initial primal bound.
Coluna
Version 0.4.2 | https://github.com/atoptima/Coluna.jl
***************************************************************************************
**** BaB tree root node
**** Local DB = 0.0000, global bounds : [ 0.0000 , Inf ], time = 3.24 sec.
***************************************************************************************
<it= 1> <et=12.61> <mst= 2.43> <sp= 1.56> <cols= 0> <al= 0.00> <DB=70000.0000> <mlp=70000.0000> <PB=Inf>
[ Info: Column generation algorithm has converged.
# <it= 1> <et=13.02> <mst= 0.00> <sp= 0.00> <cols= 0> <al= 0.00> <DB=70000.0000> <mlp=70000.0000> <PB=Inf>
[ Info: Phase one determines infeasibility.
Node is already conquered. No children will be generated.
If I add a lower bound on x variables (x[] >= 0), I find the same solution with GLPK and Coluna.
direct approach with GLPK
JuMP.objective_value(model) = 64.14285714285715
x[1,1] = 1.0
x[1,6] = 1.0000000000000002
x[2,2] = 1.0000000000000002
x[2,3] = 1.0
x[2,4] = 1.0
Coluna
Coluna
Version 0.4.2 | https://github.com/atoptima/Coluna.jl
***************************************************************************************
**** BaB tree root node
**** Local DB = 0.0000, global bounds : [ 0.0000 , Inf ], time = 3.46 sec.
***************************************************************************************
<it= 1> <et=13.04> <mst= 2.01> <sp= 2.39> <cols= 2> <al= 0.00> <DB= 0.0000> <mlp=70000.0000> <PB=Inf>
<it= 2> <et=13.39> <mst= 0.06> <sp= 0.00> <cols= 2> <al= 0.00> <DB= 0.0000> <mlp=50016.0000> <PB=Inf>
<it= 3> <et=13.39> <mst= 0.00> <sp= 0.00> <cols= 2> <al= 0.00> <DB= 0.0000> <mlp=30047.0000> <PB=Inf>
<it= 4> <et=13.39> <mst= 0.00> <sp= 0.00> <cols= 2> <al= 0.00> <DB= 0.0000> <mlp=10082.0000> <PB=Inf>
<it= 5> <et=13.51> <mst= 0.00> <sp= 0.00> <cols= 2> <al= 0.00> <DB= 42.7000> <mlp= 83.0000> <PB=Inf>
<it= 6> <et=13.63> <mst= 0.00> <sp= 0.00> <cols= 1> <al= 0.00> <DB= 56.7083> <mlp= 66.3750> <PB=66.3750>
<it= 7> <et=13.63> <mst= 0.00> <sp= 0.00> <cols= 0> <al= 0.00> <DB= 64.1429> <mlp= 64.1429> <PB=64.1429>
[ Info: Dual bound reached primal bound.
Node is already conquered. No children will be generated.
──────────────────────────────────────────────────────────────────────────────────────
Time Allocations
─────────────────────── ────────────────────────
Tot / % measured: 3154s / 0.4% 3.74GiB / 42.4%
Section ncalls time %tot avg alloc %tot avg
──────────────────────────────────────────────────────────────────────────────────────
Coluna 1 14.2s 100.0% 14.2s 1.59GiB 100.0% 1.59GiB
SolveLpForm 7 1.47s 10.3% 210ms 68.7MiB 4.2% 9.82MiB
Getting primal solution 7 279ms 2.0% 39.8ms 7.48MiB 0.5% 1.07MiB
Cleanup columns 7 176ms 1.2% 25.2ms 11.2MiB 0.7% 1.60MiB
Store records 1 96.5ms 0.7% 96.5ms 4.99MiB 0.3% 4.99MiB
Update Lagrangian bound 7 80.5ms 0.6% 11.5ms 2.84MiB 0.2% 416KiB
Update reduced costs 7 70.2ms 0.5% 10.0ms 3.80MiB 0.2% 556KiB
Smoothing update 7 49.6ms 0.3% 7.08ms 3.85MiB 0.2% 564KiB
Restore/remove records 1 15.7μs 0.0% 15.7μs 0.00B 0.0% 0.00B
──────────────────────────────────────────────────────────────────────────────────────
[ Info: Terminated
[ Info: Primal bound: 64.14285712357142
[ Info: Dual bound: 64.14285712357142
x[1,1] = 1.0
x[1,6] = 1.0
x[2,2] = 1.0
x[2,3] = 1.0
x[2,4] = 1.00000000125
Ok, thank you, Guillaume. I think however that if the subproblem is unbounded, the master solution should also be declared as unbounded, no? It is not correct to declare the problem infeasible here.
Also, I do not understand why the solution value (64.1429) when I set
@variable(model, 1>=x[m in M_axis, j in J]>=0);
is different from the root (fractional) solution value (70.3333) when I set
@variable(model, 1>=x[m in M_axis, j in J]>=0, Bin);
For me, setting x variables fractional should result in solving only the root of column generation. Does my understanding is correct or not?
Ok, thank you, Guillaume. I think however that if the subproblem is unbounded, the master solution should also be declared as unbounded, no? It is not correct to declare the problem infeasible here.
I agree it's incorrect to declare the problem infeasible. However, the original problem is not unbounded. Only the subproblem is because some variables have negative reduced cost. At the very least, col gen should throw an exception saying that a subproblem is unbounded.