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 produ cts 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 som e chemical products. We call it the Strong Interaction Problem (SIP). The g eneral instance of the problem is NP-complete while single nest instances a re polynomially solvable. We establish the boundary at which the problem be comes hard. We also present an exact algorithm for solving the problem usin g a variable redefinition approach. Computational testing on randomly gener ated problems indicates that our algorithm is several orders of magnitude f aster than solution of the problems without reformulation using existing al gorithms and commercial software.