Polytope methods in parameterized complexity

线性规划是一种数学问题解决工具，在工业规划、运筹学和更广泛的非数学优化中被证明是非常有用的。自诞生以来的几十年里，围绕着它发展了一套深刻而丰富的数学理论，成为理论计算机科学领域的核心部分。该领域还催生了多家商业公司，包括ILOG(现为IBM所有)，他们开发了CPLEX优化套件，IBM将其归功于商业效率的提高，带来了数亿美元的节省。然而，这项研究的理论和实践之间存在脱节。在理论计算机科学中，重点是具有绝对性能保证的方法，即性能保证(就算法的效率和产生的解的质量而言)，适用于所述算法的每一种可能的输入。因此，所考虑的一组算法仅限于那些可能提供这种“普遍最坏情况”保证的算法。另一方面，在实践中使用的方法，如分支定界和分支切割，众所周知在许多“真实世界”实例中非常成功，尽管在极少数最糟糕的情况下效率非常低。换言之，理论计算机科学的粗粒度问题观点导致了不必要的悲观结论。我们从参数复杂性的角度提出了一种组合优化的研究，特别是线性规划工具和分枝定界方法的能力。在参数化的复杂性中，上述粗粒度的视图被问题复杂性的更细粒度的多变量视图所取代，其中可以用这些实例的某些参数有界来解释“容易”问题实例的可行性，即，我们可以使用结构参数来捕获和量化相对实例的难度。该视角最近取得了一些成功，其中分支和边界算法已经被证明对于某些问题具有非常好的理论上保证的性能，假设这些实例的所谓的“完整性缺口”是有界的(该条件在实践中也是已知的)。这些结果建立在线性规划的一些非常特殊的结构性质的基础上--问题的表述，称为持久性和半完整性--这些性质以前没有被理论界充分研究过，可能是因为它们的值在严格的粗粒度最坏情况下并不明显。本项目将以几种方式研究这种结构性质的条件，从而为结构化问题松弛理论奠定基础，并使用这些工具为一系列重要的问题开发新的有用的算法，包括基于分支和边界的问题以及更传统的组合问题。

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.