102. Column generation for a two-dimensional multi-criteria bin packing problem
Invited abstract in session TC-2: Integer Programming I, stream Discrete and Combinatorial Optimization.
Thursday, 11:45-13:15Room: H4
Authors (first author is the speaker)
| 1. | Christof Groschke
|
| iPattern institute, Niederrhein University of Applied Sciences | |
| 2. | Steffen Goebbels
|
| iPattern Institute, Faculty of Electrical Engineering and Computer Science, Niederrhein University of Applied Sciences | |
| 3. | Jochen Rethmann
|
| Faculty of Electrical Engineering and Computer Science, Niederrhein University of Applied Sciences |
Abstract
At the OR 2024 conference, we presented a mixed integer linear program (MIP) for a 2D bin packing problem in printed circuit board manufacturing. In this problem, rectangular printed circuit boards have to be packed into larger rectangular boards (bins) for production in a given multiplicity without overlapping and under certain distance constraints. Among other objectives, the number of bins, but also the number of different bin layouts, is to be minimized. Since the running times of the previously presented MIP are only acceptable for small problem instances, we now discuss a branch-and-price approach. We partition the search space by using an adapted Ryan-Foster-branching. In each node of the tree, we apply column generation. The columns that are iteratively added to a relaxed master problem represent different layouts. A pricing problem computes the layouts, separating the time-consuming constraints from the master problem.
Keywords
- Engineering Optimization
- Combinatorial Optimization
- Mixed-Integer Programming
Status: accepted
Back to the list of papers