Branching Algorithms for the Reliable Production Process Design Problem

In the well-known Subgraph Homeomorphism Problem (SHP), it is required to make a homeomorphic embedding of some pattern digraph \(\varPi \) into the given target digraph G. Such an embedding is performed by some one-to-one map f defined on the node set \(V(\varPi )\) such that, for each arc (v, u) of \(\varPi \) , there exists an elementary f(v)-f(u)-path in G, and all such paths are vertex-disjoint. In this paper we consider the proposed recently Reliable Production Process Design Problem (RPPDP), which generalizes the SHP in the following way: The RPPDP has applications in production management planning, where the decision maker is aimed to propose a family of plans tolerant to possible faults of manufacturing units and supply chains. We propose the first branch-and-bound and branch-and-price algorithms for the RPPDP. The results of numerical experiments demonstrate high performance and mutual complementarity of the proposed algorithms.