Polytope methods in parameterized complexity

线性规划是一种数学解决问题的工具，在工业规划、运筹学和更普遍的数学优化方面非常有用。几十年来，围绕它形成了一个深刻而丰富的数学理论，它已成为理论计算机科学领域的核心部分。该领域也催生了多家商业公司，包括ILOG（现在归IBM所有），他们开发了CPLEX优化套件，被IBM称赞为提高业务效率，节省了数亿美元的多个案例。然而，这项研究的理论和实践之间存在脱节。在理论计算机科学中，重点是具有绝对性能保证的方法，即性能保证（就算法的效率和生成的解决方案的质量而言），适用于所讨论的算法的每一个可能的输入。因此，所考虑的算法集被限制为那些“普遍最坏情况”保证是可能的。另一方面，在实践中使用的方法，例如branch-and-bound和branch-and-cut，已知在许多“现实世界”实例中取得了巨大的成功，尽管在罕见的最坏情况下效率非常低。换句话说，理论计算机科学的粗粒度问题观导致了不必要的悲观结论。我们建议从参数化复杂性的角度研究组合优化，特别是线性规划工具和分支绑定型方法的力量。在参数化复杂性中，上面描述的粗粒度视图被更细粒度的多变量问题复杂性视图所取代，其中“简单”问题实例的可行性可以通过这些实例的一些参数来解释，也就是说，我们可以使用结构参数来捕获和量化相对实例的难度。这种观点最近取得了一些成功，在假设这些实例的所谓“完整性差距”是有界的情况下，分支边界算法已被证明在某些问题上具有非常好的理论保证性能（这一条件在实践中也被认为是相关的）。这些结果建立在线性规划问题的一些非常特殊的结构性质上，这些性质被称为持久性和半完整性，这些性质以前没有被理论界充分研究过，可能是因为它们的价值在严格的粗粒度最坏情况下并不明显。该项目将以几种方式研究这种结构性质的条件，从而为结构化问题松弛理论奠定基础，并使用这些工具为一系列重要问题开发新的有用的算法，包括基于分支和边界的问题和更传统的组合问题。

Linear Programming is a mathematical problem-solving tool that has provenimmensely useful in industrial planning, operational research, and inmathematical optimisation more generally. Over the decades since itsinception, a deep and rich mathematical theory has developed around it,which has become a central part of the field of theoretical computerscience. The field has also spawned multiple commercial companies,including ILOG (now owned by IBM), who developed the CPLEX optimisationsuite, credited by IBM for improvements in business efficiency yieldingmultiple cases of savings of hundreds of millions of dollars.However, there is a disconnect between the theoretical and practicalstrands of this research. In theoretical computer science, the focus is onmethods with absolute guarantees of performance, i.e., performanceguarantees (in terms of efficiency of the algorithm and quality of theproduced solution) that apply for every possible input to the algorithm inquestion. Consequently, the set of algorithms considered is restricted tothose for which such "universal worst-case" guarantees are possible. Onthe other hand, methods employed in practice, such as branch-and-bound andbranch-and-cut, are known to have great success with many "real-world"instances, despite being highly inefficient in the rare worst case. Inother words, the coarse-grained problem view of theoretical computerscience leads to unnecessarily pessimistic conclusions.We propose a study of combinatorial optimisation, and in particular of thepower of linear programming tools and branch-and-bound-type methods, fromthe perspective of parameterized complexity. In parameterized complexity,the coarse-grained view described above is replaced by a morefine-grained, multivariate view of problem complexity, where thefeasibility of "easy" problem instances can be explained by some parameterof these instances being bounded, i.e., we can use a structural parameterto capture and quantify the relative instance difficulty.This perspective has recently had some success, where branch-and-boundalgorithms have been shown to have a very good theoretically guaranteedperformance for certain problems, under the assumption that the so-called"integrality gap" of these instances is bounded (a condition that is alsoknown to be relevant in practice). These results build upon some veryparticular structural properties of the linear programming-formulation ofthe problem, referred to as persistence and half-integrality -- propertiesthat have not previously been fully investigated by the theory community,possibly since their value is not apparent under a strict coarse-grainedworst case perspective.This project will investigate the conditions for such structuralproperties in several ways, thereby laying the foundations for a theory ofstructured problem relaxations, and using these tools to develop new anduseful algorithms for a range of important problems, both branch-and-boundbased and more traditional combinatorial ones.