Imagine you are an employee in the glass industry tasked with producing rectangular pieces from large glass sheets. You have a few variable-sized glass sheets with different sizes and costs, and you’ve received orders that require 100 rectangular pieces, each with its width and height. You need to perform guillotine cuts (edge-to-edge) on the large glass sheets to produce the required small rectangular items, while minimizing production costs. Now, if someone gives you a book of patterns, where each pattern is a feasible configuration of some items in one of the glass sheets, you only need to select a set of patterns that contains each item at least once and minimize the total cost. To find these patterns, we use a matheuristic approach, which is a hybrid method that combines mathematical programming and heuristic techniques to solve optimization problems.
The matheuristic algorithm we developed is designed to solve the Variable-Sized 2-Dimensional Bin Packing Problem through an iterative process that involves exploring a set of feasible packings and adjusting their configuration to optimize the cost function. The algorithm employs the Dantzig Wolfe decomposition technique to initialize the feasible packings dataset and computes ceiling and floor ratios based on its properties.
During the exploration phase, a subset of packings is released, and a Mixed Integer Model is utilized to calculate the tentative cost and assignments of the released items. The algorithm selects the assignments that result in a lower cost than the current configuration. Subsequently, the tentative assignments guide the construction of a feasible packing.
If the packing’s ratio exceeds the ceiling ratio, the packing is fixed and eliminated from the pool of feasible packings, which triggers a recursive call to explore the remaining set. Our approach helps to efficiently find an (near) optimal packing solution while considering the practical constraints of the glass industry.
In conclusion, the Variable-Sized 2-Dimensional Bin Packing Problem is a challenging optimization problem with many possible solutions. The matheuristic approach provides a powerful tool for solving this problem, using a combination of mathematical programming and heuristic techniques. By exploring only potentially feasible packings and enforcing constraints on the objective function value, the algorithm can find some good patterns that we can use in Dantzig-Wolfe formulation to improve the solution in reasonable amount of time.
Xiaojuan He
Deakin University
