Crossing Minimal Edge‐Constrained Layout Planning using Benders Decomposition

We present a new crossing number problem, which we refer to as the edge‐constrained weighted two‐layer crossing number problem (ECW2CN). The ECW2CN arises in layout planning of hose coupling stations at BASF, where the challenge is to find a crossing minimal assignment of tube‐connected units to given positions on two opposing layers. This allows the use of robots in an effort to reduce the probability of operational disruptions and to increase human safety. Physical limitations imply maximal length and maximal curvature conditions on the tubes as well as spatial constraints imposed by the surrounding walls. This is the major difference of ECW2CN to all known variants of the crossing number problem. Such as many variants of the crossing number problem, ECW2CN is NP ‐hard. Because the optimization model grows fast with respect to the input data, we face out‐of‐memory errors for the monolithic model. Therefore, we develop two solution methods. In the first method, we tailor Benders decomposition toward the problem. The Benders subproblems are solved analytically and the Benders master problem is strengthened by additional cuts. Furthermore, we combine this Benders decomposition with ideas borrowed from fix‐and‐relax heuristics to design the Dynamic Fix‐and‐Relax Pump (DFRP). Based on an initial solution, DFRP improves successively feasible points by solving dynamically sampled smaller problems with Benders decomposition. Because the optimization model is a surrogate model for its time‐dependent formulation, we evaluate the obtained solutions for different choices of the objective function via a simulation model. All algorithms are implemented efficiently using advanced features of the GuRoBi‐Python API, such as callback functions and lazy constraints. We present a case study for BASF using real data and make the real‐world data openly available.