Portfolio of Solving Strategies in CEGAR-based Object Packing and Scheduling for Sequential 3D Printing

This paper presents Portfolio-CEGAR-SEQ, a parallelized algorithm that leverages modern multi-core CPUs and a portfolio of diverse object arrangement strategies to outperform the original CEGAR-SEQ method in solving the combinatorial challenges of object arrangement and scheduling for sequential 3D printing, often resulting in more efficient use of printing plates.

The Gist

Imagine you have a 3D printer. In the old days, if you wanted to print 20 small toys, the printer would build them all at the same time, layer by layer. It would print a bit of Toy A, then a bit of Toy B, then a bit of Toy C, all together.

But there's a problem with this "all-at-once" method:

1. The "Stringy" Mess: The printer head has to jump back and forth between toys constantly, leaving ugly strings of plastic behind.
2. The "One Bad Apple" Risk: If the printer jams on Toy #15, you have to scrap the entire batch of 20 toys because they are all stuck together in the same printing cycle.

The Solution: The "One-by-One" Strategy
This paper proposes a smarter way: Sequential Printing. Instead of building all toys together, the printer finishes Toy A completely, then moves on to Toy B, then Toy C.

• The Benefit: If Toy A fails, you only lose Toy A. The others are safe.
• The Catch: This is a massive puzzle. When the printer is working on Toy B, Toy A is already sitting there, finished and hard. The printer's arm (the extruder) must move around Toy A without crashing into it to get to Toy B. It's like trying to park a car in a garage that is already full of other cars, but you have to park them one by one without hitting the ones already there.

The Problem: The "Parking Lot" Puzzle

The author, Pavel, is trying to solve a math problem: How do you arrange a bunch of 3D objects on a flat square plate so they can be printed one after another without the printer crashing?

This is a "combinatorial nightmare." There are billions of ways to arrange the objects. If you try to calculate the perfect arrangement for a huge batch of objects, a standard computer might take years to figure it out.

The Old Way: The "Single-Track" Thinker

The previous method (called CEGAR-SEQ) was like a very smart but single-minded librarian.

• It had one specific rule: "Always try to put the books (objects) in the center of the shelf (printing plate) because the middle is usually the most stable."
• It would try to solve the puzzle using this one rule. If it failed, it would try again, tweaking the numbers slightly.
• The Flaw: Modern computers have many "brains" (multi-core CPUs). The old method only used one brain at a time, leaving the rest of the computer idle. It was like having a team of 8 chefs but only letting one cook while the others watched.

The New Way: The "Strategy Portfolio"

The author introduces a new algorithm called Portfolio-CEGAR-SEQ.

Think of this like a Tournament of Chefs.
Instead of asking one chef to cook the perfect meal, you hire 20 different chefs. Each chef has a slightly different philosophy:

• Chef 1: "I put everything in the center."
• Chef 2: "I put everything in the top-right corner."
• Chef 3: "I put everything in the bottom-left corner."
• Chef 4: "I print the shortest objects first."
• Chef 5: "I print the tallest objects first."

How it works:

1. Parallel Processing: The computer fires up all 20 "chefs" (strategies) at the exact same time, using all the cores of the modern CPU.
2. The Race: They all race to solve the packing puzzle.
3. The Winner: As soon as one of them finds a solution that fits the objects onto the plate without crashing, the computer stops the others and says, "Great job! That's the one we'll use."

Why is this a big deal?

The experiments showed that this "Tournament" approach is a game-changer:

• Speed: Because it uses all the computer's power at once, it finds solutions much faster.
• Efficiency: Sometimes, the "Center" chef fails to fit all the objects on one plate, requiring a second plate. But the "Corner" chef might find a way to fit them all on just one plate.
• Real World Impact: If you are a 3D printing farm operator, saving one printing plate means you save time, electricity, and plastic. For a large batch of 30 printer parts, the old method might need 7 plates, while the new "Portfolio" method only needs 6. That's a huge saving when you are printing hundreds of items.

The Bottom Line

This paper is about taking a very hard math problem (fitting 3D objects on a plate without crashing) and solving it by harnessing the full power of modern computers. Instead of relying on one "best guess" strategy, the new system runs a whole team of different strategies simultaneously, picks the winner, and helps 3D printers work faster, safer, and more efficiently.

In short: It's like upgrading from a single detective solving a crime to a whole SWAT team searching every room at once, ensuring the job gets done perfectly and quickly.

Technical Summary

1. Problem Definition

The paper addresses the Sequential Object Packing and Scheduling (SEQ-PACK+S) problem in Fused Deposition Modeling (FDM) 3D printing. Unlike standard 3D printing where all objects are printed layer-by-layer simultaneously, sequential printing completes objects one by one.

Key Challenges:

• Collision Avoidance: As objects are printed sequentially, previously printed objects remain on the build plate. The print head (extruder), gantry, and cables must navigate around these completed objects without colliding.
• Continuous & Discrete Complexity: The problem involves determining continuous positions ($X, Y$) for objects and a discrete temporal ordering ($\pi$) of printing.
• Optimization: The goal is to fit a batch of objects onto the minimum number of printing plates while ensuring the print head can traverse vertically over completed objects to reach the next one.
• Computational Hardness: The problem is NP-hard (a generalization of rectangle packing). Previous solutions using the CEGAR-SEQ algorithm translate the problem into a linear arithmetic formula solved by an SMT solver (Z3), but this approach runs in a single-threaded mode, failing to utilize modern multi-core CPUs effectively.

2. Methodology

The authors propose Portfolio-CEGAR-SEQ, a high-level parallelization strategy that runs multiple instances of the CEGAR-SEQ algorithm simultaneously with different heuristic configurations.

A. Mathematical Formalization

The problem is modeled using:

• Objects ($O$): A set of 3D shapes.
• Extruder ($E$): Modeled as a moving volume (including the nozzle, gantry, and cables).
• Constraints:
  1. Sequential Non-Colliding: If object $i$ is printed before $j$, the extruder moving to print $j$ must not intersect with the volume of $i$.
  2. Printing Plate Requirement: All objects must fit within the plate boundaries.
  3. Extruder Traversability: The extruder must be able to lift vertically above an object to move to the next position.
• Optimization: The algorithm attempts to shrink the effective printing plate area (scaling factor $\sigma$) to find the tightest packing.

B. The Portfolio Approach

Instead of relying on a single heuristic, the authors define a Composite Strategy consisting of two orthogonal components:

1. Tactic (Object Arrangement): Determines where on the plate objects are placed.
   • Center: Places objects toward the center (original strategy, optimized for heated bed uniformity).
   • Corner Strategies: Places objects toward specific corners (e.g., Max-X/Min-Y), exploiting modern enclosed printers where heat distribution is more uniform.
2. Ordering (Object Selection): Determines the sequence in which objects are selected for a specific plate.
   • Height-based: Shortest-to-tallest, Tallest-to-shortest.
   • Random: Random selection.
   • Input: Order of arrival.

The Portfolio-CEGAR-SEQ algorithm (Algorithm 2) iterates through the Cartesian product of these tactics and orderings (creating up to 20 composite strategies). These instances are executed in parallel on a multi-core CPU. The system returns the best solution found among all parallel threads.

3. Key Contributions

• Parallelization of CEGAR-SEQ: The authors successfully parallelized the solving process at the algorithmic level (portfolio approach) rather than the low-level solver level. This avoids the exponential complexity issues of fine-grained parallelization.
• New Heuristic Strategies: They introduced alternative placement tactics (corner-based) and ordering strategies (height-based) that were previously unexplored in this context.
• Composite Strategy Framework: They demonstrated that combining different tactics and orderings creates a synergistic effect, often outperforming any single strategy.
• Implementation: The algorithm is implemented in C++ and utilizes the Z3 SMT solver.

4. Experimental Results

Experiments were conducted on an AMD Ryzen 7 2700 (8 cores) using two datasets: random cuboids and complex 3D printer parts.

• Solver Comparison (Z3 vs. Gecode):

  • The SMT-based approach (Z3) significantly outperformed the CSP-based approach (Gecode) in both success rate and runtime.
  • Z3 could solve instances with ~30 objects within a 60-second timeout, whereas Gecode failed beyond ~25 objects. Z3's use of rational domains provided higher accuracy than Gecode's integer millimeter resolution.

• Portfolio Performance:

  • Runtime: Running 20 composite strategies in parallel increased the wall-clock time only moderately (acceptable factor) compared to a single run, due to efficient multi-core utilization.
  • Solution Quality (Number of Plates):
    • For small batches, the Combined Portfolio (all 20 strategies) significantly reduced the number of printing plates required compared to the original CEGAR-SEQ.
    • In a specific test with 30 printer parts, the original CEGAR-SEQ required 7 plates, while Portfolio-CEGAR-SEQ reduced this to 6 plates.
  • Synergy: The "Tactic" component (arrangement strategy) provided the most significant individual benefit, but combining it with "Ordering" strategies yielded the best overall results.

5. Significance

• Operational Efficiency: Reducing the number of printing plates required for a batch directly saves time, material, and energy for 3D printing operators.
• Hardware Utilization: The approach effectively leverages the parallelism of modern consumer-grade CPUs, which was previously underutilized by sequential SMT solvers.
• Robustness: Sequential printing inherently improves robustness (if one object fails, others can continue) and print quality (reduced stringing from fewer head movements). This algorithm makes sequential printing more viable for large batches by solving the complex collision avoidance problem efficiently.
• Future Work: The authors suggest integrating object rotation directly into the formal model and using heuristic solutions to initialize the solver for further performance gains.

In conclusion, Portfolio-CEGAR-SEQ represents a significant advancement in 3D printing optimization, transforming a computationally difficult combinatorial problem into a tractable task by leveraging parallel computing and diverse heuristic portfolios.