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

Read PDF
Ask AI
Cite

Copy citation

DOINot available for this paper

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

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 PPP_{P} ( Center tactic), (ii) objects are placed towards the maximum xx and minimum yy coordinates w.r.t. PPP_{P} ( Max-X-Min-Y tactic).
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.
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.
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).
More in this topic

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

Explore similar work

CardsList
Aug 25, 2026

Sequential Object Placement Optimization with Convex Decomposition

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×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.

Yuezhe Zhang, Xiangyu Lyu, Sohan Rudra +2

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 OptimizationRobotic Manipulation
AskPDF
May 14, 2026

PyCSP3-Scheduling: A Scheduling Extension for PyCSP3

PyCSP3^3 provides a productive way to build constraint models for solving combinatorial constrained problems and export them to XCSP3^3, preserving a complete separation between modeling and solving. However, it lacks native support for scheduling abstractions such as interval variables, sequence variables, and resource functions. As a result, scheduling models must be encoded with low-level integer variables and manual channeling constraints, even though PyCSP3^3 already provides global constraints like NoOverlap and Cumulative on integer arrays. We present PyCSP3^3 Scheduling, a library that adds scheduling abstractions to PyCSP3^3 through 53 dedicated constraints and 27 expressions, and compiles them down to standard PyCSP3^3/XCSP3^3 constraints, maintaining the modeling/solving separation that underpins the PyCSP3^3 ecosystem. On 261 paired instances across 17 model families (5 runs each), both formulations produce identical objectives on all 72 doubly-proved optimal pairs and nearly half of the families (8/17) remain structurally unchanged after compilation; however, runtime performance diverges across families, with clear gains on some (up to 5.8x) and regressions on others due to the overhead of compilation decompositions. Code and benchmarks are available at: https://github.com/sohaibafifi/pycsp3-scheduling

Sohaib Afifi

Univ. Artois, UR 3926, Laboratoire de Génie Informatique et d’Automatique de l’Artois (LGI2A), F-62400 Béthune, France

Constraint Programming
AskPDF
Mar 30, 2026

Differentiable Initialization-Accelerated CPU-GPU Hybrid Combinatorial Scheduling

This paper presents a hybrid CPU-GPU framework for solving combinatorial scheduling problems formulated as Integer Linear Programming (ILP). While scheduling underpins many optimization tasks in computing systems, solving these problems optimally at scale remains a long-standing challenge due to their NP-hard nature. We introduce a novel approach that combines differentiable optimization with classical ILP solving. Specifically, we utilize differentiable presolving to rapidly generate high-quality partial solutions, which serve as warm-starts for commercial ILP solvers (CPLEX, Gurobi) and rising open-source solver HiGHS. This method enables significantly improved early pruning compared to state-of-the-art standalone solvers. Empirical results across industry-scale benchmarks demonstrate up to a 10×10\times performance gain over baselines, narrowing the optimality gap to <0.1%<0.1\%. This work represents the first demonstration of utilizing differentiable optimization to initialize exact ILP solvers for combinatorial scheduling, opening new opportunities to integrate machine learning infrastructure with classical exact optimization methods across broader domains.

Mingju Liu, Jiaqi Yin, Alvaro Velasquez +1

University of Maryland, College Park, Maryland, USA · University of Colorado, Boulder, Colorado, USA

Combinatorial OptimizationInteger Linear ProgrammingDifferentiable Optimization
AskPDF