On generating maximal nondominated Benders cuts
On generating maximal nondominated Benders cuts
复制标题
DOI：
10.1007/s10479-011-0883-6
复制
发表时间：
2013-11
影响因子：
4.8
通讯作者：
H. Sherali;B. Lunday
中科院分区：
文献类型：
--
作者：
H. Sherali;B. Lunday
在本文中，我们探讨了一些算法策略，通过生成最大非支配割来加速Benders分解方法的收敛。基于对马格南蒂和黄的开创性工作的解读，（Operations Research，29（3），464-484，1981）为了在多目标框架内生成非支配割，我们提出了一种算法策略，该算法策略利用Benders子问题的右手侧的抢先小扰动来生成最大非支配Benders割，以及通过对决策变量权重的替代强调在每次迭代中生成附加切割的补充策略。我们还研究了计算有效性的解决次级子问题，使用一个客观的削减所提出的Magnanti和黄与确定的Pareto最优区域切割生成利用互补松弛条件。此外，我们展示了一个标准的可行性切割可以从子问题的解决方案中提取，通过使用人工变量只产生最优切割。通过使用核心点估计技术（Papadakos in Computers and Operations Research，36（1），176-195，2009）在实现期间近似Magnanti和Wong的基线过程，这些算法策略在来自关于固定收费网络流程序的文献的实例上进行测试。
In this paper, we explore certain algorithmic strategies for accelerating the convergence of Benders decomposition method via the generation of maximal nondominated cuts. Based on interpreting the seminal work of Magnanti and Wong (Operations Research, 29(3), 464–484, 1981) for generating nondominated cuts within a multiobjective framework, we propose an algorithmic strategy that utilizes a preemptively small perturbation of the right-hand-side of the Benders subproblem to generate maximal nondominated Benders cuts, as well as a complimentary strategy that generates an additional cut in each iteration via an alternative emphasis on decision variable weights. We also examine the computational effectiveness of solving a secondary subproblem using an objective cut as proposed by Magnanti and Wong versus identifying the Pareto-optimality region for cut generation by utilizing complementary slackness conditions. In addition, we exhibit how a standard feasibility cut can be extracted from the solution of subproblems that generate only optimality cuts through the use of artificial variables. With Magnanti and Wong’s baseline procedure approximated during implementation via the use of a core point estimation technique (Papadakos in Computers and Operations Research, 36(1), 176–195, 2009), these algorithmic strategies are tested on instances from the literature concerning the fixed charge network flow program.