On branching heuristics for the bi-objective 0/1 unidimensional knapsack problem
On branching heuristics for the bi-objective 0/1 unidimensional knapsack problem
复制标题
双目标0/1一维背包问题的分支启发法
DOI：
10.1007/s10732-017-9346-9
复制
发表时间：
2017
影响因子：
2.7
通讯作者：
Frédéric Saubion
中科院分区：
文献类型：
--
作者：
Audrey Cerqueus;Xavier Gandibleux;Anthony Przybylski;Frédéric Saubion
研究了求解多目标优化问题的分支定界算法中涉及的分支策略。在搜索树的每个节点处的分支变量的选择确实构成了这些算法的重要组成部分。在这项工作中，我们专注于多目标背包问题。在文献中，用于这些问题的分支算法是静态的，即，在执行之前确定变量的顺序。这项研究探讨了定义更复杂的分支策略的好处。我们首先分析和比较一组典型的分支启发式，并得出结论，没有一个可以被确定为最好的整体启发式。使用一个甲骨文，我们强调，在同一个分支和绑定算法的分支算法相结合，导致大大减少搜索树，但引起很高的计算成本。基于学习自适应技术，我们提出了动态自适应分支策略，能够选择合适的启发式应用在搜索树的每个节点。对双目标0/1一维背包问题进行了实验。
This paper focuses on branching strategies that are involved in branch and bound algorithms when solving multi-objective optimization problems. The choice of the branching variable at each node of the search tree constitutes indeed an important component of these algorithms. In this work we focus on multi-objective knapsack problems. In the literature, branching heuristics used for these problems are static, i.e., the order on the variables is determined prior to the execution. This study investigates the benefit of defining more sophisticated branching strategies. We first analyze and compare a representative set of classic branching heuristics and conclude that none can be identified as the best overall heuristic. Using an oracle, we highlight that combining branching heuristics within the same branch and bound algorithm leads to considerably reduced search trees but induces high computational costs. Based on learning adaptive techniques, we propose then dynamic adaptive branching strategies that are able to select the suitable heuristic to apply at each node of the search tree. Experiments are conducted on the bi-objective 0/1 unidimensional knapsack problem.
登录
查看更多内容
DOI：
--
发表时间：
1975
期刊：
影响因子：
--
作者：
A. Thesen
通讯作者：
A. Thesen
DOI：
--
发表时间：
2010
期刊：
影响因子：
--
作者：
Julien Jorge
通讯作者：
Julien Jorge
DOI：
10.1007/978-3-642-40627-0_36
发表时间：
2013-09
期刊：
--
影响因子：
--
作者：
Manuel Loth;M. Sebag;Y. Hamadi;Marc Schoenauer
通讯作者：
Manuel Loth;M. Sebag;Y. Hamadi;Marc Schoenauer
影响因子：
2.7
作者：
F. Glover
通讯作者：
F. Glover
DOI：
10.1016/j.ejor.2017.01.032
发表时间：
2017-08
期刊：
Eur. J. Oper. Res.
影响因子：
--
作者：
Anthony Przybylski;X. Gandibleux
通讯作者：
Anthony Przybylski;X. Gandibleux