An Investigation into Prediction + Optimisation for the Knapsack Problem
An Investigation into Prediction + Optimisation for the Knapsack Problem
复制标题
背包问题的预测优化研究
DOI：
--
复制
发表时间：
2019
期刊：
影响因子：
--
通讯作者：
Tias Guns
中科院分区：
文献类型：
--
作者：
Emir Demirovic;Peter James Stuckey;J. Bailey;Jeffrey Chan;C. Leckie;K. Ramamohanarao;Tias Guns
我们研究背包问题的预测+优化公式。目标是根据历史数据预测背包物品的利润，然后使用这些预测来解决背包问题。关键是项目利润事先未知，因此必须进行估计，但解决方案的质量是根据真实利润来评估的。我们将问题、最小化预期遗憾的目标和学习问题形式化，并研究适合优化问题的不同机器学习方法。最近的线性程序方法已将线性松弛直接合并到损失函数中。相反，我们考虑改变损失函数的侵入性较小的技术，例如标准和多输出回归，以及学习排序方法。我们根据实际能源价格数据和综合基准对这些方法进行了实证比较，并研究了不同方法的优点。
We study a prediction + optimisation formulation of the knapsack problem. The goal is to predict the profits of knapsack items based on historical data, and afterwards use these predictions to solve the knapsack. The key is that the item profits are not known beforehand and thus must be estimated, but the quality of the solution is evaluated with respect to the true profits. We formalise the problem, the goal of minimising expected regret and the learning problem, and investigate different machine learning approaches that are suitable for the optimisation problem. Recent methods for linear programs have incorporated the linear relaxation directly into the loss function. In contrast, we consider less intrusive techniques of changing the loss function, such as standard and multi-output regression, and learning-to-rank methods. We empirically compare the approaches on real-life energy price data and synthetic benchmarks, and investigate the merits of the different approaches.