EN
by Chahira Mourad and Tim Varelmann
On a brisk December evening at the North Pole, Santa's workshop is alive with activity. The elves are working tirelessly to ensure every gift is wrapped and ready for delivery. However, Santa is facing a logistical challenge: his stock of gift-wrap rolls is running critically low. With Christmas Eve fast approaching, Santa must determine the most efficient way to wrap all the presents while minimizing waste and avoiding unnecessary costs. How can he optimize his resources?
The cutting stock problem is a well-known optimization problem in operations research. The goal is to optimize resource usage by reducing leftovers and maximizing efficiency. It aims to answer the question:
How can we divide large units of material into smaller pieces to meet demand while minimizing the number of raw material units used?
This problem has significant applications in industries like manufacturing and textiles, where minimizing waste is crucial for cost efficiency. For instance, a factory might need to cut large sheets of steel into parts for machinery or divide rolls of fabric into sections for clothing. The objective remains consistent: meet the demand for smaller pieces using the least material possible.
In Santa’s case, the rolls of gift-wrap paper are the raw materials, and the gifts represent the demand. Each type of gift—ranging from postcards to XXL presents—requires a specific length of wrapping paper. Santa’s challenge is to minimize the number of rolls used while ensuring every gift is wrapped. All of Santa's rolls have the same width. We assume that the Christmas Elves are skillful enough in their wrapping technique that the seven gift types can all be wrapped with that width, and we therefore focus only on optimizing the length of the cuts that are required.
Santa’s biggest challenge lies with the XXL presents, which require 15 meters of wrapping paper each. This nearly consumes an entire roll, leaving minimal room for other gifts. The elves view the XXL presents as the dooming threat in Santa’s otherwise manageable wrapping dilemma. Could Santa still meet the wrapping demands without exceeding the available rolls?
To better understand the problem, here’s a detailed breakdown of the required wrapping paper:
By incorporating this data into his model, Santa gains a clearer picture of the constraints and opportunities to optimize his resources. He can use at most 20 gift wraps!
To tackle this challenge, Santa translates the problem into a mathematical model, where every constraint and variable mirrors the wrapping workshop’s realities. Santa utilizes the Python library Pyomo to formulate and solve the problem.
Before defining the decision variables, objective, and constraints, Santa’s model relies on the following data:
• Roll Length: The total length of each roll of gift-wrap paper.
• Number of Rolls: The total number of gift-wrap rolls available.
• Gift Types: A list of all gift categories, each requiring a specific amount of wrapping paper per unit.
• Demand for Each Gift Type: The total number of units required for each gift category.
This data serves as the foundation for the model, ensuring that all constraints and objectives align with the real-world parameters of Santa’s wrapping challenge. You can explore the full code for Santa’s optimization problem here available on my GitLab page. If you're curious how many rolls Santa would need for your gifts, try the code yourself and experiment with different inputs!
• giftToRoll: Represents how many pieces of a particular gift type are cut from a specific roll. It is defined for every pair of (giftType, giftRoll).
• useRoll: A binary variable (0 or 1) that indicates whether a roll is used. It is defined for every giftRoll.
The objective is to minimize the total number of rolls used, ensuring an efficient allocation of resources.
1. Every Gift Must Be Wrapped: Each gift type must receive enough wrapping paper to cover all required gifts.
2. Roll Length Limits: The total length of wrapping paper cut from any roll cannot exceed the roll’s length.
3. Usage Restriction: A roll can only be considered used if it contributes to wrapping at least one gift.
This structured approach ensures that Santa’s resources are utilized efficiently while respecting all constraints.
After formulating the model, Santa uses an optimization solver to find the best solution. This process highlights key concepts in optimization:
A problem is deemed infeasible when no solution satisfies all constraints. For example, if Santa does not have enough rolls to wrap all the gifts, or if a single XXL present requires more wrapping paper than the length of any roll, the solver will flag the problem as infeasible. In such cases, Santa must either acquire additional rolls or adjust the requirements to make the problem solvable.
A feasible solution satisfies all constraints, meaning that every gift is wrapped and no roll is overused. However, feasibility does not guarantee efficiency. For instance, using 10 rolls when it’s possible to wrap all the gifts with only 7 rolls is feasible but suboptimal.
An optimal solution minimizes resource usage while meeting all constraints. For Santa, this means determining the smallest number of rolls needed to wrap all the gifts. The solver might conclude: "Santa needs to use at least 7 rolls of gift-wrap paper to meet the demand." This optimal solution ensures both efficiency and sustainability.
In Santa's case, he ended up needing 4 gift wrapping rolls to cover all the gifts he needs to deliver. Specifically, the solver showed Santa the exact way to divide the wrapping rolls he has in order to minimize waste and consequently the number of used gift wraps.
With the help of mathematical optimization, Santa’s workshop successfully overcomes the wrapping crisis. The cutting stock problem, though widely applied in industrial settings, proves invaluable for solving Santa’s holiday logistics challenge. By minimizing waste and maximizing efficiency, Santa ensures every child receives their gift while managing resources responsibly.
This example underscores the power of mathematical models in addressing real-world challenges, whether in a factory or at the North Pole. The next time you find yourself wrapping presents or cutting materials, remember Santa and his optimization elves. With a little math and a touch of holiday cheer, you too can find the most efficient solution!
