III: Small: Exploiting and Extending Integer Linear Programming in Computational Biology

整数线性规划(ILP)是一种通用的建模和优化技术，它以不同于传统用途的创造性方式在计算生物学中得到越来越多的使用。现代ILP解算器和计算机的速度有了惊人的提高，现在通常可以解决缺乏保证有效的求解方法的困难计算问题的重要实例。这个项目将进一步利用整数规划来解决生物学中计算问题的实际情况。这个项目的更广泛的影响将是通过改进的计算工具，这些工具将被创造出来用于生物学，也许还有医学。这可能会对生物学产生革命性的影响。对研究生和本科生的培训，以及对参与计算的生物学家的推广，也将产生更广泛的影响。这个项目还将影响算法计算机科学，通过展示重点的转变，从寻求最坏情况下的有效解决方案或近似到各种大小和性质的问题实例，到寻找有效地找到现实问题实例的准确解决方案的方法。在为整数规划建模生物现象方面存在智力挑战，非微不足道的技术问题，以及需要的教育和推广努力，使进展可用于更大的生物界。研究问题有三大类：1)许多研究问题涉及如何制定并更有效地实施大量相关的ILP计算。这是因为需要评估解决方案的生物保真度和统计意义，这往往会导致生物模型和ILP公式的变化，以及许多连续的ILP计算。2)通常可以为计算问题设计数学上等价但非常不同的ILP公式，在求解ILP实例所需的时间和内存方面有很大的差异。许多研究问题涉及如何为生物问题的子类设计最佳的ILP公式，并确定这些公式中常见的成功的新习语(或建模见解)。3)许多技术问题来自使用ILP作为一种语言来表达对生物问题的解决方案，这些问题不是以线性约束的形式自然提出的。这利用了这样一个事实，即整数规划是NP难的，可以用NP表示任何问题。然而，其结果是，与传统的ILP公式相比，这些公式往往是非直观的，并且巨大，变量与方程的比率比ILP解算器预期的要高。

Integer Linear Programming (ILP) is a versatile modeling and optimization technique that has been increasingly used in computational biology in inventive ways that differ from its traditional uses. Spectacular improvements in the speed of modern ILP solvers and computers now often allow the solution to important instances of hard computational problems that lack guaranteed-efficient solution methods. This project will further the exploitation of integer programming to solve realistic instances of computational problems in biology. The broader impact of this project will be through the improved computational tools that will be created for use in biology and perhaps medicine. This could have a transformative impact in biology. Broader impact will also be in the training of graduate and undergraduate students, and in outreach to biologists involved in computation. This project will also impact algorithmic computer science, by demonstrating a shift in emphasis from seeking worst-case efficient solutions or approximations to problem instances of all sizes and properties, to seeking methods that are effective in finding exact solutions to realistic problem instances of great importance.There are intellectual challenges in modeling biological phenomena for integer programming, non-trivial technical issues, and educational and outreach efforts needed to make the advances available to a larger biological community. The research questions are of three broad types: 1) Many research questions concern how to formulate, and more efficiently implement, a large succession of related ILP computations. This arises due to the need to evaluate the biological fidelity, and statistical significance, of a solution, often leading to changes in the biological model and ILP formulation, and many successive ILP computations. 2) It is often possible to devise mathematically-equivalent, but very different, ILP formulations for a computational problem, with large differences in the time and memory needed to solve the ILP instances. Many research questions concern how to devise the best ILP formulations for sub-classes of biological problems, and to identify successful new idioms (or modeling insights) that are common in these formulations. 3) Many technical issues come from the use of ILP as a language to express solutions to biological problems that are not naturally posed in terms of linear constraints. This exploits the fact that integer programming, being NP-hard, can express any problem in NP. However, the consequence is that the formulations are often non-intuitive, and huge in comparison to traditional ILP formulations, with a higher ratio of variables to equations than is expected by ILP solvers.