Distance and matching-induced search algorithm for the multi-level lot-sizing problem with substitutable bill of materials

This study examines the multi-level capacitated lot-sizing problems with a special focus on item replaceability. Two linear programming models are established using different variable definitions and the McCormick envelope. These are further strengthened using some valid inequalities. In large-scale instances, the problem becomes computationally difficult to solve because of its non-deterministic polynomial-time hardness. Therefore, a matching-induced search algorithm to solve the problem is proposed. The algorithm leverages the matching between the rounded relaxation and the incumbent solution values to fix a few binary variables. It also applies the relax-and-fix heuristic to solve the reduced-size problems and progressively improve solution quality. The algorithm is further enhanced by using both the matching information of historical feasible solution values and the distance between the relaxation and incumbent solution values. Extensive computational experiments are conducted to test the efficiency of the models and algorithms. Experimental results show that increasing the number of substitutable items on the bill of materials (BOM) or increasing the overlapping ratios among the BOMs, or both, can effectively reduce the total cost. The proposed enhanced algorithm can perform better than the relax-and-fix and some other heuristics in the literature.