Multi-Commodity Flow Problem (MCF) with Column Generation#

The Multi-Commodity Flow Problem is a classic optimization problem in operations research. It involves determining the optimal way to transport multiple distinct commodities through a shared network while minimizing costs, subject to constraints like capacity and demand. In this notebook, we specifically address the Minimum Cost Multi-Commodity Flow Problem, a variant of the MCF problem where the objective is to minimize the cost of the network flow. To provide a comprehensive understanding, we first solve the problem using a traditional approach, followed by a solution using the Column Generation method.

Problem Definition#

Given a network \(G = (V, E)\), where \(V\) represents the set of nodes (locations) and \(E\) represents the set of edges (connections), the problem involves determining the optimal flow of multiple commodities through the network. Each edge \((e \in E)\) has an associated capacity and cost, while each commodity \(k\) has specific demand requirements. The goal of this variant of MCF problem is to minimize the total cost of transporting all commodities while satisfying the following constraints:

  • Capacity Constraints: The total flow on any edge cannot exceed its capacity.

  • Demand Satisfaction: Each commodity must be transported from its source node to its sink node in the required quantity.

  • Flow Conservation: For any node other than the source or sink, the total inflow of a commodity must equal its total outflow.

Here is a mathematical formulation of MCF:#

Indices#

  • u, v: Nodes in the network.

  • k: Commodities being transported.

  • \(\mathbf{e_{u,v}}\): Edge connecting nodes u and v.

  • \(\mathbf{ks_{k,v}}\): Source node v of commodity k.

  • \(\mathbf{kt_{k,v}}\): Target/Sink node v of commodity k.

Parameters#

  • \(\mathbf{dem_k}\): Demand for commodity k.

  • \(\mathbf{cap_{u, v}}\): Capacity of edge (u, v) in the network.

  • \(\mathbf{c_{k, u, v}}\): Cost of transporting one unit of commodity k across edge (u, v).

Decision Variable#

  • \(\mathbf{x_{k, u, v}}\): Flow of commodity k on edge \({e_{u,v}}\).

\begin{align} & \underset{x}{\min} \qquad \sum_k \sum_e c_{k,e} \cdot x_{k,e} \\[1ex] & \text{s.t.} \nonumber \\[1ex] & \sum_k x_{k,u,v} \leq cap_{u,v} \qquad \forall u,v \\[1ex] & \sum_{e_{u,v} ~ | ~ ks_{k,u}} x_{k,e} - \sum_{e_{v,u} ~ | ~ ks_{k,u}} x_{k,e} = dem_{k} \qquad \forall k \\[1ex] & \sum_{e_{u,v} ~ | ~ kt_{k,u}} x_{k,e} - \sum_{e_{v,u} ~ | ~ kt_{k,u}} x_{k,e} = - dem_{k} \qquad \forall k \\[1ex] & \sum_{e_{u,v}} x_{k,e} = \sum_{e_{v,u}} x_{k,e} \qquad \forall k, v ~ | ~ \notin ks_{k,v} \wedge \notin kt_{k,v} \\[1ex] & x_{k,u,v} \geq 0 \qquad \forall k, u, v \\[1ex] \end{align}

  1. Objective Function: Minimize the total transportation cost by summing the cost of flows for all commodities over all edges.

  2. Capacity Constraint: The total flow on each edge for all commodities cannot exceed the edge’s capacity.

  3. Source Node Flow Conservation: The net flow at the source node of a commodity equals the demand for that commodity (outflow matches demand).

  4. Sink Node Flow Conservation: The net flow at the sink node of a commodity equals the negative of the demand (inflow matches demand).

  5. Intermediate Node Flow Conservation: For all intermediate nodes, the flow into the node must equal the flow out of the node for all commodities.

  6. Non-negativity constraint.

Network

[31]:

# Import required libraries

import networkx as nx
from gamspy import Container
from gamspy import Set
from gamspy import Alias
from gamspy import Parameter
from gamspy import Variable
from gamspy import Equation
from gamspy import Sum
from gamspy import Model
from gamspy import Ord
from gamspy import Card
from gamspy import Problem
from gamspy import Sense
from gamspy import Number

1. Prepare data#

[32]:

nodes = [f"n{i}" for i in range(1, 6)]
commodities = [f"k{i}" for i in range(1, 5)]
edges = [
    ("n1", "n2"),
    ("n1", "n3"),
    ("n1", "n4"),
    ("n2", "n3"),
    ("n2", "n4"),
    ("n3", "n4"),
    ("n3", "n5"),
    ("n4", "n5"),
]

sources = [("k1", "n1"), ("k2", "n1"), ("k3", "n2"), ("k4", "n3")]
targets = [("k1", "n4"), ("k2", "n5"), ("k3", "n5"), ("k4", "n5")]

dem = [
    ("k1", 15),
    ("k2", 25),
    ("k3", 10),
    ("k4", 5),
]

cap = [
    ("n1", "n2", 20),
    ("n1", "n3", 10),
    ("n1", "n4", 15),
    ("n2", "n3", 10),
    ("n2", "n4", 15),
    ("n3", "n4", 30),
    ("n3", "n5", 15),
    ("n4", "n5", 30),
]

edge_cost = [
    ("k1", "n1", "n2", 1),
    ("k1", "n1", "n3", 5),
    ("k1", "n1", "n4", 15),
    ("k1", "n2", "n3", 1),
    ("k1", "n2", "n4", 4),
    ("k1", "n3", "n4", 8),
    ("k1", "n3", "n5", 5),
    ("k1", "n4", "n5", 3),
    ("k2", "n1", "n2", 1),
    ("k2", "n1", "n3", 3),
    ("k2", "n1", "n4", 13),
    ("k2", "n2", "n3", 4),
    ("k2", "n2", "n4", 4),
    ("k2", "n3", "n4", 8),
    ("k2", "n3", "n5", 7),
    ("k2", "n4", "n5", 5),
    ("k3", "n1", "n2", 1),
    ("k3", "n1", "n3", 1),
    ("k3", "n1", "n4", 12),
    ("k3", "n2", "n3", 3),
    ("k3", "n2", "n4", 4),
    ("k3", "n3", "n4", 9),
    ("k3", "n3", "n5", 4),
    ("k3", "n4", "n5", 2),
    ("k4", "n1", "n2", 1),
    ("k4", "n1", "n3", 2),
    ("k4", "n1", "n4", 11),
    ("k4", "n2", "n3", 2),
    ("k4", "n2", "n4", 4),
    ("k4", "n3", "n4", 6),
    ("k4", "n3", "n5", 8),
    ("k4", "n4", "n5", 3),
    ]

2. Build Model - Traditional Multi-Commodity Problem#

[33]:

m = Container()

[34]:

# SETS
v  = Set(m, "v",  records=nodes,  description="Nodes")
k  = Set(m, "k",  records=commodities,  description="Commodities")
e  = Set(m, "e",  [v, v], records=edges, description="Edges")
ks = Set(m, "ks", [k, v], records=sources, description="Commodity Sources")
kt = Set(m, "kt", [k, v], records=targets, description="Commodity Sinks")

u = Alias(m, "u", v)

[35]:

# PARAMETERS
cost = Parameter(m, "cost", [k, v, v], edge_cost, description="Cost of transporting one unit of K_i on edge (u, v)")
demand = Parameter(m, "demand", k, dem, description="Demand for each commodity")
capacity = Parameter(m, "capacity", [v, v], cap, description="Capacity of edge (u, v)")

# VARIABLE #
x = Variable(m, name="x", domain=[k, u, v], type="Positive", description="Flow of commodity k on edge (u, v)")

[36]:

# EQUATIONS #

cap_cons = Equation(m, name="cap_cons", domain=[u, v], description="Capacity constraint for edge (u,v)")
cap_cons[u, v] = Sum(k, x[k, u, v]) <= capacity[u, v]


flow_balance_inter = Equation(m, name="flow_balance_inter", domain=[k, v], description="Flow conservation for intermediate nodes")
flow_balance_inter[k, v].where[(~ks[k, v]) & (~kt[k, v])] = Sum(e[u, v], x[k, e]) == Sum(e[v, u], x[k, e])


flow_balance_src = Equation(m, name="flow_balance_src", domain=k, description="Flow conservation at source node")
flow_balance_src[k] = (Sum(e[u, v].where[ks[k, u]], x[k, e]) - Sum(e[v, u].where[ks[k, u]], x[k, e]) == demand[k])


flow_balance_snk = Equation(m, name="flow_balance_snk", domain=k, description="Flow conservation at sink node")
flow_balance_snk[k] = (Sum(e[u, v].where[kt[k, u]], x[k, e]) - Sum(e[v, u].where[kt[k, u]], x[k, e]) == -demand[k])

[37]:

mcf = Model(m, name="mcf", equations=m.getEquations(), problem="LP", sense=Sense.MIN, objective=Sum([k, e[u, v]], cost[k, e] * x[k, e]))
mcf.solve()
print("Solution Status:", mcf.status)
print("Objective Value:", mcf.objective_value)

Solution Status: ModelStatus.OptimalGlobal
Objective Value: 580.0

[38]:

def read_solution(df, cost):
    solution = {}

    # For each commodity (k1, k2, etc.)
    for commodity in df.columns:
        flows = []
        # Get non-zero flows
        non_zero_flows = df[df[commodity] > 0]
        for (source, target), flow in non_zero_flows[commodity].items():
            e_cost = [edge[3] for edge in cost
                        if edge[0] == commodity
                        and edge[1] == source
                        and edge[2] == target][0]
            flows.append({
                'from': source,
                'to': target,
                'amount': flow,
                'cost': flow * e_cost
            })

        if flows:
            solution[commodity] = flows

    # Print readable output
    for commodity, move_data in solution.items():
        print(f"\n{'-'*20}")
        print(f"{commodity}: ${sum([flow['cost'] for flow in move_data])}")
        for flow in move_data:
            print(f"  {flow['from']} → {flow['to']}: {flow['amount']} (${flow['cost']})")

read_solution(x.pivot(index=["u", "v"], columns=["k"]), edge_cost)


--------------------
k1: $100.0
  n1 → n2: 15.0 ($15.0)
  n2 → n3: 5.0 ($5.0)
  n2 → n4: 10.0 ($40.0)
  n3 → n4: 5.0 ($40.0)

--------------------
k2: $370.0
  n1 → n3: 10.0 ($30.0)
  n1 → n4: 15.0 ($195.0)
  n3 → n5: 10.0 ($70.0)
  n4 → n5: 15.0 ($75.0)

--------------------
k3: $65.0
  n2 → n3: 5.0 ($15.0)
  n2 → n4: 5.0 ($20.0)
  n3 → n5: 5.0 ($20.0)
  n4 → n5: 5.0 ($10.0)

--------------------
k4: $45.0
  n3 → n4: 5.0 ($30.0)
  n4 → n5: 5.0 ($15.0)

Limitations of the Traditional Multi-Commodity Flow Problem Formulation#

The traditional edge-based formulation of the Multi-Commodity Flow Problem (MCF) is straightforward and intuitive but faces significant challenges when applied to large-scale networks:

  1. Scalability Issues: The number of decision variables increases rapidly with the size of the network (nodes, edges, and commodities).

  2. Memory Overhead: Large-scale problems require significant memory to store the decision variables and constraints.

Path Formulation of MCF#

The path-based formulation offers an alternative by focusing on complete paths that commodities can take between their source and sink. While this approach provides a clearer view of commodity flows, it introduces a new challenge:
The number of possible paths in a network grows exponentially with its size. For large-scale problems, considering all possible paths explicitly becomes computationally infeasible.

Column Generation for Path-Based MCF#

To address the impracticality of handling all paths simultaneously, Column Generation provides a more efficient framework. Instead of starting with all possible paths, the method begins with a Restricted Master Problem (RMP) that considers only a subset of feasible paths. New paths are then generated dynamically as needed. This approach focuses computational effort on the most relevant paths, making the solution process scalable.

How Column Generation Works?#

Column Generation is an iterative optimization method that alternates between two key steps:

  1. Solving the Restricted Master Problem (RMP):

    • The RMP is solved using a limited set of paths.

    • Dual variables from the RMP are used to calculate the reduced costs of potential new paths.

  2. Solving the Pricing Problem:

    • A shortest path problem (or its equivalent) is solved to identify new paths with negative reduced cost.

    • If such paths are found, they are added to the RMP, and the process repeats.

  3. Stopping Criterion:

    • The algorithm terminates when no new paths with negative reduced cost can be identified.

Advantages of Column Generation in Path-Based MCF#

  • Reduced Problem Size:

    • By starting with a limited set of paths, the initial problem is significantly smaller and more manageable.

  • Dynamic Path Generation:

    • New paths are only added when they have the potential to improve the solution, ensuring computational efficiency.

Column Generation thus transforms the path-based formulation into a scalable and efficient approach for solving large-scale MCF problems.

Defining Initial and Possible Paths#

To start the Column Generation (CG) algorithm, we require a feasible solution as a starting point. This is achieved by defining initial paths that connect the source node to the sink node for each commodity. These initial paths ensure the problem is solvable from the outset, even if some paths are not practically feasible. But the following points need to be considered:

  1. Cost Handling:

    • If a path between the source and sink of a commodity exists in the network (as per the problem’s data), the actual cost from the problem is used.

    • If a path between the source and sink does not exist, a very high cost is assigned to discourage its use in the solution.

  2. Purpose of Initial Paths:

    • To guarantee a feasible solution to the Restricted Master Problem (RMP) at the start of the column generation process.

    • To serve as the baseline for generating improved paths iteratively.

Function to process columns generated by the pricing problem#

[39]:

def process_solution(sol, source, sink):
    filtered = [(item[0], item[1]) for item in sol if item[2] != 0.0]   # Filter out elements with zero values
    G = nx.DiGraph()
    G.add_edges_from(filtered)
    all_paths = list(nx.all_simple_paths(G, source, sink))  # Get all paths from source to sink

    # Convert paths from node lists to edge lists to match GAMSPy format
    formatted_paths = []
    for path in all_paths:
        edge_path = []
        for i in range(len(path) - 1):
            edge_path.append((path[i], path[i + 1], 1))
        formatted_paths.append(edge_path)
    return formatted_paths

[40]:

# Define possible paths: A set to track all paths that can be dynamically added during column generation
possible_paths = [f"p{i}" for i in range(1, 51)]

# Initial paths from source to sink for each commodity (Used to obtain a feasible solution)
initial_paths = [
    ("p1", "n1", "n4", 1),
    ("p2", "n1", "n5", 1),
    ("p3", "n2", "n5", 1),
    ("p4", "n3", "n5", 1),
]

# Each path belongs to one commodity (based on source -> sink)
path_k_map = [
    ("k1", "p1", 1),
    ("k2", "p2", 1),
    ("k3", "p3", 1),
    ("k4", "p4", 1),
]

# Update the previous data to add direct edges. Since edges (1,4) and (3,5) already exist, we will only add the other direct edges; (1,5) and (2,5)
edges.extend([("n1", "n5"), ("n2", "n5")])

# For the new edges, we will add the capacity just enough for each commodity to flow through (equal its demand)
cap.extend([("n1", "n5", 25), ("n2", "n5", 10)])

# For the new edges, we will add the cost as 1000 for each commodity to discourage the use of these edges later
edge_cost.extend([
    ("k1", "n1", "n5", 1000), ("k1", "n2", "n5", 1000),
    ("k2", "n1", "n5", 1000), ("k2", "n2", "n5", 1000),
    ("k3", "n1", "n5", 1000), ("k3", "n2", "n5", 1000),
    ("k4", "n1", "n5", 1000), ("k4", "n2", "n5", 1000),
    ])

[41]:

# Update existing symbols
e.setRecords(edges)         # Update the set of edges
capacity.setRecords(cap)    # Update the capacity of edges
cost.setRecords(edge_cost)  # Update the cost of edges


# Define new symbols from the updated data
p  = Set(m, "p", records=possible_paths, description="Set of all possible paths in the network")
pp = Set(m, "pp", p, description="Dynamic subset of p, containing only currently active paths")

# Select the first |k| paths (one per commodity) as the initial active set
pp[p] = Ord(p) <= Card(k)

# Parameters related to paths and commodities
paths       = Parameter(m, "paths", [p, v, v], initial_paths, description="All paths")
p_k_map     = Parameter(m, "p_k_map", [k, p], path_k_map, description="1 if path p is used for commodity k, 0 otherwise")

Restricted Master Problem (RMP)#

In the Column Generation framework, the Restricted Master Problem (RMP) is the core optimization problem that we iteratively solve.

The RMP starts with a limited subset of paths and solves the multi-commodity flow problem over these paths. These paths are dynamically updated during the column generation process by adding new paths with negative reduced costs obtained from the pricing problem.

The RMP’s mathematical model:#

We add the following Indices:#

  • \(\mathbf{p}\): Set of all possible paths in the network

  • \(\mathbf{pp}\): Dynamic subset of p, containing only currently active paths

We add the following Parameters#

  • \(\mathbf{Path_{p, e}}\): 1 if edge \(e\) is in path \(p\), 0 otherwise.

  • \(\mathbf{Pk_{k, p}}\): 1 if path \(p\) is used for commodity \(k\), 0 otherwise.

Decision Variable#

  • \(\mathbf{f_{k, p}}\): Flow of commodity \(k\) on path \(p\).

\begin{align} & \underset{f}{\min} \qquad \sum_k \sum_{pp} (\sum_e Path_{pp, e} \cdot c_{k, e}) \cdot f_{k, pp} \\[1ex] & \text{s.t.} \nonumber \\[1ex] & \sum_k \sum_{pp} Path_{pp, e} \cdot f_{k, pp} \leq Cap_e \qquad \forall e \\[1ex] & \sum_{pp} Pk_{k,pp} \cdot f_{k,pp} \geq Dem_k \qquad \forall k \\[1ex] & f_{k,p} \geq 0 \qquad \forall k, p \\[1ex] \end{align}

  1. Objective Function: Minimize the total transportation cost by summing up the cost of flows \(f_{k,p}\) of all commodities k on their respective paths p.

  2. Capacity Constraint: Ensure the total flow of all commodities on each edge e does not exceed the edge’s capacity.

  3. Demand Satisfaction Constraint: Guarantee that the total flow of each commodity k on all paths satisfies the commodity’s demand.

  4. Non-negativity constrint.

Restricted Master Problem - Path formulation of MCF Problem#

[42]:

# VARIABLES
f = Variable(m, name="f", type="positive", domain=[k,p], description="Flow of commodity k on path p")
z = Variable(m, name="z", type="free", description="Total transportation cost")


# EQUATIONS
rmp_obj = Equation(m, name="rmp_obj", description="Objective function (minimize total cost)")
cap_constraint = Equation(m, name="cap_constraint", domain=[v,v], description="Capacity constraint for each edge")
demand_constraint = Equation(m, name="demand_constraint", domain=k, description="Demand constraint for each commodity")

rmp_obj[...] = z == Sum([k, pp], Sum(e, paths[pp, e] * cost[k, e]) * f[k, pp])
cap_constraint[e[u, v]] = - Sum([k, pp], paths[pp, e] * f[k, pp]) >= - capacity[e]
demand_constraint[k] = Sum(pp, p_k_map[k, pp] * f[k, pp]) >= demand[k]


# Initialize the model
rmp = Model(m, name="rmp", problem=Problem.LP, sense=Sense.MIN, equations=[rmp_obj, cap_constraint, demand_constraint], objective=z)

Pricing problem - Shortest path model#

The pricing problem is a crucial part of the column generation framework. Its purpose is to identify new paths with negative reduced cost for each commodity. If such a path is found, it is added to the Restricted Master Problem (RMP) to improve the solution. If no such paths exist, the column generation process terminates.

The mathematical model is defined as follows:#

\begin{align} & \underset{y}{\min} \qquad - (D * \alpha) + \sum_e (c_e + \beta_e) \cdot y_e \\[1ex] & \text{s.t.} \nonumber \\[1ex] & \sum_{e_{s,v}} y_e = D \\[1ex] & \sum_{e_{u,t}} y_e = D \\[1ex] & \sum_{e_{v,u}} y_e - \sum_{e_{u,v}} y_e = 0 \qquad \forall v ~ | ~ \notin s_{v} \wedge \notin t_{v} \\[1ex] & y_{u,v} \geq 0 \qquad \forall u,v \\[1ex] \end{align}

  1. Objective Function: Minimize the reduced cost of the path. α is the marginal of the demand constraint and β is the marginal of the capacity constraint.

  2. Source Constraint: Ensure the total flow leaving the source node equals the demand for the commodity.

  3. Sink Constraint: Ensure the total flow entering the sink node equals the demand for the commodity.

  4. Intermediate Node Flow Conservation: Ensure the flow entering any intermediate node equals the flow leaving that node, maintaining flow conservation throughout the path.

  5. Non-negativity constraint.

[43]:

# Sets
s = Set(m, name="s", domain=v, description="Source node")
t = Set(m, name="t", domain=v, description="Sink   node")

# Parameters
sub_cost   = Parameter(m, name="sub_cost", domain=[v,v])
sub_demand = Parameter(m, name="sub_demand")
alpha      = Parameter(m, name="alpha")

# Variables
y = Variable(m, name="y", type="positive", domain=[u,v], description="New path")

# Equations
pricing_obj    = Equation(m, name="pricing_obj", description="Objective function for shortest path")
pricing_cap = Equation(m, name="pricing_cap", domain=[u,v], description="Capacity constraint for edge (u,v)")
pricing_source = Equation(m, name="pricing_source", description="Flow conservation at source node")
pricing_target = Equation(m, name="pricing_target", description="Flow conservation at target node")
pricing_flow   = Equation(m, name="pricing_flow", domain=v, description="Flow conservation at intermediate nodes")


pricing_obj[...] = z == - (alpha * sub_demand) + Sum(e, (sub_cost[e] + cap_constraint.m[e]) * y[e])
pricing_cap[e[u,v]] = y[e] <= capacity[e]
pricing_source[...] = Sum(e[s, v], y[e]) == sub_demand
pricing_target[...] = Sum(e[u, t], y[e]) == sub_demand
pricing_flow[v].where[(~s[v]) & (~t[v])] = Sum(e[v, u], y[e]) == Sum(e[u, v], y[e])


# Initialize the model
pricing = Model(m, name="pricing", problem=Problem.LP, equations=[pricing_obj, pricing_cap, pricing_source, pricing_target, pricing_flow], sense=Sense.MIN, objective=z)

Solving with Column Generation#

[44]:

# Initialization
pi    = Set(m, name="pi", domain=p, description="set of the last path")
pi[p] = Ord(p) == Card(pp) + 1

has_negative_reduced_cost = True  # A flag to track negative reduced costs
path_no = len(pp)  # Number of initial paths


# Run as long as we have negative reduced costs
while has_negative_reduced_cost:

    rmp.solve()

    for commodity in k.toList():
        s[v] = ks[commodity, v]
        t[v] = kt[commodity, v]
        sub_cost[e] = cost[commodity, e]
        alpha[...] = demand_constraint.m[commodity]
        sub_demand[...] = demand[commodity]

        pricing.solve()

        # path that might improve the master model found
        if pricing.objective_value < -0.0001:
            new_paths = process_solution(y.toList(), s.toList()[0], t.toList()[0])
            for path in new_paths:
                path = [(pi.toList()[0],) + edge for edge in path]
                initial_paths.extend(path)
                paths.setRecords(initial_paths)
                p_k_map[commodity, pi] = Number(1)
                pp[pi] = True
                pi[p] = pi[p.lag(1)]

    # if no new paths are added (lengths are equal), the flag turns to False
    has_negative_reduced_cost = path_no != len(pp)
    path_no = len(pp)

[45]:

rmp.solve()
print("Solution Status:", rmp.status)
print("Objective Value:", rmp.objective_value)
read_solution((f.pivot() @ paths.pivot(index=["p_0"], columns=["v_1", "v_2"])).T.sort_index(level=0), edge_cost)

Solution Status: ModelStatus.OptimalGlobal
Objective Value: 580.0

--------------------
k1: $100.0
  n1 → n2: 15.0 ($15.0)
  n2 → n4: 10.0 ($40.0)
  n2 → n3: 5.0 ($5.0)
  n3 → n4: 5.0 ($40.0)

--------------------
k2: $370.0
  n1 → n4: 15.0 ($195.0)
  n1 → n3: 10.0 ($30.0)
  n3 → n5: 10.0 ($70.0)
  n4 → n5: 15.0 ($75.0)

--------------------
k3: $65.0
  n2 → n4: 5.0 ($20.0)
  n2 → n3: 5.0 ($15.0)
  n3 → n5: 5.0 ($20.0)
  n4 → n5: 5.0 ($10.0)

--------------------
k4: $45.0
  n3 → n4: 5.0 ($30.0)
  n4 → n5: 5.0 ($15.0)

For those interested in exploring column generation in more detail, the foundational work by Desrosiers and Lübbecke provides an excellent introduction and comprehensive overview of the technique, its principles, and its applications. You can refer to:

Desrosiers, J., & Lübbecke, M. E. (2006). A Primer in column generation. Column Generation, 1–32. https://doi.org/10.1007/0-387-25486-2_1