Coordinated cutting plane generation via multi-objective separation
Coordinated cutting plane generation via multi-objective separation
复制标题
通过多目标分离协调切割平面生成
DOI：
10.1007/s10107-012-0596-x
复制
发表时间：
2012
影响因子：
2.7
通讯作者：
Stefano Gualandi
中科院分区：
文献类型：
--
作者：
E. Amaldi;Stefano Coniglio;Stefano Gualandi
在切割平面法中，如何生成“最佳的”切割集合的问题既是核心问题，也是关键问题。我们提出了一种字典式多目标割平面生成方案，它在给定族的所有最大违反的有效不等式中生成一个非支配且最大多样性的w.r.t.之前发现的伤口。通过优化多样性度量，我们引入了一种连续切割之间的协调形式。我们的重点是左手边系数为0-1，右手边系数不变的有效不等式，它包含了几族有效的不等式。作为切割分集的度量，我们考虑1-范数距离的集合。先前切割的法线向量。在这种情况下，我们的词典序多目标分离问题归结为目标函数系数取值不同的标准分离问题。在一个纯粹的割面环境下，分别对最大团和最小Steiner树问题分离稳定集和割集不等式时，我们评估了协调割面生成方案的影响。与非支配最大违规切割的标准分离相比，我们用相当少的回合和切割来填补相同比例的二元性缺口。我们方案的潜力也被在最大团的割枝设置中获得的结果所指示，其中割接协调允许平均地大幅减少分支和界限节点的数量。
In cutting plane methods, the question of how to generate the “best possible” set of cuts is both central and crucial. We propose a lexicographic multi-objective cutting plane generation scheme that generates, among all the maximally violated valid inequalities of a given family, an inequality that is undominated and maximally diverse w.r.t. the cuts that were previously found. By optimizing a diversity measure, we introduce a form of coordination between successive cuts. Our focus is on valid inequalities with 0–1 coefficients in the left-hand side and a constant right-hand side, which encompasses several families of valid inequalities. As cut diversity measure, we consider an aggregate of the 1-norm distances w.r.t. the normal vectors of the previous cuts. In this case, our lexicographic multi-objective separation problem reduces to the standard separation problem with different values for the objective function coefficients. The impact of our coordinated cutting plane generation scheme is assessed in a pure cutting plane setting when separating stable set and cut set inequalities for, respectively, the max clique and min Steiner tree problems. Compared to the standard separation of undominated maximally violated cuts, we close the same fraction of the duality gap in a considerably smaller number of rounds and cuts. The potential of our scheme is also indicated by the results obtained in a cut-and-branch setting for max clique, where cut coordination allows for a substantial reduction, on average, of the number of branch-and-bound nodes.
DOI：
10.1007/978-3-319-33461-5_3
发表时间：
2016
期刊：
--
影响因子：
--
作者：
Dadush D
通讯作者：
Dadush D