💻 computer science

Stepwise Composition of Heuristic Components for Offline Strip Packing: A Controlled Study of Batch Reinforcement Learning

This controlled study demonstrates that while batch reinforcement learning for stepwise heuristic composition in offline strip packing yields modest, statistically significant improvements over static portfolios, its performance remains inferior to budgeted local search and offers limited advantage over well-tuned static configurations.

Original authors: Wenru Lin, Zhouwang Yang, Lei Liu

Published 2026-10-12

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Wenru Lin, Zhouwang Yang, Lei Liu

Original paper licensed under CC BY 4.0 (https://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine a factory floor where a machine must cut a long, wide sheet of metal into a specific set of rectangular pieces. The goal is simple: fit every piece onto the sheet without any overlap, using as little vertical space as possible. This is a classic puzzle known as strip packing. For decades, engineers have relied on "constructive heuristics"—simple, fast rules that place one piece at a time, always choosing the best spot available at that exact moment. These rules are like a skilled worker who never looks ahead but makes the best decision for the piece in hand. Over time, researchers have created many variations of these rules, and the standard practice has been to run all of them on a problem and simply keep the best result. This works well, but it is wasteful; it builds the same layout many times over, hoping one of the static rules happens to fit the current puzzle perfectly.

The question researchers asked was whether a computer could learn to be smarter than a static rule. Instead of picking one rule and sticking with it, could a computer learn to switch between different rules as it builds the layout, changing its strategy based on how the pieces are currently arranged? This is the promise of reinforcement learning, a type of artificial intelligence where a system learns by trial and error to make a sequence of decisions. The researchers wanted to see if a computer could learn to compose these simple rules step-by-step, adapting its choices in real-time to create a better packing than any single fixed rule could achieve on its own.

To test this, the team built a learning system that acted as a conductor for a set of existing, well-known packing rules. They trained this system on thousands of practice puzzles using a method called batch reinforcement learning, which learns from a fixed set of past experiences rather than exploring the world in real-time. The system was designed to look at the current state of the packing—how much space was left, the shape of the gaps, and the size of the remaining pieces—and decide which rule to apply next. They tested this on a large collection of standard test cases, comparing the learning system against the best static rules and against a "portfolio" approach where the computer simply runs many different static rules and picks the winner.

The results revealed a nuanced picture of what learning can and cannot do in this field. When the learning system was used on its own, without any safety net, it performed worse than the best single static rule. It struggled to find a perfect strategy from scratch. However, when the researchers let the learning system act as a helper to the established static rules, it added a small but measurable improvement. By switching between rules at the right moments, the learning system helped the static shells produce slightly tighter packings. This gain was consistent and statistically significant, proving that the system was indeed making useful, state-dependent decisions rather than just guessing randomly. Crucially, the study found that this composition gain itself remained robust, replicating significantly on a completely new set of puzzles.

Yet, the story takes a sharp turn when cost and efficiency are considered. The researchers found that the learning system was incredibly expensive to run. The computer time required to make its decisions was so high that, even with its slight improvement in packing quality, it was outperformed by a much simpler approach: a basic local search. This simpler method, which involves taking a good static solution and making small, random swaps to improve it, achieved far better results in a fraction of the time. In fact, the local search method was so efficient that it dominated the learning system across every budget tested. The learning system's high cost was partly due to a technical artifact in how the computer code was running, which inflated the time measurements, but even after correcting for this, the learning approach remained too slow to be practical compared to the simpler search methods.

The study also uncovered that the learning system's specific advantage over simpler switching strategies was not as robust as hoped. While it outperformed random switching and simple open-loop strategies on the data it was trained on, this advantage did not fully replicate on the new puzzles. On these new puzzles, a simple, pre-planned schedule of rule switches caught up to the complex learning system, performing marginally better on one of the test shells and indistinguishably on the other. This suggests that while the learning system successfully learned to combine rules effectively, its specific ability to outperform a simple pre-planned schedule via state-dependent decisions was not a universal truth that generalized to all new situations.

Ultimately, the paper concludes that while learning to switch rules step-by-step is a fascinating idea that can squeeze out a tiny bit of extra efficiency, it is not a silver bullet. The most effective approach for this problem remains a combination of running a few different static rules and using a fast, budgeted local search to refine the best result. The learning system, despite its sophistication, could not compete with the speed and reliability of these simpler, established methods. The research serves as a careful reality check, showing that in the world of packing puzzles, the most powerful tool is often not the most complex one, but the one that balances quality with the cost of computation.

Technical Summary: Stepwise Composition of Heuristic Components for Offline Strip Packing

Problem Definition
The paper addresses the offline two-dimensional strip packing problem (2DSP), an NP-hard problem requiring the placement of a set of rectangles into a fixed-width, open-topped strip to minimize the total used height. The study focuses on constructive skyline heuristics, which place items one by one in a single pass. While existing literature has established that no single variant of these heuristics dominates across all instances, static "shells" like BBF (enumerating 288 strategy combinations) and TWBF (18 ordering $\times$ policy combinations) have been used to select the best static configuration per instance.

The central research question is whether a learned controller can adaptively compose these same heuristic components (item-selection rules and placement policies) step-by-step within a single construction pass, reacting to the current partial layout (state), rather than selecting a single static configuration for the entire instance.

Methodology
The authors employ Batch Reinforcement Learning (RL) to train a controller that selects action pairs (selection rule $\times$ placement policy) at each construction step.

MDP Formulation:
- State/Observation: The policy observes a 15-dimensional compressed feature vector ( $\phi(x_t)$ ) derived from the skyline shape, remaining items, and progress metrics. This constitutes a Partially Observable MDP (POMDP).
- Actions: 9 discrete actions formed by the Cartesian product of 3 item-selection rules (widest-fit, first-fit, fitness-number) and 3 placement policies (LM, TN, SN).
- Reward: A dense, telescoping reward is used, defined as the negative increment of the "waste-identity" ( $\Phi_t = W \cdot H_t - A_t$ ) normalized by the lower bound. This ensures the cumulative return aligns directly with minimizing the final construction height (before post-processing).
Learning Algorithm: The study utilizes Fitted Q Iteration (FQI) with tree-based ensemble regressors (histogram gradient boosting). The training uses a fixed dataset of transitions collected from behavior episodes (random, BF-like, and S2-like policies).
Safety Fallback: The deployed artifact is an ensemble: the learned policy is paired with a "safety fallback" (the best fixed configuration found on the training fold). The final output is the minimum height of the two.
Experimental Design:
- Data: 224 development instances (families C, BKW, NT, PV) and 160 untouched final test instances.
- Controls: The study pre-registered a rigorous control battery to isolate the value of state-dependent learning from mere diversity or switching. Controls include:
  - Random stepwise switching.
  - Stateless frequency-matched sampling.
  - Fixed open-loop stage tables.
  - Train-selected static configurations.
  - Equal-CPU-budget comparisons against random restarts and local search.
- Cost Accounting: A critical methodological control involves capping native threads (OpenMP) to one during inference to eliminate "thread-churn" artifacts that artificially inflate CPU time measurements for tree-based models.

Key Results

Standalone Performance: The raw learned constructor (without fallback) does not outperform the best single fixed configuration. It trails the best fixed configuration (7.90% vs 7.26% mean gap). The reported "fourth place" performance (5.74%) belongs to the two-member fallback ensemble, not the learned policy alone.
Composition Gains: When integrated into published shells (TWBF-18 and BBF-288), the learned policy adds statistically significant but practically modest value.
- On the 104-instance classical subset, adding the learned policy reduces the mean gap by 0.305 points for TWBF-18 and 0.163 points for BBF-288.
- The augmented BBF-288 shell achieves a 4.405% gap, numerically lower than the strong baseline FH (4.501%), though the difference is not statistically significant.
Mechanism Validation (Development Set): On the development set, the composition gain significantly exceeds all control arms (random switching, stateless sampling, open-loop tables). This suggests the gain is driven by state-dependent, closed-loop decisions rather than just switching diversity or marginal action frequencies.
Mechanism Validation (Final Set): On the untouched final test set, the advantage of the learned policy over the open-loop stage table diminishes. The open-loop table catches up and marginally exceeds the learned policy on TWBF-18, indicating the closed-loop advantage does not generalize robustly to new distributions in this specific setting.
Cost and Efficiency:
- Inference Tax: The raw measured CPU time for the learned policy was inflated by a factor of ~488 due to OpenMP thread-churn in the tree ensemble. After capping threads, the inference time dropped by 94.6%.
- Budgeted Search Dominance: Even with corrected CPU costs, the learned policy is never cost-competitive. A simple random-swap local search with a "not-worse" acceptance criterion, given the same CPU budget as the learned policy's inference, achieves a mean gap of 1.873% (vs. 4.405% for the augmented shell). At 0.2s/instance, local search achieves 2.963%, outperforming all constructive methods and shells tested.
- Static Portfolios: A train-selected static portfolio of 12 configurations achieves a lower mean gap (4.238%) at roughly one-tenth the CPU cost of the augmented BBF-288 shell.

Significance and Claims
The paper claims to provide the first controlled study of stepwise, batch-RL composition for offline strip packing using named classic components. Its significance lies in:

Establishing Limits: It demonstrates that while learned composition offers a statistically significant complementarity to static shells, the gains are small and do not overcome the performance of simple, budgeted local search or well-tuned static portfolios.
Methodological Rigor: It highlights the importance of pre-registered control batteries to distinguish between genuine state-dependent learning and spurious gains from diversity or switching.
Cost Accounting: It identifies and quantifies a specific "inference tax" artifact in tree-based RL (OpenMP thread-churn) and argues that future learning-based packing papers must report thread-controlled CPU times to avoid distorted cost claims.
Modest Conclusions: The authors explicitly state that the learned policy does not beat the best fixed configuration on its own, and that the "closed-loop" advantage observed on the development set did not replicate on the final set. The primary contribution is mapping the precise boundaries where stepwise composition adds value (modest complementarity) and where it fails (cost-competitiveness and generalization of state-dependence).

Technical Summary: Stepwise Composition of Heuristic Components for Offline Strip Packing

More like this