Analytics Branching and Selection for the Capacitated Multi-Item Lot Sizing Problem with Nonidentical Machines

We study a capacitated multi-item lot sizing problem with nonidentical machines. For the problem, we propose several mathematical formulations and their per-item and per-period Dantzig-Wolfe decompositions, followed by exploring their relative efficiency in obtaining lower and upper bounds. Additionally, we observe that the optimum has a correlation with the solution values of the pricing subproblems of Dantzig-Wolfe decompositions, along with the solution values of the uncapacitated problems and linear programming (LP) relaxation. Using these solution values, we build statistical estimation models (i.e., generalized linear models) that give insight on the optimal values, as well as information about how likely a setup variable is to take a value of 1 at an optimal point. We then develop an analytics branching and selection method where the information is utilized for an analytics-based branching and selection procedure to fix setup variables, which is, to our knowledge, the first research using likelihood information to improve solution qualities. This method differs from approaches that use solution values of LP relaxation (e.g., relaxation induced neighborhood search, feasibility pump, and LP and fix). The application is followed by extensive computational tests. Comparisons with other methods indicate that the optimization method is computationally tractable and can obtain better results.