The world is dynamic and changes over time, thus any optimization problem used to model real life problems must address this dynamic nature, taking into account the cost of changes to a solution over time. The multistage model was introduced with this goal in mind. In this model we are given a series of instances of an optimization problem, corresponding to different times, and a solution is provided for each instance. The strive for obtaining near-optimal solutions for each instance on one hand, while maintaining similar solutions for consecutive time units on the other hand, is quantified and integrated into the objective function. In this paper we consider the Generalized Multistage $d$-Knapsack problem, a generalization of the multistage variants of the Multiple Knapsack problem, as well as the $d$-Dimensional Knapsack problem. We present a PTAS for Generalized Multistage $d$-Knapsack.
翻译:世界是动态的,随着时间的变化而变化,因此,用于模拟现实生活问题的任何优化问题都必须解决这种动态性质,同时考虑到随着时间的推移改变解决办法的成本。多阶段模式是本着这一目标引入的。在这个模式中,我们得到了一系列与不同时间相对应的优化问题实例,并为每个实例提供了解决办法。努力为每个实例获得接近最佳的解决方案,同时为连续时间单位保留类似的解决方案,将量化,并纳入到目标功能中。在本文件中,我们考虑了通用多阶段多阶段美元-Knapsack问题,多级Knapsack问题多阶段变体的概括化,以及美元-Dimensional Knapsack问题。我们为通用多级多阶段的美元-Knapsack提供了一种PATAS。我们为通用多级的多级元-Knapsack 提供了一种通用的 PTAS。