Improving Directions in Mixed Integer Bilevel Linear Optimization
Federico Battista, Ted K. Ralphs
我们考虑在混合整数双水平线性优化问题(MIBLP)的解决方案方法中改进方向的核心作用。 目前最先进的解决MIBLP的方法采用最初开发的用于解决混合整数线性优化问题的分支和切割框架。 这种方法依赖于两种子问题的神谕:用于检查候选人对领导者和追随者的决定是否可行,以及产生有效不平等所需的问题。 通常情况下,这两种类型的神谕是分开管理的,但在这项工作中,我们探索它们的紧密连接,并提出基于解决单一类型的子问题的解决方案框架:确定是否存在所谓的改进跟随者问题的可行方向。 这个子问题的解决产生了信息,这些信息既可以用来检查可行性,又可以产生强烈的有效不平等。 在之前的工作基础上,我们揭示了改善方向在实施跟随者最佳性条件方面的基本作用,并将以前已知的基于最优的放松层次结构扩展到混合整数设置,表明相关的放松可行区域与改善方向衍生的交叉切口相关的闭合完全一致。 使用开源求解器 MibS 的修改版本的实现的数字结果表明,这种方法可以产生实际的改进。
We consider the central role of improving directions in solution methods for mixed integer bilevel linear optimization problems (MIBLPs). Current state-of-the-art methods for solving MIBLPs employ the branch-and-cut framework originally developed for solving mixed integer linear optimization problems. This approach relies on oracles for two kinds of subproblems: those for checking whether a candidate pair of leader's and follower's decisions is bilevel feasible, and those required for generating...