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

Pavel Surynek

cs.AIMar 12, 2026

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

Authors: Pavel Surynek

Organizations: Faculty of Information Technology, Czech Technical University in Prague, Thákurova 9, 160 00 Praha 6, Czechia

Abstract

Computing power that used to be available only in supercomputers decades ago especially their parallelism is currently available in standard personal computer CPUs even in CPUs for mobile telephones. We show how to effectively utilize the computing power of modern multi-core personal computer CPU to solve the complex combinatorial problem of object arrangement and scheduling for sequential 3D printing. We achieved this by parallelizing the existing CEGAR-SEQ algorithm that solves the sequential object arrangement and scheduling by expressing it as a linear arithmetic formula which is then solved by a technique inspired by counterexample guided abstraction refinement (CEGAR). The original CEGAR-SEQ algorithm uses an object arrangement strategy that places objects towards the center of the printing plate. We propose alternative object arrangement strategies such as placing objects towards a corner of the printing plate and scheduling objects according to their height. Our parallelization is done at the high-level where we execute the CEGAR-SEQ algorithm in parallel with a portfolio of object arrangement strategies, an algorithm is called Porfolio-CEGAR-SEQ. Our experimental evaluation indicates that Porfolio-CEGAR-SEQ outperforms the original CEGAR-SEQ. When a batch of objects for multiple printing plates is scheduled, Portfolio-CEGAR-SEQ often uses fewer printing plates than CEGAR-SEQ.

Figures & tables

Panel of Figure 1 — Fig. 1 : Standard 3D printing slice by slice and sequential 3D printing where objects are completed one by one shown in Prusa Slicer [ 5 ] . The ordering of objects for sequential printing is shown by numbers. Printer extruder and gantry must avoid previously printed objects in the sequential case (printing of the last object is shown). The sequential arrangement and schedule has been obtained by the CEGAR-SEQ algorithm [ 6 ] .

Fig. 2 : Object arrangement strategies (tactics): (i) objects are placed towards the center of the printing plate

P_{P}

( Center tactic), (ii) objects are placed towards the maximum

x

and minimum

y

coordinates w.r.t.

P_{P}

( Max-X-Min-Y tactic).

Panel of Figure 3 — Fig. 3 : Comparison of solving SEQ-PACK+S by the Gecode solver and the z3 solver on random cuboids on a 200mm $\times$ 200mm plate. The right part shows cactus plots of runtimes (lower plot is better).

Fig. 4 : Sorted runtimes of Portfolio-CEGAR-SEQ with various portfolios on printer parts.

Panel of Figure 5 — Fig. 5 : Average number of printing plates used by a sub-optimal variant of Portfolio-CEGAR-SEQ under four different portfolios of composite strategies.

Fig. 6 : Histogram of the number of plates used by a sub-optimal variant of Portfolio-CEGAR-SEQ under four different portfolios of composite strategies.

Panel of Figure 7 — Fig. 7 : The benefit of portfolio-based sequential print scheduling for 30 pieces of printer parts - left: the standard parallel printing. Middle: objects scheduled sequentially by the previous CEGAR-SEQ (7 plates used). Right: objects scheduled sequentially by Portfolio-CEGAR-SEQ (6 plates used).

Algorithm Selection

Algorithm selection predicts which solver, model, or strategy will work best for a given instance, context, or computational budget.

See all 50 papers

Sequential Object Placement Optimization with Convex Decomposition
Aug 25, 2026Yuezhe Zhang, Xiangyu Lyu, Sohan Rudra +2Combinatorial Optimization Robotic Manipulation
Interactive Robot Perception & Learning, Technical Univsersity of Darmstadt, Germany · Intelligent Autonomous Systems, Technical Univsersity of Darmstadt, Germany · Robotics and Semantic Systems, Lund University, Sweden +1
PyCSP3-Scheduling: A Scheduling Extension for PyCSP3
May 14, 2026Sohaib AfifiConstraint Programming
Univ. Artois, UR 3926, Laboratoire de Génie Informatique et d’Automatique de l’Artois (LGI2A), F-62400 Béthune, France
Differentiable Initialization-Accelerated CPU-GPU Hybrid Combinatorial Scheduling
Mar 30, 2026Mingju Liu, Jiaqi Yin, Alvaro Velasquez +1Combinatorial Optimization Integer Linear Programming
University of Maryland, College Park, Maryland, USA · University of Colorado, Boulder, Colorado, USA

Aug 25, 2026J/K move · Enter open · S save

Sequential Object Placement Optimization with Convex Decomposition

Yuezhe Zhang, Xiangyu Lyu, Sohan Rudra, Davide Tateo+1

Interactive Robot Perception & Learning, Technical Univsersity of Darmstadt, Germany · Intelligent Autonomous Systems, Technical Univsersity of Darmstadt, Germany · Robotics and Semantic Systems, Lund University, Sweden+1

Combinatorial Optimization Robotic Manipulation

Open paper AskPDF arXiv

Robotic object packing has been a core challenge for robotic deployment in logistics, industry, etc., due to the curse of dimensionality in combinatorial search and the difficulty of dealing with dynamic collision constraints for irregularly shaped objects. Current heuristic and learning-based methods mainly assume a limited spatial discretization resolution of space, and computation becomes extremely inefficient as discretization accuracy increases. In this work, we eliminate this assumption by introducing SOPO-CD, which frames sequential object placement as a differentiable nonlinear optimization problem with hard constraints in a decomposed free space. We formulate the constraints of placing a convex object inside a convex hull as constraining the vertices of the object to lie inside the convex hull. The constraints and their derivatives can be written in closed form and calculated efficiently. We implement a custom solver that achieves local-optimal placements within tightly constrained space in milliseconds; a

50 \times

speedup compared to a fine-grained grid search method. We evaluate our framework on 2D Tangram, 2D Tetris, and 3D Bin Packing, and have demonstrated strong computational performance and packing utility. We also demonstrate its real-world applicability for solving the Tangram puzzle using a robot equipped with a dexterous hand.

Abstract

Algorithm Selection

Explore similar work

Sequential Object Placement Optimization with Convex Decomposition

PyCSP3-Scheduling: A Scheduling Extension for PyCSP3

Differentiable Initialization-Accelerated CPU-GPU Hybrid Combinatorial Scheduling