博士论文
主要内容
本文研究了具有同余约束的离散组合优化问题，并给出了处理这类约束类型的新方法。
研究同余约束的强烈动机来自整数规划中一个长期悬而未决的问题，即具有有界子行列式的约束矩阵的整数规划是否有效可解。
它的一个重要特例是同余约束整数规划
分钟{< c、x >: Tx≤b, <γ,x >≡r (mod), x∈Z ^ n}
具有完全非模约束矩阵T。
这类问题在m = 2时是多项式时间可解的，这导致了一种有效的算法，用于具有双模约束矩阵的整数规划，即n × n子行列式的绝对值以2为界的全秩矩阵。
尽管这些进展很大程度上依赖于已知的具有宇称约束的组合最小切割和循环问题的现有结果，但需要新的方法来超越双模情况，即m bbb2。
我们通过几种新技术在这个方向上取得了初步进展。特别地，我们展示了如何有效地判定具有完全非模约束矩阵m = 3的同余约束整数规划的可行性。
此外，对于一般的m，我们的技术还允许识别不可行问题的平面方向，并推导出问题的解与其松弛之间的接近界。
在本文的第二部分，我们研究了前面提到的奇偶约束最小割问题的推广(因此也推广了其他众所周知的最小割问题的变体，如全局最小割和最小s-t割)，即同余约束最小割，其中我们考虑了一些整数r和m的顶点数与r模m相等的割。
我们开发了一种新的收缩技术，灵感来自于Karger著名的最小切割收缩算法，它与进一步的见解一起，导致了一个多项式时间随机逼近方案，用于任何常数模数m的同余约束最小切割。我们不是收缩原始图的边缘，而是使用分离技术在较小的顶点集上创建辅助图，用于执行随机边缘收缩。这样，就得到了待压缩的候选顶点对的结构良好的分布，其中所涉及的顶点对通常不通过边连接。
作为副产品，我们的技术揭示了对近最小奇切的新结构见解，以及更一般地，近最小同余约束切。
最后，我们给出了在形成小宽度层流族的一组切点中寻找受边约束的生成树的结果。特别是在旅行商问题(TSP)的背景下，寻找具有良好定义的性质的生成树的新技术，特别是在切链上满足宇称约束的树，对于推动一类近似算法的分析至关重要。
我们的主要贡献是一种新的动态规划方法，其中表项的值不仅依赖于以前表项的值(通常是这种情况)，而且还依赖于与每个表项一起保存的特定代表性解决方案。这允许处理广泛的约束类型，包括一致性约束的放松，或每个切割中边缘数量的上限和下限。
具体地说，我们给出了一个准多项式时间算法来求解具有最优可能保证的最小链约束生成树问题。
此外，我们展示了如何在(路径)TSP的上下文中使用宇称约束及其泛化可以处理，并讨论了在这种情况下的含义。
本文研究在附加假设约束矩阵的子行列式是有界的或具有特定结构的情况下的整数线性优化问题。对这一主题的贡献有三个方面。本文的第一部分给出了一个结构结果，即具有有界子行列式的矩阵的不同行数的一个新的上界。形式上，我们证明了一个列秩满且具有不同行且最大的n×n子行列式的绝对值不超过Δ的矩阵a∈n^ {m×n}，如果Δ>1满足m≤Δ^{log log Δ+2}·n^2+1，如果Δ=1满足m≤n^2+n+1。后一种情况是Heller [Pacific J. of Math]给出的完全非模矩阵的界的直接结果。， 7(1957)，第1351-1364页。作为一个推论，我们得到了m上的相同界对于一个任意的具有不同行的积分矩阵，其最大的子行列式的绝对值不超过Δ。本文第二部分介绍了单模矩阵的以下推广:如果A的n×n子行列式的绝对值集合为{A,b,c}，则矩阵A∈0 ^{m×n}是{A,b,c}-模，且其中A≥b≥c≥0。假设a和b满足一定的条件，我们证明了任意{a,b,0}模矩阵可以通过行置换和初等列运算转化为块结构。基于这种分解，我们构造了一种算法，该算法可以有效地识别{a,b,c}模矩阵，除非输入矩阵具有重复关系，即它允许满足2⋅|k1|=|k2|的非零n×n子行列式k1和k2。这是对经典的全非模矩阵识别算法的扩展。 The third part of the thesis focuses on strictly 3-modular polyhedra, i.e., polyhedra of the form {x∈ℝ^n:Ax≤b} where A∈ℤ^{m×n} has full column rank, its n×n subdeterminants are elements of {0,±3}, and b∈ℤ^m. We show that any integer infeasible strictly 3-modular polyhedron admits a flat direction of width at most 3, independently of its dimension.
我们考虑标准形式的线性优化问题。我们研究了(m- n)约束矩阵的(n- n)子行列式在绝对值上以常数为界的特殊情况。本文给出了几个特殊情况下的结果，表明这类整数优化问题是多时间可解的。Veselov和Chirkov[41]在双模情况下找到了解决这个问题的有效算法，即如果子行列式以2为界，在附加假设下，所有这些子行列式都是非零的。我们通过提供双模情况下的强多项式算法推广了这一结果。这是基于解决奇奇奇约束的TU问题。进一步，我们考虑了当(n × n)-子行列式为0,3或-3时的严格3模情况。我们给出了一个等价的带同余约束的tu -描述。对于重要的特殊情况，我们证明了如何确定可行性，并且如果不可行，则底层tu问题允许宽度为1的平坦方向。最后，我们给出了双模优化算法核心成分的Python实现。
本文从理论和实践两方面讨论了变维混合整数线性规划中的几个问题。
该问题是数学与计算机科学的交叉问题，具有丰富的理论和广泛的应用。然而，整数线性规划中的许多问题在计算上是难以处理的或已知是np困难的。
整数线性规划的许多研究都是为了将定维问题的正复杂性结果应用到变维的相关问题中。
在论文的第一部分中，我们研究了用较少整数变量的混合整数线性规划来重新表述整数线性规划。我们的重新表述抓住了问题的基本代数和几何结构。当只有少数整数变量时，有效求解混合整数线性规划的能力会影响我们的建模决策。这导致了混合整数公式，它可以比单独的线性不等式描述更优雅地表达可行解集。
许多由整数线性规划建模的现实问题具有组合的味道，其中可行的解决方案可以通过从给定的基础集中选择元素来构建。
在论文的第二部分，我们研究了这类在时间方面的整数线性优化问题。对于某些应用程序，构建最终可行解决方案的资源不能立即获得，但解决方案只能以增量方式逐步构建。我们的目标是为全局优化问题找到一个可行的解决方案，并且在中间时间步长中也相当好。为了得到这样的解，我们在中间步骤中构造目标函数来惩罚违反全局问题的约束。我们发现许多研究的问题继承了相关全局问题的np -硬度。另一方面，多项式可解的情况被识别。
在无人机监控基站布局应用的驱动下，第三部分研究了几何覆盖问题的算法和复杂度结果。从数学优化和理论计算机科学的不同领域的技术相结合，以解决一个著名的地形保护问题的新版本。
本文研究约束子模函数最大化问题(CSFMAX)。边际收益递减的性质是由子模函数捕获的，在许多相关的最大化问题中可以观察到。因此，CSFMAX问题自然出现在各种各样的环境中——从传感器放置到机器学习——并且近年来引起了相当大的兴趣。本文旨在通过从不同的角度来看待CSFMAX问题，从而有助于更好地理解这些问题。我们介绍的技术可以简化、概括和改进现有的结果。
在本文的第一部分中，我们考虑了松弛和舍入方法，它们成为CSFMAX的标准和极其通用的工具。在这种情况下，最常见的舍入技术之一是争用解决方案。这种方案首先对每个坐标进行独立舍入，然后去掉一些元素，从而得到一个可行集。此外，删除元素的步骤通常是随机的。这导致了程序中随机化的第二个来源，这可能使分析复杂化。我们提出了一种不同的多面体观点来设计争用解决方案，从而避免了在第二步中明确地处理随机化。这是通过关注滴注过程的边缘来实现的。除了避免随机化的一个来源，我们的观点允许采用多面体技术。两者都可以显著简化争用解决方案的构造和分析。
我们展示了如何通过我们的框架，可以获得二部匹配的最优单调争用解决方案。到目前为止，关于争用解决方案的最优性，只知道很少的结果。我们对二部匹配的争用解决方案也改进了二部匹配相关间隙的下界。
此外，我们还推导了一种通用匹配的单调争用解决方案，该方案比以前的最佳方案有了显著改进。同时，我们的方案通过产生一个略高的下界来暗示当前一般匹配的相关间隙的最佳下界并不紧。
我们的结果导致在匹配约束和进一步约束的组合上改进了各种CSFMAX问题的近似因子。
由于前人的研究结果显示了线性最大化和次模最大化之间的有趣联系，我们在本文的第二部分进一步研究了这两个问题之间的关系。在线性规划中，泛在单纯形算法是基于多面体邻域的任何局部最优也是全局最优这一事实。我们证明了类似的结果适用于次模最大化。特别是，单调CSFMAX问题的每个局部最优都产生1/2逼近，并且我们还给出了对非单调设置的适当扩展。然而，快速达到局部最优是一项艰巨的任务。此外，我们描述了一个快速和非常通用的局部搜索过程，适用于广泛的约束族，并统一和扩展了以前的方法。在我们的框架中，我们匹配已知的近似保证，同时解开和简化先前的方法。此外，尽管它具有通用性，但我们能够证明我们的局部搜索过程比以前的专门方法略快。
此外，我们还解决了一个开放的问题，即线性优化oracle是否足以获得子模最大化的强逼近算法。我们通过提供一个约束族的例子来证明情况并非如此，当仅使用多项式许多线性优化oracle调用相同的约束时，很难获得次模最大化的良好近似值。从以前的工作中可以得出，我们所证明的硬度与对数因子密切相关。
多面体上混合整数点上的多元标量多项式函数优化问题是线性规划问题的推广。虽然LP问题已被证明是多项式可解的，但其扩展到混合整数点，即混合整数线性规划(MILP)，是np困难的。然而，如果整数变量的数量是固定的，则MILP是多项式可解的。
我们开发了具有固定变量数的(混合)整数规划问题的算法，用于几类目标函数，这些目标函数是至少两次的固定次多项式，并带有一些额外的假设。这样，我们就能够为给定的问题类别提供新的复杂度结果。
第一个结果处理在二维多面体的整数点上最小化三次多项式。我们展示了这个
通过提供显式算法，该问题可以在输入大小的时间多项式中求解，从而扩展了先前的二次多项式结果。我们对有界多面体和无界多面体都证明了这一点。
第二个结果处理在二维多面体的整数点上最小化齐次多项式。在多项式阶数固定且多面体有界的情况下，给出了一种求解该问题的时间多项式算法。当函数是齐次函数的平移时，这个结果仍然成立，即使结果函数不齐次且平移向量未知。我们还证明了如果多面体是无界的，那么这个问题的最小尺寸的解可以在输入尺寸上具有指数大小。
第三个结果处理固定维多面体混合整数点上二次多项式的最小化问题。我们证明了这个问题在时间上是可解的，它是输入大小和定义约束和目标函数的矩阵的最大绝对值的多项式。我们还将此结果与先前的结果结合起来，得出了由变维低秩矩阵定义的二次函数的类似结果。
第四个结果也涉及在固定维多面体的整数点上最小化二次多项式。当目标函数为齐次且定义它的矩阵最多有一个正特征值或一个负特征值时，我们给出了该问题的全多项式时间逼近格式。
本文讨论了网络中有害扩散过程的最佳抑制保护模型中出现的问题。具体来说，我们研究了20年前由Hartnell[59]提出的消防员问题，它的一个变体，被称为防火资源最小化(RMFC)，以及多层次关键节点问题(MCN)，这是本文引入的一个新模型。
消防员问题和RMFC问题在过去的几十年里引起了相当大的关注，但是尽管在几个方面取得了进展，这些问题的近似性仍然没有得到很好的理解。即使底层图是树也是如此，树是在这种情况下研究最多的图结构之一，也是本文第一部分的重点。在此工作之前，最著名的近似比率是消防员问题的O(1)近似和RMFC问题的O(log n)近似，两者都是基于LP的，并且基本上匹配两个自然LP松弛的完整性间隙。我们通过提出消防员问题的PTAS和RMFC的O(1)-近似来改进这两种近似，两者都与已知硬度结果定性匹配。我们的结果是通过将已知的lp与几种新技术相结合而获得的，这些技术允许有效地枚举超常数大小的约束集来增强天然lp。
在本文的第二部分，我们将MCN问题定义为网络保护领域中两种不同范式的结合。第一种观点是从预防的角度来看待网络安全:对于给定的网络，目标是修改其结构，以尽量减少其传播故障的能力。第二个视角考虑阻塞模型。这些问题是针对已经发生攻击的场景提出的，本着消防员问题的精神。在这种情况下，假定有害的扩散过程以允许采取防御反应的特定动态通过网络传播。MCN问题结合了这两种观点，遵循Brown等人提出的防御者-攻击者-防御者模型框架。在本文中，我们定义了MCN问题，我们为它设计了一个精确的算法，我们进行了实验研究，在性能和最优解的质量上与一个更简单的顺序模型进行了比较。
本文讨论了求解整数和混合整数凸极小化问题的几种方法。也就是说，我们尝试最小化凸集上的凸函数，并附加一个约束，即少量变量必须是积分的。
本文共分为四个部分。
在第一部分中，我们将连续凸优化的镜像下降法应用于混合整数设置。该方法的主要特点是迭代次数与维数无关，然而，该方法依赖于一个强大的oracle，即所谓的改进oracle。对于只要求两个变量为积分的情况，我们给出了一个有效的客户端实现。
第二部分包含两个可选的、简短的、几何上的证明，证明了一个众所周知的结果，即在有界凸集的积分点上最小化凸函数是固定维的多项式。特别地，我们提出了一种基于混合整数线性优化oracle的oracle-多项式算法。
然后，在第三部分，我们将重心法推广到整数和混合整数设置。关键的一步在于用更一般的中心点代替重心点，使我们能够使用体积以外的度量。引入了中心点和近似中心点的概念。对于特殊情况，我们证明了(近似)中心点的性质。在整数设置和维数固定的情况下，给出了一种计算近似中心点的算法。此外，我们建立了基于无格多面体的(混合)整数最小化问题的最优性证明，并给出了一种算法
基于以这种最优性证书终止的中心点。
在最后一部分中，我们考虑了一类特殊的，不一定是凸的变维优化问题。我们的目标是优化集合P \ Zn上的f(Wx)，其中f是一个非线性函数，P Rn是一个多面体，w2zd n。维数n可以变化，但是，我们假设维数d是固定的。我们得到了后一类问题到整数线性问题的一个e有效变换。核心结果是表征集合W(P \ Zn)的表示定理，可以看作是Frobenius
多面体的类型定理。
本文研究了构造混合整数非线性规划的强凸松弛的新技术。局部优化软件可以快速识别出MINLP的有希望的工作点，而凸松弛的解提供了MINLP最优值的全局界，可用于评估局部解的质量。当然，这种评估的效率很大程度上依赖于凸松弛的质量。
一般MINLP的凸松弛可以通过用凸低估和凹高估函数代替模型描述中出现的每个非线性函数来构造。在这种情况下，希望在底层域上使用给定函数的最佳凸低估器和凹高估器——分别是所谓的凸包络和凹包络。然而，这些包络层的计算可能非常困难，因此包络层的解析表达式仅适用于某些结构良好的函数类。
影响估计器强度的另一个因素是基础域的大小:域越小，估计器的质量越好。在许多应用中，变量的初始域的选择是相当保守的，而更严格的边界是由MINLP的约束集隐式地给出的。因此，利用约束集信息的约束收紧技术是改进估计量和加速全局优化算法的重要组成部分。
本文的重点在于开发和计算minlp的新凸松弛，特别是在化学工程中的两个应用。详细地，我们推导了一种新的用于化学过程建模的一般结构的边界收紧技术，并提供了不同的方法来生成各种非线性函数的强凸松弛。
首先，我们的目标是优化设计混合蒸馏/熔融结晶工艺，这是一种新的工艺配置，可以将混合物分离成其组分。对这一过程以及其他分离过程进行形式化表示的一个关键部分是对过程中的质量守恒进行建模。利用相应方程组的解析性质，对所涉及变量的定义域进行约简。与标准软件相比，使用该技术可以显著加快混合蒸馏/熔融结晶过程的计算速度。
然后，我们集中讨论非线性函数的凸松弛的生成。首先，我们利用已有的两类有趣的二元函数理论。一方面，我们详细阐述、实现并说明了二元函数的切割生成算法的强度，这些函数在每个变量中是凸的或凹的，并且在整个域上Hessian的符号是相同的。另一方面，分析了色谱分离过程中高级平衡函数的松弛策略，并最终应用于完整描述色谱分离过程的可行分离区域。
其次，我们建议在扩展空间中推导包络，以克服在原始空间中计算凸包络所涉及的组合困难。特别地，我们考虑了一类函数，它们占了通用基准库中所有非线性的大部分。这些函数在变量的一部分是凹的，在变量的另一部分是凸的。对于这类一般的函数，原始变量空间中的凸包络至今还没有被发现。基于与多线性单项式的同时凸化，给出了它们的凸包络的扩展表达式的封闭形式。通过构造，这种方法不仅得到了函数的凸包络的扩展公式，而且得到了函数和所涉及的多线性单项式的强同步松弛。几个例子表明，这种同时的松弛可以比单个函数的松弛好几个数量级。
最后，受到函数和多线性单项式同时松弛的强度和计算影响的启发，我们进一步关注几个函数的同时凸化。在这种方法中，由于考虑到不同函数之间的相互依存关系，涉及相同变量中的几个函数的最小最小值的放宽要严格得多。本文研究了几种函数的同时凸包，利用凸包的丰富理论，给出了它们的内外描述的理论结果。此外，我们还应用这些结果给出了几种单变量凸函数的紧凸松弛的公式。
所有凸化技术的实现都可以作为开源MINLP求解器SCIP的插件获得。几个案例研究的计算结果揭示了与最先进的方法相比，所提出的技术的好处。
对系统决策中存在的不确定性进行建模的需求催生了优化理论中两个主要领域的发展:随机优化和鲁棒优化。随机优化利用概率分布对输入数据的不确定性进行建模，并要求优化某个随机量，如期望值。随机优化的主要缺点是需要假设输入数据可能实现的某些随机知识，以及需要隐性假设优化需要多次执行，以便优化的随机量是有意义的。另一方面，鲁棒优化假设存在对手，该对手控制物化输入数据，并选择它以使决策者的效用最小化。这种方法消除了前面提到的缺点，但它也有自己的缺点。特别是，鲁棒优化通常会给出过于保守的解决方案。然而，在许多情况下，这种保守程度是适当的，而在其他情况下，它可以被调节。
简而言之，本文研究的是鲁棒组合优化问题。其核心是对组合问题的几个新的鲁棒对应物的研究。与许多现有的模型不同，这些模型以未知资源成本的形式对不确定性进行建模，我们的模型试图捕捉潜在组合结构中存在的不确定性。换句话说，本文研究的是结构不确定性对经典组合优化问题的影响。具体地说，我们假设对手能够在选择了标称解决方案后移除资源的特定子集，例如图中的边。如果对于任何可接受的故障场景的实现，解决方案的所需结构特性(例如包含s-t路径或包含连通图)保持不变，则标称解决方案是可行的。
沿着这些思路，我们定义了几个新的鲁棒组合优化模型。所有这些模型的共同特征是假设底层组合结构是上理想的。这一性质确保了本文所讨论的所有生成的健壮对应物都涵盖了问题。一方面，从许多应用程序的角度来看，这个属性是现实的。另一方面，它有助于控制鲁棒解的质量，从而使其比其他鲁棒模型更保守。
本文的重点是发展有效的精确和近似算法，以解决经典组合优化问题的鲁棒对应问题。这些结果得到了相应的复杂性理论结果的补充。对鲁棒组合优化的相关文献进行了综述。
本文讨论了大型生物系统的一般建模框架，一方面将其应用于各种实际实例，另一方面对其复杂性和结构进行了严格的形式化和数学分析。
对于生物应用，首先概述了现有的生物系统分析方法，并在此背景下对所提出的建模框架进行了分类。该框架基于逻辑隐含公式。它允许验证生物模型，预测其对规定刺激的反应，以及确定疾病或失败模式的可能干预策略。随后将这一基本模型扩展到两个方向:一是纳入生物单元中反应的时序信息。这种泛化还可以检测由于建模错误而产生的可能未知的时间信息或不一致。此外，它还提供了一种将相关生物单元的逻辑模型一致地集成到一个模型中的方法。其次，通过对生物组分的活性水平进行精细离散化，增强了纯二进制基本框架。这允许根据一个成分的不同活动水平来表达不同的效果，因此模型的预测变得更加复杂。
在数学方面，推导并形式化了逻辑框架及其扩展。基本模型演变为一类特殊的可满足性问题(SAT)，其复杂性被划分为一般困难但数学上容易的子类。利用了SAT与整数规划的对应关系，并对其多面体进行了分析。有趣的是，SAT问题比它的整数规划等价问题允许更广泛的多项式可解问题。然而，计算结果证明了整数规划方法在计算上是可行的。基本的SAT问题也可以转化为二部有向图，并讨论了它们的实际应用。在此基础上，针对一类特殊的生物单元，导出了基于线性规划对偶的对偶框架，完善了该类生物单元的理论。
基本框架的动态扩展产生了一个相关的SAT问题，该问题包含原始问题作为特例，因此也难以解决。这个扩展的重点是对扩展SAT问题的最大可行和最小不可行的解决方案的分析。因此，有必要对SAT问题的解集进行优化，建议采用等效整数规划方法。为了枚举所有最大可行和最小不可行的解，采用了关节生成算法。为此，导出了扩展SAT问题的单调重新表述，保留了最大可行解和最小不可行解，同时显著减小了描述的大小。在某些非常严格的情况下，所得到的整数优化问题甚至在计算上是可处理的。最后，利用原始有向图中的图结构完全表征了最小不可行解，得到了一种通过多面体投影计算所有最小不可行解的替代方法。
逻辑框架的离散扩展导致了SAT问题的推广，即所谓的区间可满足性问题。在此设置中，变量为整数值，关联的间隔提供了一组值，表达式变为TRUE。为了在计算上确定可行解，将该问题转化为一个多项式系统，并利用希尔伯特的Nullstellensatz来检验其可行性。此外，从复杂度和可满足性两个方面分析了一般区间可满足性问题。在计算复杂度方面，即使对公式进行一定的限制，一般情况下也很难求解。对于区间可满足性，研究了经典随机SAT的阈值现象，并确定了特定阈值的下界。
近二十年来，半确定优化问题引起了许多研究者的关注。如今，它在诸如控制、结构设计、统计或难组合问题的放松等不同领域中有着各种各样的应用。本文主要研究大规模半定优化问题的实际可处理性。从理论上讲，这些问题可以用多项式时间内点法近似求解。内点法的复杂度估计与求解精度成对数逆增长，但在矩阵大小和约束数量上均为3.5阶。后者的性质禁止在实践中解决大规模问题。
在本文中，我们提出了基于先进的一阶方法的新方法，如平滑技术和Mirror-Prox算法，用于求解具有中等精度的结构化大规模半确定优化问题。这些方法需要非常具体的问题格式。然而，一般的半定优化问题不符合这些要求。在初步的步骤中，我们将略为结构化的半定优化问题以这些方法可适用的另一种形式，即矩阵鞍点问题来重新定义。最后一种方法的复杂度结果与约束的数量和目标精度的反比呈线性关系。
平滑技术分为两个阶段:首先导出目标函数的光滑逼近，然后将最优一阶方法应用于适应问题。本文给出了这种一阶最优方法的一个改进版本。该改进方案的最坏情况复杂度结果与原方法相同。然而，数值结果表明，在实际应用中，该方案的迭代次数要比原方案少得多。使用平滑技术中最优一阶方法的改进版本，我们能够在大约四个小时内解决随机生成的矩阵鞍点问题，涉及100个大小为12'800 x 12'800的矩阵，绝对精度达到0.0012。
对于由上述变换步骤得到的矩阵鞍点问题，平滑技术和Mirror-Prox方法每次迭代都需要计算一个或两个矩阵指数。使用标准技术，对称矩阵求幂的效率估计随矩阵的大小呈三次增长。显然，这种操作限制了平滑技术和镜像- prox方法在实践中可以解决的问题类别。我们提出了一种随机镜像- prox方法，其中我们用随机逼近代替精确矩阵指数。在一类重要的大规模矩阵鞍点问题的理论复杂度估计方面，这种随机化方法优于所有竞争对手。此外，我们展示了数值结果，其中随机方法只需要确定性对应的58%的CPU时间来解决大约随机生成的矩阵鞍点问题，其中有100个大小为800 x 800的矩阵。
作为本论文的附带结果，我们表明对冲算法-一种在理论计算机科学中大量使用的方法-可以被解释为双重平均方案。将套期保值算法嵌入到双平均方案的框架中，我们可以推导出该算法的三个新版本。这些改进的对冲算法的效率保证至少与原始方法的复杂性估计一样好，有时甚至更好。我们提出了数值实验，其中改进的方法显着优于其香草对应物。
本文通过向调度员提供持续的决策支持，解决了在复杂的中心站区域管理密集铁路交通的问题。为此，提出了一种闭环离散控制框架，其中模型预测控制器以配置计划的形式提供决策支持。模型预测控制器假定路网拓扑结构、列车时刻表、线路以及对未来列车运行的预测都已给出。控制员的时间关键任务是为调度员提供一个无冲突的调度计划，该计划在考虑的时间范围内为每列火车分配一个行驶路径和开始时间，此外，最大限度地减少可能在中央车站发生的延误和中断连接。
文献中已经提出了许多列车调度模型和算法，但在实际应用中获得成功的模型和算法很少。少数成功的应用程序要么局限于受限制的交换机区域，要么考虑更简单的网络拓扑，要么基于缺乏质量断言的启发式方法。不受这些限制影响的方法，到目前为止还没有在日常操作中应用，主要是因为它们的计算复杂性。本文提出的中央车站区域列车调度方法不仅速度快，而且为决策支持系统提供了质量保证。
本文从三个连续的步骤来解决列车调度问题:
1.不同的列车路线、不同的发车时间和不同的速度组合在一起，形成了一套不同的、所谓的阻塞时间楼梯，它基本上模拟了铁路网络中列车运行的安全走廊。
2.将数学约束分配模型表述为一个二元线性规划，其中约束排除了可选阻塞时间楼梯之间的安全相关冲突和操作冲突，因此，为每个列车运动分配阻塞时间楼梯的选择是有限的。
3.在模型中加入了一个双目标函数，根据中心站产生的延误和中断的连接来衡量分配的质量。最后，一个基于数学优化技术的商业求解器计算出最佳分配。
这种方法在计算时间方面的效率取决于二元线性规划的公式。与以前的公式相比，本文提出的公式具有更少的变量和更少而更强的约束。由于更强的约束，相关的LP松弛提供了更好的目标值边界，这反过来又可以被求解器利用，并导致更短的计算时间。
本论文的一个主要方面是在一个全面的案例研究中展示该框架的可行性，以便行业将该框架进一步整合到实际操作中。与瑞士联邦铁路(SBB)密切合作，在实验室环境中模拟了闭环离散时间控制系统。在模拟中，火车在瑞士伯尔尼的中央火车站一天内被调度。该闭环离散时间控制框架能够在1分钟的时间间隔内成功地调度列车。然而，实验室的环境排除了对闭环系统对实际铁路系统的质量影响的研究。本文概述了三个额外的重要步骤，这是在实践中成功整合这一框架之前所需要的:
1.该框架与一个模拟环境相连接，该环境将负责模拟实际铁路系统中的列车运动。
2.调度员必须被纳入闭环系统。一个良好的控制系统与调度员交互的平台对于所提出的决策支持系统的成功集成至关重要。
3.当调度员与控制系统之间的交互平台能够在模拟的实体铁路系统上成功运行时，模拟就可以被真实的铁路系统所取代。
很明显，SBB致力于改进业务流程，因此支持了本论文。但值得注意的是，SBB也支持论文建议的逐步方法，将决策支持系统集成到其操作过程中。因此，SBB启动了一个新项目，通过将闭环控制系统与铁路仿真软件连接起来，进一步研究该框架。
本文研究了车辆在轨道网络中的无冲突路由问题，这是运输和物流中许多应用中经常遇到的问题。在各种设置中，无冲突路由问题最常见的路由方法是顺序路由，其中请求以最快的方式一个接一个地得到服务，而不会干扰先前路由的车辆。由于经常缺少对线路质量的保证，因此需要有更好的理论认识。无冲突车辆路由也是一个固有的兴趣，作为一个姊妹问题的研究充分的分组路由问题。
在第一部分中，我们给出了关于双向网络的一些新的理论结果。我们考虑一组k辆车的无冲突路径的自然基本模型。在此之前，没有一种有效的算法具有次线性(k)近似保证且不受图拓扑限制。研究表明，无冲突车辆路径问题即使在路径上也很难求解到最优。在顺序路由方案的基础上，我们提出了一种最大跨度为O(OPT) + k的树的算法。将此结果与分组路由的思想相结合，我们得到了具有次线性近似保证的第一个有效算法，即O(√k)-近似。此外，还提出了一种随机算法，该算法的makespan为O(polylog(k))•OPT + k，该算法依赖于将树嵌入技术应用于图的压缩版本，以获得与图大小无关的近似保证。
第二部分是关于个人快速交通(PRT)中路由的应用。PRT是一种小型自动车辆按需运送乘客的公共交通方式。车辆的集中控制为优化路线提供了有趣的可能性。PRT中的路由是一个在线问题，其中传输请求随着时间的推移而出现，并且需要在不了解未来请求的情况下做出路由决策。此外，PRT中的网络是定向的。路由问题的复杂性以及用于PRT的路由算法实质上必须实时运行的事实常常导致选择快速顺序方案。这种方案的简单性源于所选路由以后永远不会更改的特性。这也是它的主要缺点，可能会导致很大的弯路。人们很自然地会问，通过使用更具适应性的路由策略，可以获得多少收益。这个问题是第二部分的核心动机之一。
我们首先提出了第一部分中使用的路由模型的一个变体，它适合于PRT。我们证明了路由问题在有向设置中仍然是困难的。进一步，我们引入了PRT网络的容量概念，并推导了它的界。计算结果表明，容量边界接近可达到的吞吐量。因此，它是PRT系统设计中估计网络容量的一个有用的量。然后，我们引入了一种新的自适应路由算法，该算法反复使用LP的解作为路由车辆的指南。一旦出现新的请求，就会将其集成到LP中，并同时对所有车辆的路由进行重新优化。我们提供的计算结果证明了自适应路由策略的潜在收益。为此，我们在许多场景中将所提出的自适应策略与顺序路由和简单的分布式路由策略进行了比较。
Wagner的论文涉及混合整数线性规划(MILP)的切割平面的生成、评估和分析。此类优化问题涉及有限多个变量，其中一些变量要求为整数。目标是在一组有限多个线性方程和不等式上最大化或最小化一个线性目标函数。
许多工业问题都可以用MILP来表述。离散变量和连续变量的同时存在给MILP算法的求解带来了困难。目前可用的算法不能在可接受的时间内解决许多现实问题，或者只能提供启发式解决方案。因此，人们对新的解决方案技术产生了持续的兴趣。
求解MILP的标准方法是采用切割平面法。在这里，潜在的MILP被用来构造一系列线性规划，这些规划的公式通过连续添加线性约束(所谓的切割平面)来改进，直到其中一个线性规划有一个满足整数约束变量上的完整性条件的最优解。
对于许多组合问题，利用问题固有的组合结构，可以立即推导出几个切割平面族。然而，对于一般的MILP，没有结构性能可以使用。切割平面的生成必须基于目标函数和给定的非结构化线性方程和不等式集。一方面，这使得一般MILP问题的强切割平面的求导比结构化问题的切割平面的求导更加困难。另一方面，正是由于这个原因，对一般MILP的切割平面生成的分析在数学上变得有趣。
在他的论文中，Wagner提出了一种生成通用MILP切割平面的方法。切割平面由无格多面体获得，即没有内部整数点的多面体。Wagner的出发点是底层MILP的线性规划松弛的最优解。通过考虑相关单纯形表的多行，推导出进一步的松弛。
Wagner论文的第一部分专门分析了这种松弛，并展示了如何从考虑的松弛中推导出一般MILP的切割平面。结果表明，生成的切割平面在离散变量空间中具有几何解释。特别地，我们发现由松弛得到的最强切割面对应于最大的无格多面体。因此，切割平面上的问题可以转化为最大无格多面体上的问题。
瓦格纳论文的第二部分讨论了生成的切割平面的评估。结果表明，重要的切割面同时也是难以导出的切割面，因为它们对应的是高度复杂的最大无格多面体。此外，Wagner还证明了在一定的线性方程组和不等式的假设下，重要的切割面可以用相对不太复杂的最大无格多面体的切割面来近似。一个概率模型被用来补充分析。此外，瓦格纳对他的结果给出了几何解释。
瓦格纳论文的第三部分着重于无晶格多面体的分析。特别地，研究了一类在切割平面框架中很重要的无格积分多面体。介绍了两种不同的极值概念。瓦格纳将无格积分多面体分为两类，一类是不能正确包含在另一个无格积分多面体中的无格积分多面体，另一类是不能正确包含在另一个无格凸集中的无格积分多面体。分析了这两个类，特别是关于他们的代表的属性和两个类之间的关系。结果表明，这两个类都具有大基数，并且它们包含非常大的元素。
对于Wagner论文的第二部分和第三部分，需要关于二维无格凸集的陈述。因此，论文的第四部分致力于这些结果的推导。
电力市场的自由化导致电网运营商的成本压力增加。由于电网运营商还负责可靠的电力供应，因此他们的目标是在成本和供应质量这两个相反的目标之间取得最佳平衡。供电质量的一个主要方面是供电的连续性，即向消费者提供电力。供电的连续性很大程度上取决于电网事故后的恢复时间，而恢复时间又直接受到执行恢复工作的(人力)资源可用性的影响。因此，电网运营商试图找到一种资源组织，以保证以最低成本提供高质量的供应。本文主要研究电网事故后恢复工作的战略资源管理问题。提出了两个模型来分析有限可用资源对供应连续性的影响。两种模型的恢复时间内因取决于当前可用的资源。
第一个模型是电网运行模型，详细模拟了在所有电压水平发生事故后资源的恢复活动。重复解决分配问题，以确定哪些事件可以通过当前可用的资源恢复。该模型的结果包括对供应不可获得性的估计，这是供应连续性的间接度量，以及事件恢复时间等概率分布的估计。通过评估各种关键绩效指标，可以对不同组织的资源进行分析和比较。在不中断供应的情况下，提出了新的关键绩效指标。该模型具有较强的可操作性，为电网运营商的资源管理战略决策提供了有效的支持工具。
第二个模型是一个基于组件的冗余电网模型，具有指数级的故障率和修复率。但是，只有在资源可用时才执行修复。故障资源的最优分配由马尔可夫决策过程决定，该决策过程使无限时间范围内未提供的平均期望功率最小化。为了处理大量的状态，制定了一个聚合模型，该模型产生基本模型的上界。尽管不同数量的资源对供应连续性的影响可以量化，但所观察到的影响只是边际效应。供电的连续性更多地取决于电网的冗余和故障/修理率，而不是可用资源的数量。该模型的计算结果证实了网状电网的高冗余性和极少发生的故障。
排放交易计划是监管框架，旨在通过为负责任的排放源创造经济激励来减少和控制污染水平。目前，有几个这类系统正在运行，欧盟排放交易计划(EU ETS)是最大的二氧化碳配额交易的多国强制性机制。本文关注的是限额与交易计划和其他排放法规的数学分析。我们回顾了关于这一主题的现有定量分析，并介绍了欧盟排放交易计划新阶段的实施以及美国、加拿大、澳大利亚和日本吹捧的限额与交易计划所带来的一些数学挑战。从理论的角度来看，本文的主旨是引入一个新的竞争均衡数学框架，在这个框架中，可以分析广泛的排放法规。从实际的角度来看，特别侧重于控制和减少大气污染的新的限额和交易计划的设计和数值分析。我们开发的工具旨在帮助政策制定者和监管机构了解不同法规的利弊。
由于法规之间的一些根本差异不会在确定性设置中发生，我们提出了一个随机均衡模型，该模型适用于企业生产产品以满足非弹性需求并被赋予许可证以在合规时抵消其污染并避免支付罚款的经济。因此，我们考虑风险中性(相对于风险厌恶)的公司，目的是在不同的排放法规之间获得更强的等效结果。能够轻易减少排放的企业就这样做，而那些减排难度较大的企业则从那些预计自己不需要所有排放许可的企业那里购买排放许可，从而形成了一个污染信用的金融市场。我们的均衡模型阐明了商品和污染配额的联合价格形成机制，捕捉了欧盟排放交易计划第一阶段的大部分特征。我们证明了一个平衡点的存在性，并证明了它的解可以归结为一个最优随机控制问题。我们还证明了排放信用价格的唯一性，并刻画了商品的均衡价格以及企业的最优生产和交易策略。
由此可见，按照欧盟排放交易体系精神设计的标准限额与交易计划是社会最优的(也是在随机环境下!)然而，这并不意味着这些方案对消费者来说不贵。特别是有证据表明，标准的限额与交易计划通过显著提高产品的价格来增加消费者成本，这些产品的生产会造成污染(例如欧盟排放交易体系的电力)。这一观察结果是显而易见的，因为监管将生产转向更清洁、因而更昂贵的技术，而污染成本则计入这些产品的价格。
本文的主要目标之一是在一个现实的框架中量化这种影响以及排放法规的其他定性性质。为此，我们利用日本电力市场数值模拟了不同监管设置下的均衡。对于这个市场来说，一方面减排成本低得惊人，另一方面，消费者负担远远超过了总体减排成本，给电力公司带来了巨大的暴利，这在EU ETS中也有观察到。此外，我们用这个数字说明，即使是基于税收的法规和标准的限额与交易计划，100%的拍卖也不能将暴利减少到合理的水平。
这一事实表明，迫切需要改进一般的限额与交易机制。我们展示了如何调整排放交易计划的监管框架，使最终消费者成本合理低，同时保持机制的社会最优性。由此得出的相对分配方案和混合分配方案表明，设计中一个看似无害的小变化可能会产生巨大的经济影响。
本文讨论了列车时刻表编制的一般问题，特别是对于大型和高利用率的铁路网。
假定时间表的商业需求是给定的，任务是为满足这些需求的每列火车提供详细的无冲突的轨道路径。在本文中，开发了一种综合方法，从预定列车服务的商业描述到全天无冲突的详细时间表。该方法遵循基于三个描述层次的分而治之策略:服务意图、宏观时间表和微观时间表。这些关卡以这样一种方式进行交互，即规划人员有可能介入每个关卡的规范，并为测试不同的备选方案启用反馈循环。
文献中已经提出了许多列车调度的模型和算法，其中一些在实践中得到了成功的应用。然而，它们要么是为大规模问题而设计的，考虑了简化的拓扑和安全系统，要么是详细的方法，但只适用于有限的区域。本文结合了这两种方法来寻找大型网络的详细时间表，部分依赖于文献中的已知模型和算法，进行改编或扩展，部分开发全新的想法和方法。
该方法的出发点是构建一个适当的结构来描述预期的列车服务，包括周期性信息。这部分周期服务意向(ppSI)包含铁路公司希望在一天内向客户提供的商业报价。ppSI的目的是建立一个正式的框架，在这个框架中可以系统地开发和描述潜在的商业报价。现代铁路时刻表的一个重要特性是其周期性，便于乘客记忆。除了这种规律性之外，引入不定期列车服务是必要的，以应对一天中不同的需求。所开发的ppSI能够以紧凑的形式描述具有部分周期结构的商业铁路报价，并能在列车调度过程中有效地利用这些报价。
处理服务意图的部分周期性的基本思想是对单个周期时间的等效投影，从而产生增广周期问题。然后，首先在聚合拓扑上用简化的安全模型(宏观)，然后再考虑铁路基础设施和列车动态的更多细节，在本地加以完善(微观级别)。最后，生成的定期无冲突列车计划在一整天内展开，以创建满足服务意图中最初指定的所有需求的生产计划。
宏观层面侧重于整个网络的全球相互依赖性，以产生时间表的最重要属性，因此必须避免处理仅与局部相关的大量详细信息。根据简化的拓扑模型，对安全约束和列车动力学进行了简化。这个描述级别的一个众所周知的模型是周期事件调度问题(PESP)。在本论文中，一个扩展称为灵活的周期事件调度问题(FPESP)的引入和应用，允许每个事件的时隙而不是固定的时间。此外，本文还提出了FPESP模型的一个扩展Flexbox模型它是FPESP的进一步推广，允许在服务意图中使用事件之间的自然依赖关系。然后将得到的(灵活的)宏观时间表用作微观层面的输入。
对于给定的时间表草案是否存在可操作的生产计划，必须在微观层面上加以检查，办法是考虑到对确保时间表无冲突很重要的详细资料，但这些资料与时间表的整体结构无关，因此在宏观层面上被忽略了。微观层面的安全模型遵循联锁系统的工作方式。它根据信令系统计算每个基础设施元素上的阻塞时间，并确保这些阻塞时间间隔不重叠。此外，计算的轨道路径必须指定列车驾驶员可以遵循的速度轮廓，给定一个合理的公差带。由于微观调度问题可能变得不可行，FPESP解的事件时隙给予了更大的自由度，这在交通密集的瓶颈区域尤为重要，在这些瓶颈区域，具有固定时间的宏观层面的解往往过于受限。
所要求的详细程度，加上密集的流量，导致了巨大的问题规模。因此，采用网络分离的方法，通过考虑网络性质，区分，将铁路网划分为可管理的大小区域冷凝和补偿区。凝结区通常位于主站附近，那里的轨道拓扑结构复杂，存在许多不同的路线。由于预计这一地区的交通密度很高，这也是一个容量瓶颈，火车需要以最大允许速度行驶，因此没有时间储备。通过利用车站区域内的各种路径可能性来避免碰撞。相反，补偿区连接两个或多个冷凝区，具有更简单的拓扑结构和更少的流量密度。在这里，应该引入时间储备来提高时间表的稳定性。在这些补偿区域中，选择合适的速度剖面是最重要的自由度。
对于这两个区域，一种新的模式叫做资源树冲突图(RTCG)是为解决微观调度问题而开发的。在该模型中，首先计算每个列车的一组调度方案，并使用树结构以紧凑的方式存储。在凝结区，这些备选方案是通过查看拓扑中的所有路线以及每列火车的离散起始时间集来计算的。在补偿区，为几个不同的路线计算一组合理的可选速度曲线。然后，导出约束，以排除涉及资源的备选方案之间的冲突。在图模型的基础上，将资源受限的整数多商品流动问题表述为整数线性规划。与之前基于冲突图中稳定集的公式相比，该模型具有更少和更强的约束，这导致了更强的LP松弛，从而大大缩短了计算时间。因此，RTCG模型可以快速解决大型问题。当某一区域在微观层面缺乏可行性时，采用反馈策略，根据从微观层面获得的信息生成另一个宏观调度。
通过来自瑞士的一些实际测试案例验证了所提出的多级方法。给出了时间表生成过程各步骤的计算结果，并与以往的方法进行了比较，以评价其改进。
线性规划是建模和解决现实世界优化问题最常用的工具之一。然而，大多数商业上可用的求解器通常无法处理大型问题，例如，现代应用中出现的数百万个变量或数十万个约束。为了解决这个问题，研究人员应用了分解方法，特别是拉格朗日弛豫。在本文中，我们研究了求解拉格朗日松弛的新方法，从而从理论和数值的角度近似地求解线性规划。
在理论部分，我们考虑了Nesterov最近提出的两种近似求解非光滑凸优化问题的原始-对偶优化方法。第一种方法称为原始-对偶子梯度法，是标准子梯度法的一种变体，其中计算的子梯度不仅用于在每一步创建一个原始解，而且还用于创建对偶解。该方法的收敛速度为0 (1/Є)2)达到Є>0的绝对精度，这是基于亚梯度的技术的最佳可能率。第二种方法称为过度间隙法，由目标函数的平滑和最优梯度格式的使用组成。其收敛速度为0 (1/Є)。利用该方法，我们设计了一种多项式时间逼近方案来求解无能力设施选址问题的线性规划松弛问题，改进了以往已知的0 (1/Є)对Є的运行时间依赖性2)到0 (1/Є)。
这两种方法都依赖于oracle来解决每次迭代中的子问题。然而，准确的预言通常是不可用的。我们考察了近似预言对方法整体收敛性的影响。我们表明，为了获得Є的总体绝对精度，原始对偶子梯度方法需要具有Є的理论精度的预言器2。相比之下，过度间隙方法需要的oracle精度为Є5这表明它不太稳定。然而，我们只是假设知道由oracle交付的解决方案的绝对准确性。引入其他需求可能会导致这些结果的改进。
在本文的实践部分，我们研究了这些方法在无容量设施选址问题和静态交通分配问题的线性规划松弛中的应用，为此我们获得了真实世界的数据。正如理论所料，过度间隙法在求解无能力设施选址问题的线性规划松弛问题上优于原始对偶次梯度法，并能得到精确的预测结果。令人惊讶的是，在解决静态交通分配问题时，原始对偶次梯度法比过度间隙法要好得多。这可以用方法中产生的子问题来解释。在过度间隙法中，我们必须解决最小二次代价流问题，这比原对偶次梯度法中产生的最短路径计算困难得多。对于求解最小二次成本流问题，我们考虑了近似预言，我们注意到过度间隙法比理论预测的更稳定。
由于我们使用了Nesterov和de Palma提出的静态交通分配问题的新公式，我们还比较了获得的交通分配与使用传统Beckmann模型获得的分配的特征。结果表明，Nesterov和de Palma模型更好地集中了交通流量，导致更可预测的拥堵。
在大多数经典网络优化问题中，主要关注的是性能。在这些问题中，人们通常不会考虑由于故障或其他原因而从给定网络中移除弧或顶点的可能性。然而，许多具有底层网络结构的系统并不是完全可靠的，因此在可能删除弧和顶点的设置中考虑网络模型通常是非常有趣的。不幸的是，在容易发生故障的情况下，人们对经典网络优化问题的了解相对较少。本文研究了在弧线和顶点可能被移除的情况下，网络上的经典组合优化问题。它包含了接下来要提出的四个主题的结果。在我们考虑的所有问题中，被移除的弧和顶点都是同时被移除的。
我们考虑的第一个问题是无环有向图中s-t可靠度的估计问题。只要待估计的信度不太小，就可以使用粗糙的蒙特卡罗方法获得高概率的良好估计。然而，这种方法需要大量的时间来为非常小的可靠性提供良好的估计。在对具有高影响的罕见事件感兴趣的模型中，通常需要估计小的可靠性。我们提出了一种方法，允许在大型无循环有向图中估计非常小的s-t可靠性，并提出了输入网络的结构条件，在这种条件下，所提出的算法是FPRAS。
将要讨论的第二个问题被称为网络流阻断，可以描述如下。在给定的流量网络中，必须移除受一定预算约束的弧子集，从而使最终网络中的最大流量值最小。虽然这个问题一般来说是np困难的，但对于平面实例的一些特殊情况，伪多项式算法是已知的。我们提出了新的方法，允许在伪多项式时间内解决比以前可能的更广泛的平面实例。特别地，我们提出了一种结合顶点移除和顶点容量的可能性的方法。在此基础上，提出了一种解决多源多汇网络中特定类型拦截问题的算法。我们还展示了一种将一大类伪多项式网络流阻断算法转换为FPAS的技术。
在论文的第三部分，我们介绍了匹配拦截问题，它基本上是其他拦截问题对匹配的自然扩展。任务是在给定的无向网络中选择一个相对于某个预算的边子集，使得结果网络中最大匹配的权重最小。给出了不同类型图类的硬度结果。对于树宽有界的图，我们引入了伪多项式算法和fpga。
在本文的第四部分，我们证明了Goemans和Vondrák关于所有固定大小子图的最小生成树的并集所包含的边数的界的一个猜想。我们证明了所证明的界可以看作是Mader定理的推广，该定理限定了任意最小边k连通图的边数。
变分分析中的一些问题，如非线性规划的必要最优性条件、具有显式等式/不等式约束的变分不等式的解和非线性互补问题，可以通过将原问题重新表述为方程或广义方程(包含)来分析和解决。然而，即使原问题完全用光滑函数来描述，结果方程的非光滑性也可能以一种非常自然的方式出现。这需要处理不平滑的方法。关注的焦点
本文的主要工作是研究由具有特殊结构的局部Lipschitz函数定义的方程，即所谓的广义小岛函数。这种结构适合于描述和计算标准广义(方向)导数，也适合于发展求解相关Lipschitz方程的广义牛顿型方法(即非光滑牛顿方法)。
本文的工作分为三个部分:适合的局部非光滑牛顿方法的识别、该方法的全球化以及全球化方法的应用和数值测试。
第一部分回顾了一类广义小岛函数及其不同的广义导数。我们计算了广义小岛函数的这些广义导数，并得到了精确的公式，特别是我们的主要应用类是由非线性程序引起的，这些非线性程序不是二次可微的，而是局部Lipschitzian导数可微的。
考虑由Bernd Kummer引入的局部非光滑牛顿方法，它可以处理不同的广义导数，并允许牛顿方程的不精确解。用该方法得到了广义Kojima函数的抽象收敛条件。
在第二部分中，通过非单调回溯的路径搜索，在相当一般的框架中描述了这种局部方法的全球化。我们讨论和分析了可能提前终止的原因。在可行性假设下，给出了全局收敛定理。我们证明了全球化方法继承了局部牛顿方法的收敛性。
我们还提出了一种全球化方法的修改，使其能够集成合适的一阶方法。
第三部分是全球化方法的应用和数值测试。对于有限维优化问题和互补问题，我们指定了我们的方法的单个步骤。对(广义)半无限优化和非线性互补问题的一组测试问题的数值结果是令人满意的。他们证实了第二部分的理论收敛结果。
主要研究不确定条件下抽水蓄能水电站的最优运行问题。这种不确定性源于水的流入和电力交易的现货市场价格的波动。该模型被表述为一个多阶段随机线性规划问题。一个连贯的和时间一致的风险调整值被纳入对风险的多时期约束。
本文由两部分组成。第一部分考虑一致的风险调整值，第二部分考虑系统的最优控制。第一部分定义了一个简单的递归风险调整值，在特殊情况下可以推导出它的下界。第二部分明确地解决了简单调度模型的一些优化问题;这些问题的结构与连贯风险度量中的问题类似。现货市场的短期交易是在有限的可处理时间阶段的情况下进行建模的。场景树是由现货价格的占用时间生成的。主成分分析显示了职业时间的特征模式。最后，对多期风险约束下的一般调度模型进行了数值求解。
能源市场的放松管制使电力工业必须采用风险管理技术。开始的自由化以及随之而来的天然气、燃料和电力价格的不确定性要求对生产设施和财政合同进行有效的管理。因此，衍生品建立了交易量和价格风险的基本工具。然而，事实证明，电力市场金融衍生品的估值尤其具有挑战性。电力在物理上是不可储存的，这一事实消除了金融数学中无套利方法的直接应用。因此，需要新的方法来评估电力市场中最简单的衍生产品。也就是说，建立无套利的电价动态模型是实现电力市场金融产品公平定价的关键一步。
在这项工作中，我们提出了一种方法，将电力市场转化为由零债券和额外风险资产组成的虚拟基础市场。利用这一结构，利率理论和数值变化技术被应用于电力市场的风险中性价格动态。结果，得到了欧式衍生品的显式公式，如点差、上限、下限和衣领期权。通过进行历史校准可以看出，在所提出的模型中，接近到期的合约波动率显著增加。
针对无闭型解的摆动型导数，提出了一种基于有限元法的求解算法。因此，利用了将多个停止时间问题简化为单个停止时间问题的级联。所得到的数值结果表明，不同摆振方式下的摆振均表现出光滑稳定的特性。这允许解释最优行权边界，并分析摆动期权价格对初始现货价格和行权数量的依赖性。有限元算法与蒙特卡罗方法的比较证明了所开发的数值程序的优点。
在过去几年中，传统市场受到日益激烈的竞争和不断增加的动态的影响。这种趋势使许多公司面临新的不确定性和风险。为了应对这些挑战，有必要提高适应能力和反应能力，并积极采取行动。这种“机动性”通常被称为灵活性。本文的重点是龙沙集团有限公司(LES)业务部门独家综合的不同灵活性的识别、评估和比较，并讨论了它们的依赖关系和相互作用。
专门从事独家合成的市场定制的与从临床前到商业数量的化学品、中间体和活性药物成分的研究、开发和制造相关的服务。独家合成市场的特点是客户数量少，合同的“排他性”(按订单制造)。合同是单独协商的(合同工程)，并且通常在需求数量和交货日期方面具有高度的客户灵活性。毫无疑问，这增加了顾客的忠诚度和满意度，但也使制造商面临不同产品生产的不确定性。容量管理)，这可能导致产能短缺，并需要重新规划和(昂贵的)生产调整。
鉴于业务功能«销售和营销»和«运营»本工作重点调查操作和合同灵活性，通过这种灵活性，LES可以对上述不确定性和风险做出反应。在对LES的基本工作流程进行一般性讨论之后，工作将集中在不同的灵活性术语上。接下来是如何评估灵活性的概念。结果表明，对于给定的合同组合和一个瓶颈工厂，相关的LES问题可以表示为一个多阶段决策问题。在多阶段框架中，每个时间点都必须决定现在是否要生产产品(1)圣阶段)或将在稍后的时间点产生(2)nd阶段)，认为基本问题可以在一个两阶段的框架中解决。将相应的两阶段方法表述为随机混合整数线性规划。特别是，该公式包括利润最大化模型以及基于条件风险价值的风险最小化公式。
在执行的案例研究中发现，合同和操作方面是密切相关的，不同灵活性的价值是由不同合同的规范和操作过程共同决定的。特别要指出的是，某些合同灵活性和业务灵活性可以相辅相成。考虑到预期利润或风险的优化，研究表明，灵活性的评估对不同的目标产生不同的结果。更准确地说，在风险视角下，灵活性通常比在风险中性方法下更受重视。最后，很明显，根据不同的目标，强有力的决策可能会发生多大的变化。
欧洲电力市场的自由化彻底改变了活跃在这些市场的公司的环境。尽管放松管制有好处，但今天的参与者正面临着由输电线路拥堵导致的市场力量问题。这一事实，再加上电力的不稳定性，使得合同定价变得困难。据观察，虚拟存储等合同的价格因所采用的估值方法而异。原因是这些合约的复制并非没有风险——标的风险无法完全对冲，因此对冲必须被视为降低风险的必要行动。
在这项工作中，我们不会继续沿着金融数学的路线，而是利用公用事业投资组合中的灵活性来评估这些合同。因此，管理的观点将采用灵活性，以控制公司的利润和损失分配。在下文中，灵活性将从降低风险的角度加以解释，并在内部对价格灵活性给予一致的原则。财务状况和生产组合的灵活性之间的联系将通过制定一个共同优化这两个方面的连贯框架来建立。为了能够在统一的基础上比较发电资产和合同，我们将发电厂确定为一套合同，以便复制这些资产——灵活的发电厂被视为期权，而不灵活的发电厂被视为期货合约。这种联合优化导致了金融中众所周知的投资组合优化问题，但需要根据电力市场进行调整。组合优化的结果是我们得到了交易和分派策略，即~e。-动态决策规则，即在今天指定，但确定整个时间范围内每个时间点的投资组合构成-类似于一系列具有行使边界的美式看跌期权。这些所谓的政策既能实现预期利润最大化，又能随着时间的推移动态控制风险。这将通过基于条件风险价值的动态风险工程方法来完成。 The advantage of our approach is linearization resulting in a linear program that can even be solved for large instances which is truly the case for utilities.
在执行的案例研究中，结果表明灵活性的价值是巨大的。特别是有人观察到，电力市场并没有正确地定价内在的灵活性——它被低估了。因此，高度重视灵活性的公用事业需要在一定程度上购买不灵活性，例如风力发电场，以增加其价值。只有在将一个实用程序的投资组合作为一个整体而不是在一个聚合级别上进行观察时，这个观察结果才会变得明显——因此，灵活性是一个投资组合属性。
在过去几年中，铁路交通有了很大的增长;此外，预计铁路客运和货运都将进一步增长。这些发展创造了优化现有基础设施利用率和铁路公司内部协调任务的需求。由于计算机科学、优化技术和智能资源管理的发展，现在可以生成频率增加的铁路时刻表。特别是在主站附近，铁路运营商预计铁路系统的运力将出现瓶颈，因为主干线在那里交汇。然而，紧凑的时刻表比不密集的时刻表更容易受到列车延误的影响。
手头的论文描述了时刻表的稳定性措施和高度相关的寻找车站区域内的列车路线的主题。由于在引入新的列车服务时，服务质量不应受到影响，因此在设计更密集的时刻表时，时间表的稳定性问题是至关重要的。不可预见的事件可能需要实时对计划进行部分修改，因此在设计新的时间表时应考虑到重新安排程序。此外，重新安排程序应尽可能易于执行。从根本上说，时间表吸收一些干扰的能力与充分利用可用容量相权衡。在评估函数的帮助下，可以检查时间表失败的可能性，它们对时间表中断的敏感性，或者它们从偏差中恢复的效率。
将精确拓扑下的列车路线问题与可用容量饱和问题分离，并在聚合拓扑下生成时刻表，得到两级方法。在上层，使用聚合拓扑生成预期列车服务的时间表。这一级别的任务是制定一个周期尽可能小的时间表，以便在尊重安全限制和列车服务意图的同时充分利用网络。在较低的层次上，使用精确的拓扑来决定先前生成的暂定时间表的可行性，并分析派生的时间表。由于本文主要研究的是时间表的稳定性，因此始终假设聚合拓扑的时间表是可用的。
通过考察站点区域的路径选择，将可行性问题建模为一个独立的集合问题。节点集对应于列车的所有可能路线，如果两个节点对应的路线是互斥的，则节点集通过一条边连接。然后应用不动点启发式方法求解独立集问题。
两列不同列车的路线不相容的概率，可以通过假设到达和离开列车的特定延迟模式来计算。然后通过引入额外的边来扩展先前的模型，这些边的权重设置为相应路由不相容的概率。然后将稳定性测度表示为扩展图的某些性质。此外，还引入了一种不依赖于任何延迟分布的稳定性测度。在第二步中，使用这些稳定性度量函数来描述不同的优化问题，然后通过随机重新启动局部搜索启发式来解决这些问题。
为了测试该方法，使用了伯尔尼站区域。根据所应用的优化问题和潜在的延迟模式，列车被安排在网络中的不同路线上行驶。结果表明:列车时刻表越紧凑，铁路系统的设计与协调、合适的轨道拓扑、有意义的列车服务意图、密集的列车时刻表、精心设计的线路以及积极管理列车延误就越重要。
本文研究了车站区域内轨道可用容量的评估问题。这个问题特别令人感兴趣，因为铁路运营商预计，整个铁路网的运力瓶颈将主要出现在位于主要铁路线路交汇处的车站附近。然而，估计一个车站区域的容量比评估两者之间的容量要费力得多。这是由于车站内存在许多开关，以确保火车可以到达任何目的地。因此，一列火车可能有数百条可能的路线。通常，存在两条以上平行轨道的路段，因此简单地为每个方向分配一条轨道是不够的。因此，列车路线对运力利用率有重大影响。
所开发的方法通过构造密集调度来声明可用的运力，其中运力定义为在考虑的轨道拓扑上提供给定列车服务意图所需的时间。此外，还介绍了时刻表稳定性的度量方法。因此，时间表可以根据其能力利用率和稳定性进行比较。
为了将列车路线的选择与列车序列的确定分离开来，引入了两级模型。在顶层，使用聚合拓扑，其中假设交换机区域具有无限容量。在聚合层面上的任务是在切换区域之间的延伸路段上固定列车序列，以使最终的时间表周期时间最小化。在较低的建模水平上，使用开关区域的精确拓扑来确定先前导出的暂定时间表的可行性。
Petri网应用于聚合水平的建模。首先，列车服务意图被描述为一个一般的Petri网，其中包括可用轨道数量和期望列车连接的限制。下一步，在平行轨道的延伸上选择列车序列，这对应于将Petri网转换为事件图——无决策Petri网。最后，利用模拟退火的方法使所得到的暂定时间表的周期时间最小化。
将切换区域临时时间表的可行性问题建模为一个独立的集合问题。列车的所有可能路线在图中被描绘成节点，如果节点对应的路线由于安全距离不足而相互排斥，则节点相互连接。采用不动点迭代启发式方法寻找独立集。如果一个时间表被证明是不可行的，则计算一个额外的限制，以便在重新计算暂定时间表时消除冲突。
该方法在伯尔尼车站区域实施并进行了测试。结果表明，密集的时间表可以在1小时内构建。可以通过修改顶层使用的聚合拓扑来检测主要限制总体容量利用率的区域部分。
由于不断变化的客户需求和期望，在制造业中，出于竞争原因，从按预测生产转向按订单生产往往是必要的。管理系统作为制造系统的重要组成部分，必须掌握这些新的要求，即管理系统必须应对复杂性和不确定性。本研究的动机是基于对制造计划和控制的严格集中方法不再合适的观察。因此，本文提出了一种基于代理的方法，作为一种支持以人为中心的管理系统的手段，以适应和灵活的行为，这在当今的制造业中是必不可少的。本文的核心提出了一个整合管理控制论、生产物流管理、人工智能和面向对象并发编程等领域概念的建模和仿真框架。因此，这项工作处于这些领域的十字路口。该框架具有三个建模级别。所得模型可以分别利用仿真进行验证。物理布局方面的考虑——比如要使用的机器的选择——在物理层上进行映射。操作问题在逻辑级别上解决，这意味着给出关于如何操作物理系统的指令。 Organizational structures and task responsibilities regarding the operations are modeled on the management level. The organizations being mapped on the management level of this framework are multi-agent systems providing means for management systems in their striving to improve their adaptiveness to the situational conditionalities of the shop-floor.
为了有效地支持管理系统，多智能体系统必须遵循控制论提出的结构准则。在可操作性方面，该框架支持递归结构的多智能体系统，其中计划、调度和执行行为可以在每个多智能体系统中找到。因此，行为决定了代理的全部动作，也表示为能力。
高级水平的适应性行为作为构建特征多样性的来源，在某种程度上得到了支持，即代理具有多层次的适应。由于具有多层次的自适应过程，可以通过衰减不确定性来获得鲁棒性。为了保持系统的凝聚力，通过引入约束块来调整主体的多样性，使其受到尊重。智能体的信息库由其知识库和内部模型体现。
此外，还区分了与决策相关的代理(管理代理)和支持决策的代理(服务代理)。目前正在管理一级开发包含管理代理的多代理系统，并对其组织结构进行绩效评估。引入管理层次的主要原因不是分析算法能力，而是检查决策主体对算法的利用。
代理的概念开发在技术上得到了基于活动对象方法的实现的支持，该方法赋予代理通信和流程自主权。三个建模级别的概念分离在技术上也得到了支持。但是，代理必须在逻辑级别上进行干预。代理作为特殊类型的服务代理可以在逻辑级别封装对象。因此，代理能够将信息流重定向到管理代理，管理代理最初在逻辑级别上连接对象。因此，除其他事项外，这些代理能够以不同于最初计划的方式分配资源。
本文主要研究电力市场的风险管理，特别是实物生产与电力合同之间的相互作用。从风险管理的角度来看，电力投资组合与传统的金融投资组合有很大的不同。电力是不可储存的，再加上边际生产成本的特点，导致了现货价格的大幅上涨。因此，电力投资组合的回报通常是重尾的，需要一种风险度量，如CVaR，来捕捉这种重尾性。为了能够在统一的基础上比较生产和合同，我们确定了对应于每个发电厂的一组合同。这些合同建立了一个复制电厂的投资组合。这种合同工程使我们能够通过生产对这些通常复杂的合同进行风险管理。此外，生产电力公司可以通过简单的无套利论证，通过研究与相应发电厂相关的成本来评估这些合同。灵活的生产单位，如燃气轮机，与期权有关，而不灵活的生产单位，如核电站，与期货有关。
电力市场严重不完整，为什么许多合同无法实现完美的对冲?因此，我们引入了最佳对冲的概念。最佳的对冲是通过最优化找到的，在这种最优化中，以CVaR衡量的风险在预期利润的约束下被最小化。事实证明，这个问题可以用线性规划来解决，使我们能够处理大量的问题。
当考虑整个投资组合时，我们试图以最好的方式利用我们的风险委托。这就引出了金融学中众所周知的投资组合优化问题。然而，由于电力组合的特殊性，这一问题需要针对电力市场进行量身定制。最优投资组合也意味着生产资产的最优分配。我们专注于具有挑战性的水力储存装置，由于其灵活性对应于一系列的选择。然而，通过水库中储存的水，这些选择是相互依赖的。选择权的行使，即生产，减少了储水量，并可能在以后的时间点禁止生产。我们开发了一种动态调度策略，将这种相互依赖性考虑在内。因此，由水电站和电力合同组成的组合优化需要推导出最优的合同组合和最优调度策略，或者用财务术语来说，是相应期权的最优行使条件。我们用线性规划来解决这个问题，即在投资组合的CVaR不超过某个阈值的约束下，在特定的时间范围内最大化预期利润，该阈值通常由公司的风险偏好决定。
结果表明，由于调度取决于所签订合同的数量风险，因此需要同时优化调度和合同。一个主要的结果是与水电站的操作灵活性相关的高价值。通过研究我们的线性投资组合优化问题的对偶，我们实际上可以量化这个值。在一个执行的案例研究中，表明这种灵活性的价值可以是实质性的。任何不考虑这种操作灵活性的评估都可能因此低估了灵活的发电厂。
本文研究了定向拟阵的重构与生成问题。定向拟阵是离散几何对象的组合抽象，如点结构或超平面排列。重构和生成这两个问题都解决了表示和构造(类)面向拟阵的基本问题。本文讨论的表示是基于有向拟阵所定义的图，即拓扑图和共回路图。本文的第一部分研究了这些图的性质，以及这些图在多大程度上决定了有向阵的问题。在第二部分中，这些图表示用于生成给定元素数量和给定秩的有向拟阵的完整列表的生成方法的设计。这些生成方法在第三部分中用于构造有向拟阵目录和点构型和超平面排列组合类型的完整列表。
重构问题是一个有向矩阵能否从它的一些表示形式重构出来的问题，这些表示形式就是图和共回路图。已知拓扑图决定有向拟阵直至同构。然而，有向拟阵的位图没有简单的图论表征。我们加强了已知的拓扑图的性质，证明了对于不被f有界的拓扑中的每一个元素f，在拓扑图中都能引出连通子图。此属性稍后用于设计基于拓扑图的生成方法。
与拓扑图情况相反，已知共回路图不能确定有向拟阵的同构类。但是，如果每个顶点都被其支持的超平面标记，则可以重建定向拟阵直至重新定向。我们给出了一个简单的算法，对这个结果给出了建设性的证明。进一步，我们推广了已知的结果，证明了一个均匀定向矩阵的同构类是由它的共回路图决定的。此外，我们还提出了多项式算法，为这一结果提供了建设性的证明，并表明算法输入的正确性可以在多项式时间内得到验证。
生成问题要求列出给定基集基数和给定秩的所有定向拟阵的方法。已知的生成方法主要是针对3阶或4阶均匀定向拟阵设计的。我们的方法基于拓扑图和共回路图表示，并生成所有同构类的有向拟阵，包括任意秩的非均匀类。生成方法通过添加单个元素来增量地扩展面向矩阵。这些单元素扩展是根据图的局部化来研究的，这些局部化是表征单元素扩展的顶点集上的签名。
前两种生成方法是基于拓扑图的。这些方法利用了本文先前研究的拓扑图的性质，特别是新的连通性性质。第一种方法是一种反向搜索方法，用于在拓扑图中生成广义定位。在第二种方法中，使用图自同构来减少同构单元素扩展的数量。此外，我们还讨论了减少同一方向的矩阵从不同分支的多次伸展的技术。
设计了两种基于共回路图表示的算法，与基于拓扑图的算法类似。然而，所有前四种生成方法都缺乏效率，原因之一是它们没有使用很好的定位特征。由于Las Vergnas的结果，共回路图的局域化可以用共回路图中共线环上的符号模式来表征。这使我们能够设计出第五种在实践中有效的方法。这种方法是一种回溯算法，它列举了在表征方面可行的所有共线循环的符号模式。结果表明，该方法类似于Bokowski和Guedes de Oliveira在统一情况下的方法。我们的方法更通用，因为它能够处理任意秩的所有定向拟阵，包括非均匀定向拟阵。此外，在回溯过程中采用了一种高效的数据结构和一种新的动态排序方法。
该生成方法用于构造定向拟阵目录。这个目录是用定向拟阵的基本方向组织的。我们讨论了目录的一些属性和生成目录的方法。定向拟阵的目录可以用来找到点构型和超平面排列的组合类型的完整列表。本文对这些上市问题进行了研究，并探讨了解决方法。此外，我们还用一个例子说明了这些完备表在解决几何猜想方面的潜力。定向拟阵、点配置和超平面排列的列表可以通过Internet访问。
约束半分配问题(C-SAP)是伪布尔优化问题的推广，其中布尔变量被离散决策变量所取代。此外，约束由一组子句给出(类似于可满足性问题)，这些子句禁止某些赋值。
C-SAP经常出现在实际应用程序中，但也可以在此设置中制定许多组合优化问题。由于C-SAP是np困难问题，因此不能期望有效地确定全局最优。出于这个原因，这项工作的一个目标是开发一种启发式算法，该算法可以有效地用于一些C-SAP实例，对于这些实例，局部搜索方法由于目光短浅而注定要失败。本文新发展的不动点启发式(FPH)推广了广义最大可满足性问题的Cochand方法，使得它也可以应用于C-SAP等约束最大化问题。我们将用点特征标签放置问题的例子来说明，FPH也可以为现实世界的问题确定快速好的近似解。
从本质上讲，FPH是基于一个离散动力系统，该系统是由迭代一个适当定义的算子得到的。对于任何固定的起始点，以这种方式生成一个点序列。选择算子时，应使该序列在很大一部分起点处收敛到问题的一个良好的局部最大值。
在FPH中，通过适当选择算子，可以将全局信息包含在求解过程中。因此，对于某些C-SAP实例，FPH比局部搜索方法有很大的优势，而局部搜索方法由于其局部视野和缺乏方向性，在这种情况下会失败。
本文描述了一种基于模型的方法来设计车间物流管理系统。该方法包括启发式设计过程和建模框架。他们一起为这个设计任务提供了模型和原则，以及工具和程序。
面对当今动荡的商业环境，车间的物流管理已经成为生产型企业走向成功的决定性问题。它决定了几个因素(例如交货时间)，这些因素对客户满意度有很大的影响。与此同时，这些因素可以非常快速和客观地测量，因此可以相当直接地评估干预措施的短期效果。到目前为止，车间的物流管理主要被认为是一项计划和控制任务。因此，所使用的仪器通常被设想为系统地预测车间任何可能的后勤干扰。面对这一目标的现实局限性，对车间物流重新认识的必要性日益成为工业实践和学术研究的主题。设想的变化涉及到车间物流的任务和目标以及手段和工具。在这种变化的范围内，公司希望从关注生产的某些状态(例如利用率)的产品/功能视图转变为关注某些技能(例如敏捷性)的关系/系统视图。的确，虽然过去的设计工作主要集中在实际性能要求上，但车间物流的长期发展越来越多地成为设计目标。
毫无疑问，这种变化导致了传统设计方法的普遍挑战。事实上，人们普遍认识到，通过更强大的技术系统来提高规划和控制的能力，因此，试图将车间转变为一个操作封闭的系统，并不是通往可持续成功的正确途径。相反，应该创建工具，允许对车间进行整体物流管理。
自从200年前亚当·斯密提出“看不见的手”以来，经济学家对竞争性经济均衡一直持矛盾的立场。一方面，它是市场经济体制的基本范式，直观易懂;另一方面，其正式处理造成相当大的困难。某些模型的第一次存在证明直到20世纪30年代才成为可能;但是，即使是简单模型的算法处理也常常被证明是困难的，因为需要对难以获得的具体模型结构进行准确的洞察。
有很多种方法来形式化平衡;在此工作均衡是通过经济主体对价格信号的反应形式化的。在这里，根据上下文，“agent”可以用来表示不同的东西:消费者、生产者、整个经济部门，或者像国家这样的地理单位，等等。代理商的“反应”被定义为净销售(供给减去需求，出口减去进口)，这是由价格决定的。所有动因反应的总和称为(市场)过剩。
当供给等于需求或供给超过需求且相应价格为零时，存在非负价格均衡。
选择在过剩函数水平上研究均衡是由许多特定的优势所驱动的，包括它广泛适用于不同的经济均衡问题，它简单地将现有的和任意异质的主体整合到一个整体均衡模型中，以及它可以并行处理主体。对于本文研究的马尔卡尔-宏观多区域能源经济模型来说，后两个优点具有决定性的价值。这种基于过剩的观点的一个严重缺点是可能缺乏证明相关算法收敛到平衡点所需的过剩函数的结构性质。
然而，由于上述优点，有必要发展两种主要的启发式方法来解决基于过量函数方法的均衡问题。首先，切削平面法(CPM)是从平衡问题的变分不等式问题(VIP)的表述中推导出来的。第二种启发式是不动点法。
对平衡问题解决的贡献包括对过量函数单调性的数学分析，在应用CPM时对单调性的中心作用的澄清，以及在某些情况下对拉格朗日函数无界性的处理。这种无界性出现在不动点问题基础上的优化问题的分解中。另一个贡献是讨论和推广了证明均衡存在的不同策略。其中一种策略最终应用于MMmr。
研究的经验结果之一是，当使用特定的VIP对偶关系时，不动点方法具有鲁棒性和收敛性。
本研究的经济导向部分首先从CO2排放边界的角度对能源经济模型进行论述。特别注意分担负担和执行二氧化碳排放许可证。
基于国家能源经济模型(Markal-Macro)，开发了不同的模拟二氧化碳排放许可的可能性。首先，利用许可将国家模型整合到国际模型MMmr中。其次，分析了不同许可策略的后果。
使用来自瑞典、荷兰和瑞士的数据，最后成功地测试了这两个启发式。尽管得出的数据必须谨慎解读，但我们还是可以观察到一些有趣的经济趋势。假设二氧化碳排放量从2000年到2040年线性减少40%，如果贴现回2000年，平均许可证价格计算为每升燃料14美分。此外，与没有排放界限的参考情况相比，gdp损失约为2%。在我们的模型中，如果引入可交易的许可而不是固定的国家排放限额，这些损失可以减少五分之一。国家之间存在着显著的经济差异。由于收益和损失的分配可能直接受到初始禀赋的影响，因此MMmr等模型在初始禀赋或转移支付谈判时可以作为一种有用的决策支持工具。
有效的风险管理需要适当的风险度量。这里的一个基本问题是市场风险的量化:如果市场利率发生变化，对投资组合价值的总体影响是什么?要回答这个问题，必须解决两个基本难题:首先，市场利率表现随机且相互关联。其次，投资组合结构是高维的，通常是非线性的。现有的风险度量技术可分为两类。纯随机方法是基于投资组合的盈亏分布。这类中最流行的方法是风险价值(VaR)，它通常代表损益分布的1%或5%的分位数。最大损失(ML)方法是第二类方法的成员，其中风险是通过一些最坏情况的值来量化的。许多这些基于最坏情况的度量检查有限的场景集合，并且不考虑相关性(例如压力测试)。更详细的方法通过解决约束最小化问题来确定最坏情况，其中可行方案集通常由市场利率的随机特征定义。 Compared to other worst case techniques, the Maximum Loss methodology uses a very particular choice of feasible domains: the so-called "trust regions" cover a certain percentage of all future outcomes and their shape reflects the correlation structure of the market rates. Furthermore, ML uses a polynomial time algorithm to identify the global minimum, whereas other techniques employ rudimentary optimization procedures. The fact that the Maximum Loss computation is based on a fast and reliable algorithm allows to solve the optimization problem repeatedly, which leads to new insights into the risks of nonlinear portfolios.