DFKI Research Department Algorithmic Business and Production released challenging Data Benchmark Set for CP-SAT solvers and Reinforcement Learning

Cable trees are widely used in industrial products to transmit energy and information between different product parts. The automatization of their production leads to many interesting problems. One such issue, the cable tree wiring problem, was recently solved and a corresponding challenging data benchmark was set for CP-SAT solvers and reinforcement learning released by DFKI research department Algorithmic Business and Production (ABP)

Cable trees are used in a variety of industrial products. For example, cable trees are needed in cars to automate many previously mechanical functions such as moving seats or opening windows and to add new functions such as voice-controlled navigation or an onboard entertainment system. The manufacturing of cable trees usually relies on cheap manual labor performed in low-cost countries where humans plug cables into harnesses following a wiring plan. Only a few automated manufacturing solutions exist, which depend on complex robotic machines, such as the Zeta machine by Komax AG, Switzerland.

These machines execute a sequence of wiring operations that highly qualified technicians develop by analyzing the wiring plan. With the continuing tendency towards customer-specific and resource-efficient just-in-time manufacturing, smaller batch sizes of cable trees need to be manufactured, requiring a frequent change of wiring plans, for which wiring sequences should be derived instantly. Scaling up human expertise to such frequent changes is simply impossible, which explains a growing interest in the intelligent automated manufacturing of cable trees. This interest is also nourished by further miniaturization of cable harnesses, which will make their manual manufacturing impossible. 

In joint work with the Lucerne University of Applied Sciences and Arts and Komax AG, Switzerland, researchers from ABP research department have achieved an automated solution to the problem of finding an optimal insertion order for a given and fixed layout, called the problem of cable tree wiring CTW. They have gathered a challenging benchmark set of 205 real-world and 73 artificial instances. Several state-of-the-art CP, OMT, and MIP solvers were benchmarked on this benchmark set, and a paper including the problem formalization and benchmark results has appeared in the Constraints Journal Cable tree wiring - benchmarking solvers on a real-world scheduling problem with a variety of precedence constraints | SpringerLink. In the benchmarking, CP solvers outperformed the other solver types on this benchmark set. In particular, the IBM Cplex CP and the Google OR-Tools CP-SAT solver showed impressive performance, with Cplex being the only tested solver to find solutions for each instance in the benchmark set and OR-Tools finding more optimal solutions than any of the other solvers tested.

Algorithmic Business and Production has further contributed the CTW benchmark set to the MiniZinc Challenge 2020, an annual competition for Constraint Programming Solvers. The complete benchmark set is available online under https://github.com/kw90/ctw_translation_toolchain. The benchmark set may also be interesting to other areas of AI, as Standard Machine Learning (ML) and Reinforcement Learning (RL) struggle with this domain due to the presence of many dead-end states: states from which the final state (all cables have been plugged successfully) cannot be reached any more.

Share this post:


Prof. Dr. Jana Koehler

Forschungsbereichsleiterin Analyse und Optimierung von Prozessen

German Research Center for Artificial Intelligence
Deutsches Forschungszentrum für Künstliche Intelligenz