Applied Optimization with Julia
Question: What are current trends in e-commerce?
Question: What is a split order?
. . .
Question: Why might they occur?
. . .
Question: What are the consequences?
. . .
Question: What are possible mitigations?
. . .
Key information about the case:
Question: What could be our objective?
We aim to improve the SKU2-warehouse allocation to minimize the number of split parcels resulting from SKUs being stored in different warehouses.
Question: What could be the sets here?
. . .
Question: What are possible parameters?
. . .
. . .
Question: What could the transactional data look like?
| \(t_{m,i}\) | A | B | C | D |
|---|---|---|---|---|
| 1 | 1 | 1 | 1 | 0 |
| 2 | 1 | 1 | 1 | 0 |
| 3 | 1 | 1 | 0 | 0 |
| 4 | 1 | 0 | 0 | 1 |
| 5 | 1 | 0 | 0 | 1 |
| 6 | 1 | 0 | 0 | 1 |
| 7 | 1 | 0 | 0 | 1 |
| 8 | 0 | 0 | 1 | 1 |
. . .
Question: What is your opinion on the assumption?
Question: What could be our decision variable/s?
. . .
. . .
. . .
Question: Anybody an idea what this could mean?
. . .
Focus on the warehouses and the co-appearance of SKUs! Discard the exact information about the customer orders.
Question: What could be the objective?
Maximize the coappearance of products that are often part of the same customer orders.
T = [
1 1 1 0;
1 1 1 0;
1 1 0 0;
1 0 0 1;
1 0 0 1;
1 0 0 1;
1 0 0 1;
0 0 1 1
]
# Create the coappearance matrix
Q = T' * T
println("Coappearance matrix Q:")
display(Q)Coappearance matrix Q:4×4 Matrix{Int64}:
7 3 2 4
3 3 2 0
2 2 3 1
4 0 1 5. . .
Question: What do the principal diagonal values tell us?
. . .
Question: What could be the sets?
. . .
. . .
We can focus on the SKUs and the warehouses, making the problem much smaller!
Question: What are possible parameters?
. . .
Instead of the transactional data, we just use the coappearance matrix in our model!
. . .
Maximize the coappearance of products that are often part of the same customer orders. In more mathematical terms: Maximize the sum of all unique pair-wise values \(q_{i,j}\) of all SKUs stored in the same warehouse.
. . .
Question: What could be our decision variable/s?
. . .
As we don’t need the customer order information, we only need to make a decision for each SKU and warehouse pair!
Question: How could we formulate the variable in Julia?
using JuMP, SCIP # SCIP is a non-commercial MIQCP solver
warehouses = ["Hamburg", "Berlin"] # Add warehouses as a vector
skus = ["Smartphone", "Socks", "Charger"] # Add SKUs as a vector
warehouse_model = Model(SCIP.Optimizer). . .
@variable(warehouse_model, X[i in skus, k in warehouses], Bin)2-dimensional DenseAxisArray{JuMP.VariableRef,2,...} with index sets:
Dimension 1, ["Smartphone", "Socks", "Charger"]
Dimension 2, ["Hamburg", "Berlin"]
And data, a 3×2 Matrix{JuMP.VariableRef}:
X[Smartphone,Hamburg] X[Smartphone,Berlin]
X[Socks,Hamburg] X[Socks,Berlin]
X[Charger,Hamburg] X[Charger,Berlin]Maximize the sum of all unique pair-wise values \(q_{i,j}\) of all SKUs stored in the same warehouse. Note, that this is a quadratic objective function!
. . .
Question: What could the objective function look like?
. . .
\[\text{maximize} \quad \sum_{i=2}^{\mathcal{I}} \sum_{j=1}^{i-1} \sum_{k \in \mathcal{K}} X_{ik}\times X_{jk} \times q_{ij}\]
. . .
The quadratic terms are \(X_{ik}\times X_{jk}\). This objective function is based on the Quadratic Multiple Knapsack Problem (QMKP), formulated by Hiley and Julstrom (2006).
Question: How could we formulate this in Julia?
. . .
Q = [2 1 2; 1 2 1; 2 1 2]
@objective(warehouse_model,
Max,
sum(
X[skus[i], warehouses[k]] * X[skus[j], warehouses[k]] * Q[i,j]
for i in 2:length(skus)
for j in 1:i-1
for k in 1:length(warehouses)
)
)X[Socks,Hamburg]*X[Smartphone,Hamburg] + X[Socks,Berlin]*X[Smartphone,Berlin] + 2 X[Charger,Hamburg]*X[Smartphone,Hamburg] + 2 X[Charger,Berlin]*X[Smartphone,Berlin] + X[Charger,Hamburg]*X[Socks,Hamburg] + X[Charger,Berlin]*X[Socks,Berlin]
Question: What constraints?
Ensure that each SKU is allocated at least once.
. . .
. . .
Question: What could the constraint look like?
\[\sum_{k \in \mathcal{K}} X_{ik} \geq 1 \quad \forall i \in \mathcal{I}\]
. . .
. . .
Question: How could we change the constraint to ensure that each SKU is allocated only once?
. . .
Question: How could we add the constraint in Julia?
@constraint(warehouse_model, single_allocation[i in skus],
sum(X[i, k] for k in warehouses) >= 1
)1-dimensional DenseAxisArray{JuMP.ConstraintRef{JuMP.Model, MathOptInterface.ConstraintIndex{MathOptInterface.ScalarAffineFunction{Float64}, MathOptInterface.GreaterThan{Float64}}, JuMP.ScalarShape},1,...} with index sets:
Dimension 1, ["Smartphone", "Socks", "Charger"]
And data, a 3-element Vector{JuMP.ConstraintRef{JuMP.Model, MathOptInterface.ConstraintIndex{MathOptInterface.ScalarAffineFunction{Float64}, MathOptInterface.GreaterThan{Float64}}, JuMP.ScalarShape}}:
single_allocation[Smartphone] : X[Smartphone,Hamburg] + X[Smartphone,Berlin] ≥ 1
single_allocation[Socks] : X[Socks,Hamburg] + X[Socks,Berlin] ≥ 1
single_allocation[Charger] : X[Charger,Hamburg] + X[Charger,Berlin] ≥ 1Ensure that the capacity of each warehouse is not exceeded.
. . .
. . .
Question: What could the second constraint be?
\[\sum_{i \in \mathcal{I}} X_{ik} \leq c_k \quad \forall k \in \mathcal{K}\]
. . .
And that’s basically it!
. . .
Question: How could we add the second constraint in Julia?
capacities = Dict("Hamburg" => 2, "Berlin" => 1) # Add capacities
@constraint(warehouse_model, capacity[k in warehouses],
sum(X[i, k] for i in skus) <= capacities[k]
)1-dimensional DenseAxisArray{JuMP.ConstraintRef{JuMP.Model, MathOptInterface.ConstraintIndex{MathOptInterface.ScalarAffineFunction{Float64}, MathOptInterface.LessThan{Float64}}, JuMP.ScalarShape},1,...} with index sets:
Dimension 1, ["Hamburg", "Berlin"]
And data, a 2-element Vector{JuMP.ConstraintRef{JuMP.Model, MathOptInterface.ConstraintIndex{MathOptInterface.ScalarAffineFunction{Float64}, MathOptInterface.LessThan{Float64}}, JuMP.ScalarShape}}:
capacity[Hamburg] : X[Smartphone,Hamburg] + X[Socks,Hamburg] + X[Charger,Hamburg] ≤ 2
capacity[Berlin] : X[Smartphone,Berlin] + X[Socks,Berlin] + X[Charger,Berlin] ≤ 1\[\text{maximize} \quad \sum_{i=2}^{\mathcal{I}} \sum_{j=1}^{i-1} \sum_{k \in \mathcal{K}} X_{ik}\times X_{jk} \times q_{ij}\]
subject to:
\[ \begin{align*} & \sum_{k \in \mathcal{K}} X_{ik} \geq 1 && \forall i \in \mathcal{I}\\ & \sum_{i \in \mathcal{I}} X_{ik} \leq c_{k} && \forall k \in \mathcal{K}\\ & X_{ik} \in \{0,1\} && \forall i \in \mathcal{I}, \forall k \in \mathcal{K} \end{align*} \]
set_attribute(warehouse_model, "display/verblevel", 0) # Hide solver output
optimize!(warehouse_model)
println("The optimal objective value is: ", objective_value(warehouse_model))
println("The optimal solution is: ", value.(X))The optimal objective value is: 2.0
The optimal solution is: 2-dimensional DenseAxisArray{Float64,2,...} with index sets:
Dimension 1, ["Smartphone", "Socks", "Charger"]
Dimension 2, ["Hamburg", "Berlin"]
And data, a 3×2 Matrix{Float64}:
1.0 0.0
-0.0 1.0
1.0 0.0. . .
Commercial solvers are faster and more robust as open source solvers but also more expensive. During your studies, you can use most of them for free though! Nonetheless, we will only use open source solvers in this course.
Questions: On model assumptions
. . .
Detect dependencies between products and allocate them accordingly, as products within orders can have dependencies and products are bought with different frequencies!
We now have covered the Quadratic Multiple Knapsack Problem and are ready to start solving some tasks in the upcoming tutorial.
For more interesting literature to learn more about Julia, take a look at the literature list of this course.