AI will know more about programming. It didn’t bite on my suggestion for heuristic simulated annealing with any substantial code output for efficiency, but will continue on the assumption provided to it that the AI will not be able to solve this alone.
o1-preview
1. Polynomial Time Approximation Algorithm with Bounded Ratio
The problem you’ve described is an instance of the Two-Dimensional Cutting Stock Problem, which is known to be NP-hard. However, there exists a polynomial-time approximation algorithm called the First-Fit Decreasing Height (FFDH) algorithm that can be applied to this problem. The FFDH algorithm has an approximation ratio of 1.7, meaning the solution it provides will use no more than 1.7 times the optimal number of panels.
FFDH Algorithm Steps:
- Sort Rectangles: Arrange all required pieces in decreasing order of their heights (keeping widths associated).
- Initialize Shelves: Start with a new panel and create horizontal shelves from top to bottom.
- Place Rectangles:
- Place rectangles onto the current shelf from left to right until no more rectangles fit in terms of width.
- If a rectangle doesn’t fit on the current shelf, start a new shelf below the current one.
- The height of each shelf is determined by the tallest rectangle on that shelf.
- Manage Panels:
- If the cumulative height of shelves exceeds the panel’s height, start packing in a new panel.
Application to Your Problem:
-
Rectangles Sorted by Height:
| Size (Width x Height) |
Quantity |
| 85 x 20 |
6 |
| 80 x 20 |
16 |
| 70 x 20 |
16 |
| 35 x 50 |
8 |
| 45 x 45 |
8 |
-
Packing Process:
- Panel 1:
- Shelf 1 (Height 85): Place 6 pieces of 85 x 20.
- Panel 2:
- Shelf 2 (Height 80): Place 7 pieces of 80 x 20.
- Panel 3:
- Shelf 3 (Height 80): Place remaining 9 pieces of 80 x 20 (7 on Shelf 3, 2 on Shelf 4).
- Shelf 4 (Height 80): Place 2 pieces of 80 x 20 and 5 pieces of 70 x 20.
- Panel 4:
- Shelf 5 (Height 70): Place remaining 11 pieces of 70 x 20.
- Shelf 6 (Height 70): Place 4 pieces of 70 x 20 and 2 pieces of 35 x 50.
- Panel 5:
- Shelf 7 (Height 50): Place 4 pieces of 35 x 50.
- Shelf 8 (Height 50): Place 2 pieces of 35 x 50 and 1 piece of 45 x 45.
- Panel 6:
- Shelf 9 (Height 45): Place 3 pieces of 45 x 45.
- Shelf 10 (Height 45): Place 3 pieces of 45 x 45.
- Panel 7:
- Shelf 11 (Height 45): Place remaining 1 piece of 45 x 45.
-
Result: Using the FFDH algorithm, all pieces can be cut from 7 panels, which is within the 1.7 approximation ratio of the optimal solution.
2. Heuristic Annealing Algorithmic Solution
While the FFDH algorithm provides a good approximation, further optimization can be achieved using heuristic methods like Simulated Annealing. This probabilistic technique searches for a global optimum by allowing occasional uphill moves (worse solutions) to escape local minima.
Simulated Annealing Steps:
- Initial Solution: Start with a feasible solution (e.g., the one provided by FFDH).
- Define Cost Function: The cost can be based on the number of panels used and total waste.
- Neighbor Solutions: Generate neighboring solutions by swapping pieces between shelves or rearranging the cutting patterns.
- Acceptance Criterion:
- If the new solution has a lower cost, accept it.
- If the new solution is worse, accept it with a probability that decreases over time (controlled by a “temperature” parameter).
- Cooling Schedule: Gradually decrease the temperature to reduce the acceptance of worse solutions over time.
- Termination: Stop when the system has sufficiently “cooled” or after a fixed number of iterations.
Benefits:
- Flexibility: Can handle complex constraints and objective functions.
- Optimization: Often finds better solutions than basic heuristics, potentially reducing the number of panels used.
3. Python Code for Performing the Calculation
Below is a Python implementation of the FFDH algorithm applied to your problem. This code models the panels, shelves, and pieces, and attempts to pack the pieces efficiently.
import math
# Define the dimensions of the panels
PANEL_WIDTH = 150
PANEL_HEIGHT = 150
# Define the pieces required
pieces = [
{'width': 20, 'height': 85, 'quantity': 6},
{'width': 20, 'height': 80, 'quantity': 16},
{'width': 20, 'height': 70, 'quantity': 16},
{'width': 35, 'height': 50, 'quantity': 8},
{'width': 45, 'height': 45, 'quantity': 8}
]
# Expand the pieces into a list
rectangles = []
for piece in pieces:
for _ in range(piece['quantity']):
rectangles.append({'width': piece['width'], 'height': piece['height']})
# Sort rectangles by decreasing height
rectangles.sort(key=lambda x: x['height'], reverse=True)
# Function to pack rectangles using FFDH
def pack_rectangles(rectangles):
panels = []
current_panel = []
current_shelf = {'height': 0, 'width_used': 0, 'rectangles': []}
current_height = 0
for rect in rectangles:
# Check if rectangle fits in current shelf
if (current_shelf['width_used'] + rect['width'] <= PANEL_WIDTH) and (rect['height'] <= current_shelf['height']):
# Place rectangle in current shelf
current_shelf['rectangles'].append(rect)
current_shelf['width_used'] += rect['width']
else:
# Start a new shelf if rectangle height is less than panel height
if rect['height'] <= PANEL_HEIGHT - current_height:
# Finish current shelf and start a new one
if current_shelf['rectangles']:
current_panel.append(current_shelf)
current_height += current_shelf['height']
current_shelf = {'height': rect['height'], 'width_used': rect['width'], 'rectangles': [rect]}
else:
# Start a new panel
if current_panel:
panels.append(current_panel)
current_panel = []
current_height = 0
current_shelf = {'height': rect['height'], 'width_used': rect['width'], 'rectangles': [rect]}
# Check if current panel is full
if current_height + current_shelf['height'] > PANEL_HEIGHT:
panels.append(current_panel)
current_panel = []
current_height = 0
# Add the last shelf and panel
if current_shelf['rectangles']:
current_panel.append(current_shelf)
if current_panel:
panels.append(current_panel)
return panels
# Pack the rectangles
panels = pack_rectangles(rectangles)
# Print the result
print(f"Total panels used: {len(panels)}\n")
for i, panel in enumerate(panels):
print(f"Panel {i+1}:")
panel_height = 0
for shelf in panel:
print(f" Shelf (Height {shelf['height']}):")
shelf_width = 0
for rect in shelf['rectangles']:
print(f" Rectangle {rect['width']}x{rect['height']}")
shelf_width += rect['width']
print(f" Shelf width used: {shelf_width}/{PANEL_WIDTH}")
panel_height += shelf['height']
print(f" Panel height used: {panel_height}/{PANEL_HEIGHT}\n")
Explanation of the Code:
- Data Preparation:
- The required pieces are expanded into a list of rectangles.
- Rectangles are sorted in decreasing order of height.
- Packing Function (
pack_rectangles):
- Iterates over each rectangle and attempts to place it on the current shelf.
- If it doesn’t fit, it tries to create a new shelf.
- If the shelf doesn’t fit in the current panel, it starts a new panel.
- Output:
- Prints the total number of panels used.
- Details each panel, shelf, and rectangles within.
Notes:
- Assumptions:
- Rectangles cannot be rotated.
- All cuts are straight and from one side to the other (guillotine cuts).
- Extensions:
- The code can be extended with optimization heuristics like Simulated Annealing.
- Additional constraints (e.g., kerf width, grain direction) can be incorporated.
Conclusion:
By applying the FFDH algorithm, we achieve a feasible solution within a known approximation ratio. For further optimization, heuristic methods like Simulated Annealing can be employed to potentially reduce the number of panels used and minimize waste.
