Decision Correction Strategy in Relax-and-Fix through Local Branching constraints

This work addresses the Capacitated Multi-Item Lot-Sizing Problem by investigating the integration of a relax-and-fix heuristic with constraints inspired by the local branching paradigm. The proposed approach aims to improve computational performance and solution quality while reducing the occurrence of infeasible subproblems. The heuristic is based on a Mixed-Integer Linear Programming formulation complemented by a backtracking strategy and three different local
branching strategies. Computational experiments show that the backtracking strategy increases the percentage of feasible solutions obtained by the relax-and-fix procedure from 80.36% to 91.78% and reduces the average gap from 12.74% to 6.60%, although at the expense of higher computational effort. In turn, the proposed local branching-based strategies reduce the need for backtracking iterations, improve computational performance, and enable the revision of previously fixed decisions. Overall, the proposed approaches constitute a promising alternative for the CLSP.