混合整型优化是研究两类变量的数学优化问题:在整型域中取值的变量和在连续域中取值的变量。混合整数优化问题自然地出现在许多环境中，这一事实已经导致人们对设计针对不同问题变体的强算法越来越感兴趣。不幸的是，混合整数优化问题比“非混合”问题(如整数规划或线性/凸规划)要少得多。这并不奇怪，因为要解决混合整数优化问题，一个人必须克服一些新的技术挑战，这些挑战在更好地研究非混合对手中没有出现。

为各种混合整数规划问题设计强算法及其一般研究是执行部队的主要研究方向之一。

混合整数线性优化

混合整数线性优化问题是只涉及线性函数和有限多变量的优化问题。求解方法有很多种，主要分为原始法和双重法。求解MILP的一种标准(双)方法是采用切割平面法。在这里，底层的MILP被用来构造一系列线性优化问题，这些问题是由一系列线性约束(即所谓的切割平面)的连续叠加产生的，直到其中一个线性优化问题的最优解满足完整性要求。对于许多组合问题，利用其固有的组合结构可以推导出多族切割平面。不幸的是，类似的方法对一般milp来说似乎是虚幻的。切割平面的生成通常基于目标函数和给定的一组线性方程和不等式。目前已有的切割平面算法大多基于几何概念。为了生成强大的切割平面，我们需要理解代数和几何之间的相互作用。有希望的切割平面是基于所谓的无晶格多面体。 The structure and algorithmic use of this type of cutting planes is a central research direction at IFOR to tackle MILPs.

混合整数凸优化

混合整数线性优化问题是线性规划的自然混合整数对应，混合整数凸优化问题(简称MICPs)则是将凸问题推广到混合整数域。一般来说，解决micp是一项困难的任务，这并不奇怪。已经在纯连续的情况下，即经典的凸优化问题，只能得到一定精度的解。此外，在具有常数维的纯整数情况下，发明有效的算法已经是一个挑战。与混合整数的情况相比，经典凸优化有一些强大的优势:我们有必要和充分的最优性条件，一个强大的对偶理论，以及可靠的算法来处理这些问题的相当大的子类。在凸优化的所有子类中，半定规划起着突出的作用:几乎工程的每个领域都发现了半定规划的应用。此外，这类特别适合于内点方法，一个有效的算法家族的凸优化。然而，内点法的内在复杂性限制了它们能够处理的问题的规模。在过去的几年里，人们开发了新的、更便宜的方法来解决更大的半确定问题。这些算法被称为一阶方法，是对旧梯度方法的非常复杂的扩展。 Their scope of applicability and the impressive acceleration possibilities that they offer are not fully understood yet. Many development strategies can still be investigated to further improve them, to make them an indispensable tool to tackle huge-size semidefinite problems, or to leverage their versatility in the context of Mixed Integer Convex Optimization.

下面我们列出执行部队在这方面正在进行的一些项目。

混合整数凸最小化(T. Oertel, R. Weismantel)

本课题的目的是发展固定维数的混合整数凸最小化问题的有效算法。为此，将混合整数线性优化技术与凸优化算法相结合。我们所考虑的方法使用切割平面算法和多边形收缩技术来生成深度切割平面。

镜像下降法(M. bees, T. Oertel, R. Weismantel)

这个项目解决了最小化凸函数在凸集与一些变量必须是整数的附加要求的问题。众所周知，这个问题是np困难的，即使考虑的函数是分段线性的。然而，我们对解决这个问题的算法方法感兴趣，其中的困难被推迟到oracle的实现。如果这个预言可以在多项式时间内实现，那么问题本身也可以在多项式时间内解决。一个自然的问题是，这个oracle是否可以有效地用于只有两个整数变量的问题，如果可以，如何扩展这样的子例程来解决一般的混合整数凸问题。在这个项目的第一步是设计一个有限时间算法的混合整数凸优化。第二步，重点应该放在算法的效率上。

多面体整数点上lipschitz -连续强凸函数的最小化(M. Baes, R. Weismantel)

本项目研究了多面体区域整数点上lipschitz连续强凸函数的最小化问题。我们的结果与一个黑盒算法的收敛速度有关，该算法迭代地解决具有常数近似因子的特殊二次整数问题。尽管潜在问题具有普遍性，但我们证明了我们可以有效地检测出关于问题编码的假设，其目标函数值接近于最优值的可行解。我们还证明了这种近似结果是多项式因子以内的最佳可能结果。与Y. Nesterov和S. Onn合作。

混合整数非线性优化

现实世界中存在着许多混合整数非线性优化问题，需要对其进行全局最优求解。这是对混合整数凸优化算法的进一步推广，其中考虑了凸函数之外的非线性函数。为了研究MINLPs全局优化的新数学方法，需要得到能够构造出强混合整数凸松弛的理论结果。特别是，我们专注于识别由积分变量诱导的组合子结构，可以用来改进全局优化算法，以及绑定收紧技术。

下面我们列出执行部队在这方面正在进行的一些项目。

固定维数的整数多项式优化(K. Zemmer, R. Weismantel)

近几十年来，线性整数规划得到了广泛的研究，并得到了一些基本的结果。虽然其中一些已经推广到各种类型的凸问题，相对而言，对一般的非凸问题知之甚少。本课题重点研究非凸整数优化的一种特殊情况，即固定维数多项式优化。近年来，二次多项式的研究取得了一些进展，但仍存在许多问题。

混合整数非线性优化及其在化工中的应用(M. Ballerstein, D. Michaels, R. Weismantel)

全局优化的一般方法是将局部搜索方法与计算底层MINLP最优函数值的强全局有效界的算法相结合。这是通过构造和求解一层(混合整数)凸松弛来实现的。为此，模型描述中涉及的非线性通常被凸下估计量和凹下估计量所取代。建立强凸松弛是获得合理边界的关键步骤。最紧凸下-和最紧凹高估被称为一个函数的凸和凸包络，并且只在一些特殊的函数类中被明确地知道。本研究计划的目标是发展新的数学方法来进行最小二乘优化。由德国研究基金会(DFG)资助的合作研究中心SFB/TR 63“InPROMPT -液相多相系统中的综合化学过程”的背景下产生的MINLPs证明了所开发算法的实用性。