Help with column generation implementation

Specific Domains Optimization (Mathematical)
1

Hello, i am currently working on a column generation model which i would like to solve with gurobi in Julia. As i am a total newbie, i dont really know where to start. This is the model i would like to implement.PDF

This is my code for the basic model so far. As i mentioned above, i dont really know how to start and therefore i havent decomposed the code in MP and SP and also didnt try to solve it. I would really appreciate help to setup a working column generation model. Thanks

using JuMP, Gurobi

m = Model(solver = GurobiSolver())

# Sets
T = 1:8
S = 1:4
I = 1:4
M = 100
alpha = 0.5

# Demand
demand = Dict(((t,s),val) for (t,s,val) in [(1,1,2), (1,2,1), (1,3,0), (2,1,1), (2,2,2), (2,3,0), (3,1,1), (3,2,1), (3,3,1), (4,1,1), (4,2,2), (4,3,0), (5,1,2), (5,2,0), (5,3,1), (6,1,1), (6,2,1), (6,3,1), (7,1,0), (7,2,3), (7,3,0)])

#Decision variables
@variable(m, slack[t in T, s in S] >= 0, continuous)
@variable(m, motivation[i in I, t in T, s in S] >= 0, ub = 1, continuous)
@variable(m, mood[i in I, t in T] >= 0, ub = 1, continuous)
@variable(m, x[i in I, t in T, s in S] >= 0, bin)

# Objective function
@objective(m, Min, sum(slack[t, s] for t in T, s in S))

# Constraints
for t in T, s in S
    @constraint(m, sum(motivation[i, t, s] for i in I) + slack[t, s] == demand[(t,s)])
end
for i in I, s in S, t in T
    @constraint(m, mood[i,t] + M * (1 - x[i, t, s]) >= motivation[i, t, s])
    @constraint(m, motivation[i, t, s] >= mood[i, t] - M * (1 - x[i, t, s]))
    @constraint(m, motivation[i, t, s] <= x[i, t, s])
end
for i in I, t in T
    @constraint(m, mood[i, t] == 1 - alpha * sum(x[i, t, s] for s in S))
end

# Solve
optimize!(m)

println("Optimal objective value: ", objective_value(m))
println("slack: ", slack.value)
println("motivation: ", motivation.value)
println("mood: ", mood.value)
println("x: ", x.value)#=
2

Hi @Carl_Baier, welcome to the forum (and to JuMP!)

There are quite a few things to fix in your example, so here’s how I would write your model.

using JuMP, Gurobi

T = 1:7  # 1:8 doesn't match `demand`?
S = 1:3  # 1:4 doesn't match demannd?
I = 1:4
M = 100
alpha = 0.5
demand = Dict(
    (t, s) => val for (t, s, val) in [
        (1,1,2), (1,2,1), (1,3,0),
        (2,1,1), (2,2,2), (2,3,0), 
        (3,1,1), (3,2,1), (3,3,1),
        (4,1,1), (4,2,2), (4,3,0),
        (5,1,2), (5,2,0), (5,3,1),
        (6,1,1), (6,2,1), (6,3,1),
        (7,1,0), (7,2,3), (7,3,0),
    ]
)

model = Model(Gurobi.Optimizer)
@variables(model, begin
    slack[t in T, s in S] >= 0
    0 <= motivation[i in I, t in T, s in S] <= 1
    0 <= mood[i in I, t in T] <= 1
    x[i in I, t in T, s in S], Bin
end)
@objective(model, Min, sum(slack))
@constraints(model, begin
    [t in T, s in S], sum(motivation[:,t,s]) + slack[t,s] == demand[(t,s)]
    [i in I, s in S, t in T], mood[i,t] + M * (1 - x[i,t,s]) >= motivation[i,t,s]
    [i in I, s in S, t in T], motivation[i,t,s] >= mood[i,t] - M * (1 - x[i,t,s])
    [i in I, s in S, t in T], motivation[i,t,s] <= x[i,t,s]
    [i in I, t in T], mood[i,t] == 1 - alpha * sum(x[i,t,:])
end)
optimize!(model)
println("Optimal objective value: ", objective_value(model))
println("slack: ", value.(slack))
println("motivation: ", value.(motivation))
println("mood: ", value.(mood))
println("x: ", value.(x))

Other good places to start are:

There is a tutorial which walks through column generation:

1 Like