Formulations and heuristics for the multi-item uncapacitated lot-sizing problem with inventory bounds
研究了多物品共享存储容量时的生产计划问题，提出了最短路径公式和有效不等式公式，以及两种混合整数规划启发式框架，其中松弛-固定启发式在10分钟内达到最优解偏差4%以内。
We consider the multi-item uncapacitated lot-sizing problem with inventory bounds, in which a production plan for multiple items has to be determined considering that they share a storage capacity. We present (a) a shortest path formulation and (b) a formulation based on the a priori addition of valid inequalities, which are compared with a facility location formulation available in the literature. Two easy-to-implement mixed integer programming heuristic frameworks are also presented, (a) a rounding scheme and (b) a relax-and-fix approach performed in a time partitioning fashion. Computational experiments are performed to evaluate the different approaches. The numerical results show that the proposed relax-and-fix heuristic outperforms all other approaches. Its solutions are within 4.0% of optimality in less than 10 minutes of running time for all tested instances, with mean gaps in the order of 2.1 and 1.8% for instances with more relaxed and tighter capacities, respectively. The obtained solutions were always better than those obtained by a commercial MIP solver running for one hour using any of the available formulations.