A variable redefinition approach for the lot sizing problem with strong set-up interactions

We address a variant of the Joint Replenishment Problem, in which the products can only be produced in fixed proportions to each other. Such problems occur commonly in the manufacture of sheet metal and die-cast parts and some chemical products. We call it the Strong Interaction Problem (SIP). The general instance of the problem is NP-complete while single nest instances are polynomially solvable. We establish the boundary at which the problem becomes hard. We also present an exact algorithm for solving the problem using a variable redefinition approach. Computational testing on randomly generated problems indicates that our algorithm is several orders of magnitude faster than solution of the problems without reformulation using existing algorithms and commercial software.