Valid inequalities

Now let us consider a variant of the Generalized Assignment Problem in which we have to pay f[m] to use machine m.

Consider the following instance:

J = 1:10
M = 1:5
c = [10.13 15.6 15.54 13.41 17.08;19.58 16.83 10.75 15.8 14.89;14.23 17.36 16.05 14.49 18.96;16.47 16.38 18.14 15.46 11.64;17.87 18.25 13.12 19.16 16.33;11.09 16.76 15.5 12.08 13.06;15.19 13.86 16.08 19.47 15.79;10.79 18.96 16.11 19.78 15.55;12.03 19.03 16.01 14.46 12.77;14.48 11.75 16.97 19.95 18.32];
w = [5, 4, 5, 6, 8, 9, 5, 8, 10, 7];
Q = [25,  24,  31,  28,  24];
f = [105, 103, 109, 112, 100];

We define the dependencies:

using JuMP, BlockDecomposition, Coluna, GLPK;

We parametrize the solver. We solve only the root node of the branch-and-bound tree and we use a column and cut generation algorithm to conquer (optimize) this node.

coluna = JuMP.optimizer_with_attributes(
    Coluna.Optimizer,
    "params" => Coluna.Params(
        solver = Coluna.Algorithm.TreeSearchAlgorithm(
            conqueralg = Coluna.Algorithm.ColCutGenConquer(
                max_nb_cut_rounds = 20
            ),
            branchingtreefile = "tree2.dot",
            maxnumnodes = 1
        )
    ),
    "default_optimizer" => GLPK.Optimizer
);

Column generation

We write the model:

model = BlockModel(coluna; direct_model = true);
@axis(M_axis, M)
@variable(model, x[j in J, m in M_axis], Bin);
@variable(model, y[m in M_axis], Bin);
@constraint(model, setpartitioning[j in J], sum(x[j,m] for m in M_axis) == 1);
@constraint(model, knp[m in M_axis], sum(w[j]*x[j,m] for j in J) <= Q[m] * y[m]);
@objective(model, Min, sum(c[j,m] * x[j,m] for m in M_axis, j in J) + sum(f[m] * y[m] for m in M_axis));

@dantzig_wolfe_decomposition(model, dec, M_axis);
sp = getsubproblems(dec);
specify!.(sp, lower_multiplicity = 0);

We optimize:

optimize!(model)

Coluna
Version 0.8.1 | https://github.com/atoptima/Coluna.jl
***************************************************************************************
**** B&B tree root node
**** Local DB = -Inf, global bounds: [ -Inf , Inf ], time = 0.33 sec.
***************************************************************************************
  <st= 1> <it=  1> <et= 0.46> <mst= 0.00> <sp= 0.00> <cols= 5> <al= 0.00> <DB=-129136.2200> <mlp=100000.0000> <PB=Inf>
  <st= 1> <it=  2> <et= 0.46> <mst= 0.00> <sp= 0.00> <cols= 5> <al= 0.00> <DB=-138882.3000> <mlp=30340.5500> <PB=Inf>
  <st= 1> <it=  3> <et= 0.46> <mst= 0.00> <sp= 0.00> <cols= 5> <al= 0.00> <DB=-129002.2333> <mlp=10387.9067> <PB=Inf>
  <st= 1> <it=  4> <et= 0.46> <mst= 0.00> <sp= 0.00> <cols= 5> <al= 0.00> <DB=-116197.4433> <mlp=  418.5400> <PB=Inf>
  <st= 1> <it=  5> <et= 0.46> <mst= 0.00> <sp= 0.00> <cols= 5> <al= 0.00> <DB=  226.4800> <mlp=  418.5400> <PB=Inf>
  <st= 1> <it=  6> <et= 0.46> <mst= 0.00> <sp= 0.00> <cols= 5> <al= 0.00> <DB=  352.6265> <mlp=  409.0543> <PB=Inf>
  <st= 1> <it=  7> <et= 0.47> <mst= 0.00> <sp= 0.00> <cols= 5> <al= 0.00> <DB=  310.9300> <mlp=  405.7200> <PB=Inf>
  <st= 1> <it=  8> <et= 0.47> <mst= 0.00> <sp= 0.00> <cols= 5> <al= 0.00> <DB=  368.9929> <mlp=  402.2214> <PB=Inf>
  <st= 1> <it=  9> <et= 0.47> <mst= 0.00> <sp= 0.00> <cols= 5> <al= 0.00> <DB=  365.0175> <mlp=  400.4725> <PB=Inf>
  <st= 1> <it= 10> <et= 0.47> <mst= 0.00> <sp= 0.00> <cols= 3> <al= 0.00> <DB=  392.9157> <mlp=  398.5957> <PB=Inf>
  <st= 1> <it= 11> <et= 0.47> <mst= 0.00> <sp= 0.00> <cols= 3> <al= 0.00> <DB=  382.3189> <mlp=  398.4844> <PB=Inf>
  <st= 1> <it= 12> <et= 0.47> <mst= 0.00> <sp= 0.00> <cols= 3> <al= 0.00> <DB=  392.0920> <mlp=  397.3807> <PB=Inf>
  <st= 1> <it= 13> <et= 0.47> <mst= 0.00> <sp= 0.00> <cols= 1> <al= 0.00> <DB=  395.0896> <mlp=  396.7196> <PB=Inf>
  <st= 1> <it= 14> <et= 0.47> <mst= 0.00> <sp= 0.00> <cols= 1> <al= 0.00> <DB=  395.5096> <mlp=  396.7196> <PB=Inf>
  <st= 1> <it= 15> <et= 0.47> <mst= 0.00> <sp= 0.00> <cols= 1> <al= 0.00> <DB=  394.8988> <mlp=  396.6188> <PB=Inf>
  <st= 1> <it= 16> <et= 0.47> <mst= 0.00> <sp= 0.00> <cols= 1> <al= 0.00> <DB=  395.4817> <mlp=  396.4117> <PB=Inf>
  <st= 1> <it= 17> <et= 0.47> <mst= 0.00> <sp= 0.00> <cols= 0> <al= 0.00> <DB=  396.2954> <mlp=  396.2954> <PB=Inf>
──────────────────────────────────────────────────────────────────────────
                                 Time                    Allocations
                        ───────────────────────   ────────────────────────
   Tot / % measured:         4.72s /  52.4%            425MiB /  60.7%

Section         ncalls     time    %tot     avg     alloc    %tot      avg
──────────────────────────────────────────────────────────────────────────
Coluna               1    2.47s  100.0%   2.47s    258MiB  100.0%   258MiB
  SolveLpForm       17   3.19ms    0.1%   188μs   1.35MiB    0.5%  81.6KiB
──────────────────────────────────────────────────────────────────────────
[ Info: Terminated
[ Info: Primal bound: Inf
[ Info: Dual bound: 396.29541664666664

The final dual bound is:

db1 = objective_bound(model)

396.29541664666664

Strengthen with valid inequalities

Let H be the set of configurations of open machines (h[m] = 1 if machine m open; 0 otherwise) such that all jobs can be assigned : sum(h'Q) >= sum(w) i.e. the total capacity of the open machines must exceed the total weight of the jobs.

H = Vector{Int}[]
for h in digits.(1:(2^length(M) - 1), base=2, pad=length(M))
    if sum(h'Q) >= sum(w)
        push!(H, h)
    end
end
H

16-element Vector{Vector{Int64}}:
 [1, 1, 1, 0, 0]
 [1, 1, 0, 1, 0]
 [1, 0, 1, 1, 0]
 [0, 1, 1, 1, 0]
 [1, 1, 1, 1, 0]
 [1, 1, 0, 0, 1]
 [1, 0, 1, 0, 1]
 [0, 1, 1, 0, 1]
 [1, 1, 1, 0, 1]
 [1, 0, 0, 1, 1]
 [0, 1, 0, 1, 1]
 [1, 1, 0, 1, 1]
 [0, 0, 1, 1, 1]
 [1, 0, 1, 1, 1]
 [0, 1, 1, 1, 1]
 [1, 1, 1, 1, 1]

Let ȳ be the solution to the linear relaxation of the problem. Let us try to express ȳ as a linear expression of the configurations. If ȳ ∈ conv H, we can derive a cut because the optimal integer solution to the problem uses one of the configurations of H.

We need MathOptInterface to define the cut callback:

using MathOptInterface

The separation algorithm looks for the non-negative coefficients χ[k], k = 1:length(H), : max sum(χ[k] for k in 1:length(H)) such that sum(χ[k]* h for (k,h) in enumerate(H)) <= ̄ȳ. If the objective value is less than 1, we must add a cut.

Since the separation algorithm is a linear program, strong duality applies. So we separate these cuts with the dual.

fc_sep_m = Model(GLPK.Optimizer)
@variable(fc_sep_m, ψ[m in M] >= 0) # one variable for each constraint
@constraint(fc_sep_m, config_dual[h in H], ψ'h >= 1) # one constraint for each χ[k]
MathOptInterface.set(fc_sep_m, MathOptInterface.Silent(), true)

The objective is min ȳ'ψ = sum(χ[k] for k in 1:length(H)). Let ψ* be an optimal solution to the dual. If ȳ'ψ* < 1, then ψ*'y >= 1 is a valid inequality.

function fenchel_cuts_separation(cbdata)
    println("Fenchel cuts separation callback...")
    ȳ = [callback_value(cbdata, y[m]) for m in M_axis]
    @objective(fc_sep_m, Min, ȳ'ψ) # update objective
    optimize!(fc_sep_m)
    if objective_value(fc_sep_m) < 1
        con = @build_constraint(value.(ψ)'y >= 1) # valid inequality.
        MathOptInterface.submit(model, MathOptInterface.UserCut(cbdata), con)
    end
end

MathOptInterface.set(model, MathOptInterface.UserCutCallback(), fenchel_cuts_separation);

We optimize:

optimize!(model)

Coluna
Version 0.8.1 | https://github.com/atoptima/Coluna.jl
***************************************************************************************
**** B&B tree root node
**** Local DB = -Inf, global bounds: [ -Inf , Inf ], time = 0.00 sec.
***************************************************************************************
  <st= 1> <it=  1> <et= 0.00> <mst= 0.00> <sp= 0.00> <cols= 5> <al= 0.00> <DB=-129136.2200> <mlp=100000.0000> <PB=Inf>
  <st= 1> <it=  2> <et= 0.00> <mst= 0.00> <sp= 0.00> <cols= 5> <al= 0.00> <DB=-139045.0100> <mlp=30340.5500> <PB=Inf>
  <st= 1> <it=  3> <et= 0.00> <mst= 0.00> <sp= 0.00> <cols= 5> <al= 0.00> <DB=-129366.4000> <mlp=20324.0700> <PB=Inf>
  <st= 1> <it=  4> <et= 0.01> <mst= 0.00> <sp= 0.00> <cols= 5> <al= 0.00> <DB=-138963.0225> <mlp=10409.6475> <PB=Inf>
  <st= 1> <it=  5> <et= 0.01> <mst= 0.00> <sp= 0.00> <cols= 5> <al= 0.00> <DB=-116680.1467> <mlp= 3762.3733> <PB=Inf>
  <st= 1> <it=  6> <et= 0.01> <mst= 0.00> <sp= 0.00> <cols= 5> <al= 0.00> <DB=  338.8240> <mlp=  412.3300> <PB=Inf>
  <st= 1> <it=  7> <et= 0.06> <mst= 0.00> <sp= 0.00> <cols= 5> <al= 0.00> <DB=  368.4725> <mlp=  408.4225> <PB=Inf>
  <st= 1> <it=  8> <et= 0.07> <mst= 0.00> <sp= 0.00> <cols= 4> <al= 0.00> <DB=  387.0237> <mlp=  401.4150> <PB=Inf>
  <st= 1> <it=  9> <et= 0.07> <mst= 0.00> <sp= 0.00> <cols= 3> <al= 0.00> <DB=  387.9907> <mlp=  399.3757> <PB=Inf>
  <st= 1> <it= 10> <et= 0.07> <mst= 0.00> <sp= 0.00> <cols= 3> <al= 0.00> <DB=  392.3535> <mlp=  397.7405> <PB=Inf>
  <st= 1> <it= 11> <et= 0.07> <mst= 0.00> <sp= 0.00> <cols= 1> <al= 0.00> <DB=  393.8619> <mlp=  396.8694> <PB=Inf>
  <st= 1> <it= 12> <et= 0.07> <mst= 0.00> <sp= 0.00> <cols= 2> <al= 0.00> <DB=  395.0354> <mlp=  396.4754> <PB=Inf>
  <st= 1> <it= 13> <et= 0.07> <mst= 0.00> <sp= 0.00> <cols= 0> <al= 0.00> <DB=  396.2954> <mlp=  396.2954> <PB=Inf>
Fenchel cuts separation callback...
Cut separation callback adds 0 new essential cuts and 1 new facultative cuts.
avg. viol. = 0.54, max. viol. = 0.54, zero viol. = 0.
  <st= 1> <it=  1> <et= 1.28> <mst= 0.00> <sp= 0.00> <cols= 4> <al= 0.00> <DB=  378.4833> <mlp=  400.0300> <PB=Inf>
  <st= 1> <it=  2> <et= 1.28> <mst= 0.00> <sp= 0.00> <cols= 1> <al= 0.00> <DB=  398.3356> <mlp=  399.2656> <PB=Inf>
  <st= 1> <it=  3> <et= 1.28> <mst= 0.00> <sp= 0.00> <cols= 3> <al= 0.00> <DB=  398.1915> <mlp=  398.9556> <PB=Inf>
  <st= 1> <it=  4> <et= 1.28> <mst= 0.00> <sp= 0.00> <cols= 0> <al= 0.00> <DB=  398.9050> <mlp=  398.9050> <PB=Inf>
Fenchel cuts separation callback...
Cut separation callback adds 0 new essential cuts and 1 new facultative cuts.
avg. viol. = 0.50, max. viol. = 0.50, zero viol. = 0.
  <st= 1> <it=  1> <et= 1.28> <mst= 0.00> <sp= 0.00> <cols= 3> <al= 0.00> <DB=  397.8726> <mlp=  399.7207> <PB=Inf>
  <st= 1> <it=  2> <et= 1.29> <mst= 0.00> <sp= 0.00> <cols= 0> <al= 0.00> <DB=  399.6563> <mlp=  399.6563> <PB=Inf>
Fenchel cuts separation callback...
Cut separation callback adds 0 new essential cuts and 1 new facultative cuts.
avg. viol. = 0.26, max. viol. = 0.26, zero viol. = 0.
  <st= 1> <it=  1> <et= 1.29> <mst= 0.00> <sp= 0.00> <cols= 0> <al= 0.00> <DB=  401.7597> <mlp=  401.7597> <PB=Inf>
Fenchel cuts separation callback...
Cut separation callback adds 0 new essential cuts and 1 new facultative cuts.
avg. viol. = 0.42, max. viol. = 0.42, zero viol. = 0.
  <st= 1> <it=  1> <et= 1.29> <mst= 0.00> <sp= 0.00> <cols= 0> <al= 0.00> <DB=  403.5883> <mlp=  403.5883> <PB=Inf>
Fenchel cuts separation callback...
Cut separation callback adds 0 new essential cuts and 1 new facultative cuts.
avg. viol. = 0.24, max. viol. = 0.24, zero viol. = 0.
  <st= 1> <it=  1> <et= 1.29> <mst= 0.00> <sp= 0.00> <cols= 0> <al= 0.00> <DB=  405.8977> <mlp=  405.8977> <PB=Inf>
Fenchel cuts separation callback...
Cut separation callback adds 0 new essential cuts and 1 new facultative cuts.
avg. viol. = 0.21, max. viol. = 0.21, zero viol. = 0.
  <st= 1> <it=  1> <et= 1.29> <mst= 0.00> <sp= 0.00> <cols= 0> <al= 0.00> <DB=  407.3509> <mlp=  407.3509> <PB=Inf>
Fenchel cuts separation callback...
Cut separation callback adds 0 new essential cuts and 1 new facultative cuts.
avg. viol. = 0.15, max. viol. = 0.15, zero viol. = 0.
  <st= 1> <it=  1> <et= 1.29> <mst= 0.00> <sp= 0.00> <cols= 5> <al= 0.00> <DB=-15322.0149> <mlp=  886.3318> <PB=Inf>
  <st= 1> <it=  2> <et= 1.30> <mst= 0.00> <sp= 0.00> <cols= 4> <al= 0.00> <DB=  433.8362> <mlp=  444.2746> <PB=Inf>
  <st= 1> <it=  3> <et= 1.30> <mst= 0.00> <sp= 0.00> <cols= 3> <al= 0.00> <DB=  434.8000> <mlp=  440.3950> <PB=Inf>
  <st= 1> <it=  4> <et= 1.30> <mst= 0.00> <sp= 0.00> <cols= 2> <al= 0.00> <DB=  438.0050> <mlp=  440.3950> <PB=Inf>
  <st= 1> <it=  5> <et= 1.30> <mst= 0.00> <sp= 0.00> <cols= 4> <al= 0.00> <DB=  437.4383> <mlp=  440.3950> <PB=Inf>
  <st= 1> <it=  6> <et= 1.30> <mst= 0.00> <sp= 0.00> <cols= 1> <al= 0.00> <DB=  439.2200> <mlp=  440.3950> <PB=Inf>
  <st= 1> <it=  7> <et= 1.30> <mst= 0.00> <sp= 0.00> <cols= 1> <al= 0.00> <DB=  440.1325> <mlp=  440.3950> <PB=Inf>
  <st= 1> <it=  8> <et= 1.30> <mst= 0.00> <sp= 0.00> <cols= 0> <al= 0.00> <DB=  440.3950> <mlp=  440.3950> <PB=Inf>
Fenchel cuts separation callback...
Cut separation callback adds 0 new essential cuts and 0 new facultative cuts.
Cut separation callback adds 0 new essential cuts and 0 new facultative cuts.
[ Info: Heuristic Restricted Master IP found improving primal solution with value 444.40000000000003
──────────────────────────────────────────────────────────────────────────
                                 Time                    Allocations
                        ───────────────────────   ────────────────────────
   Tot / % measured:         3.20s /  40.8%            332MiB /  50.5%

Section         ncalls     time    %tot     avg     alloc    %tot      avg
──────────────────────────────────────────────────────────────────────────
Coluna               1    1.30s  100.0%   1.30s    168MiB  100.0%   168MiB
  SolveLpForm       31   8.70ms    0.7%   281μs   3.30MiB    2.0%   109KiB
──────────────────────────────────────────────────────────────────────────
[ Info: Terminated
[ Info: Primal bound: 444.40000000000003
[ Info: Dual bound: 440.395

Valid inequalities significantly improve the previous dual bound:

db2 = objective_bound(model)


db2

440.395

This page was generated using Literate.jl.