Implementing a model with column generation

Specific Domains Optimization (Mathematical)
1

Hello, I have the following model and want to solve it with column generation according to these instructions. Unfortunately, I am a complete coding newbie and wanted to ask if anyone would like to help me implement this model with column generation. I would be very grateful.

This is my code:

using JuMP
using Gurobi
using DataFrames

I_list = [1, 2, 3]
T_list = [1, 2, 3, 4, 5, 6, 7]
K_list = [1, 2, 3]
alpha=0.5
M = 10000
Max = 6

Demand_Dict = Dict(
    (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
)

# Create the model
model = Model(Gurobi.Optimizer)

# Decision variables
@variable(model, slack[t in T_list, s in K_list] >= 0)
@variable(model, motivation[i in I_list, t in T_list, s in K_list], Bin)
@variable(model, mood[i in I_list, t in T_list] >= 0)
@variable(model, x[i in I_list, t in T_list, s in K_list] >= 0)
@variable(model, y[i in I_list, t in T_list], Bin)

# Objective function
@objective(model, Min, sum(slack[t, s] for t in T_list, s in K_list))

# Constraints for demand
for (t, s) in keys(Demand_Dict)
    @constraint(model, slack[t, s] >= Demand_Dict[(t, s)] - sum(motivation[i, t, s] for i in I_list))
end

# Constraints for i in I_list:
for i in I_list
    @constraint(model, sum(y[i, t] for t in T_list) >= 4)
 for t in T_list
        @constraint(model, mood[i, t] == 1 - alpha * y[i, t])
        @constraint(model, sum(x[i, t, s] for s in K_list) == y[i, t])
        @constraint(model, sum(x[i, t, s] for s in K_list) <= 1)
        for s in K_list
            @constraint(model, motivation[i, t, s] >= mood[i, t] - M * (1 - x[i, t, s]))
            @constraint(model, motivation[i, t, s] <= mood[i, t] + M * (1 - x[i, t, s]))
            @constraint(model, motivation[i, t, s] <= x[i, t, s])
		end
    end
    for t in 1:(length(T_list) - Max)
        @constraint(model, sum(x[i, u, s] for s in K_list for u in t:(t + Max)) <= Max)
    end
end

# Solve the model
optimize!(model)
2

Is the current model too slow to solve?

What parts are you stuck on?

Rather than trying to write everything in one go, break it down into steps.

  • What is a column
  • Create an initial set of columns
  • Create the master using the initial set of columns
  • Write a pricing function which takes the dual from the master and returns a new column
  • Write the loop that iteratively solves the master and then generates a new column.

I also don’t think your formulation is exactly correct. Is motivation a variable in the master?