Continuous variables in GeneralizedAssignment demo

[rrsadykov]

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

[guimarqu]

Hey Ruslan,

Thanks for the report, I'll take a look tomorrow.

[guimarqu]

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.

[guimarqu]

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

[rrsadykov]

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.

[rrsadykov]

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?

[rrsadykov]

Ok, I understood: x variables are fractional also in the subproblem.

[guimarqu]

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.