Operations Research 2025
Abstract Submission

235. Combining Benders Decomposition and Column Generation for Optimal Box Selection

Invited abstract in session WE-2: Decomposition Methods & Robust Optimization, stream Discrete and Combinatorial Optimization.

Wednesday, 16:30-18:00
Room: H4

Authors (first author is the speaker)

1. Pia Schreynemackers

Abstract

We consider a two-stage optimization problem with sparsity constraints, motivated by a common challenge in packaging logistics: minimizing the volume of transported air by optimizing the size and number of available packaging boxes, given the demand for order items.
In the first stage, we select the optimal sized packaging boxes. This stage is modeled as a binary selection problem, where the objective function is the value of the subproblem. In the second stage, the items demanded are assigned to the selected boxes. This stage is formulated as an assignment problem, with the goal of minimizing the unused volume in the selected boxes. The objective function in the second stage evaluates the quality of the item-to-box assignment. Additionally, we incorporate sparsity constraints in the first stage, which limit the number of different box types used in the assignment.
To solve this problem, we propose a cutting plane approach using Benders Decomposition in combination with Column Generation. In contrast to general Benders cuts, we can understand their meaning here and generate them by a purely combinatorial algorithm. This understanding allows us to apply Column Generation, as the coefficients of the constraints of the new variables also can be derived directly from the combinatorial structure. The combination of both known procedures therefore provides a particularly promising approach to this problem.

Keywords

Status: accepted

Back to the list of papers