机构名称：
¥ 18.0
本文在组合和凸优化的界面上引入了一类新的问题。我们考虑每个顶点与凸面程序配对的图形，每个边缘通过额外的凸成本和约束来串联两个程序。我们将这样的图称为凸集（GCS）的图。在GCS上，我们可以制定任何可以通过普通加权图制定的优化问题，顶点和边缘的标量成本。实际上，对于凸面程序中变量的任何固定选择，GCS都会简化为加权图，例如，我们可以在其中寻找，例如路径，匹配，旅行或最低成本的生成树。GCS问题中的挑战在于共同解决问题的离散和连续组成部分。通过组合图形的建模能力和凸优化，GCSS是一个灵活的框架，可以制定和解决许多现实世界中的问题。图形和组合目标（例如，找到路径或巡回赛）模拟了问题的高级离散骨架。凸成本和约束填补了低级连续的细节。本论文的主要贡献是解决任何GCS问题的有效而统一的方法。从加权图上优化问题的整数线性编程公式开始，此方法将相应的GCS问题作为有效的混合构成凸点程序（MICP）制定。然后，可以使用公共分支和结合的求解器将此MICP求解为全局最优性，或者大约通过将其凸松弛的溶液四舍五入。重要的是，MICP及其解决方案的配方都是完全自动的，并且我们框架的用户不需要在混合构成优化方面的任何专业知识。我们首先以一般术语描述GCS框架和MICP的表述，而没有以GC在GC上解决的特定组合问题为前提。我们通过跨越物流，运输，调度，导航和计算几何形状的多个示例来说明我们的技术。然后，我们专注于GC中的最短路径问题（SPP）。这个问题特别有趣，因为它概括了各种多阶段的决策问题，并且使用我们的技术可以非常有效地解决。我们考虑了SPP在GC中的两个主要应用：动力学系统和无碰撞运动的最佳控制
凸面集的图形，带有用于最佳控制的应用程序...
主要关键词
相关文件推荐
