识别变量之间的原因关系是决策过程的关键步骤。虽然因果推断需要随机实验，但研究人员和政策制定者越来越多地利用观测研究由于观察数据的广泛可用性和实验的不可行性而导致的因果假设。匹配方法是对观察数据进行因果推断的最常用技术。然而，由于实验者制造的不同选择，一对一匹配中的对分配过程在推论中产生不确定性。最近，提出了离散优化模型来解决这种不确定性。虽然具有离散优化模型可能的强大推断，但它们产生非线性问题并缺乏可扩展性。在这项工作中，我们提出了贪婪的算法来解决与持续结果的观测数据的强大因果推断测试实例。我们提出了一个独特的框架，可以重新设计非线性二进制优化问题作为可行性问题。通过利用可行性制定的结构，我们开发贪婪方案，以求解稳健的测试问题。在许多情况下，所提出的算法实现全球最佳解决方案。我们在三个现实世界数据集上执行实验，以展示所提出的算法的有效性，并将我们的结果与最先进的求解器进行比较。我们的实验表明，所提出的算法在计算时间方面显着优于精确的方法，同时实现了同样的因果试验结论。两个数值实验和复杂性分析都表明所提出的算法确保在决策过程中利用大数据的力量所需的可扩展性。
translated by 谷歌翻译
最小的平方和群集（MSSC）或K-Means型聚类，传统上被认为是无监督的学习任务。近年来，使用背景知识来提高集群质量，促进聚类过程的可解释性已成为数学优化和机器学习研究的热门研究课题。利用数据群集中的背景信息的问题称为半监督或约束群集。在本文中，我们为半监控MSSC提供了一种新的分支和绑定算法，其中背景知识被包含为成对必须 - 链接和无法链接约束。对于较低的界限，我们解决了MSSC离散优化模型的Semidefinite编程宽松，并使用了用于加强界限的纤维平面程序。相反，通过使用整数编程工具，我们提出了将K-Means算法适应受约束的情况。这是第一次，所提出的全局优化算法有效地管理，以解决现实世界的情况，最高可达800个数据点，具有必要的必须 - 链接和无法链接约束以及通用数量的功能。这个问题大小大约比最先进的精确算法解决的实例大约四倍。
translated by 谷歌翻译
2021-02-18
组合优化是运营研究和计算机科学领域的一个公认领域。直到最近，它的方法一直集中在孤立地解决问题实例，而忽略了它们通常源于实践中的相关数据分布。但是，近年来，人们对使用机器学习，尤其是图形神经网络（GNN）的兴趣激增，作为组合任务的关键构件，直接作为求解器或通过增强确切的求解器。GNN的电感偏差有效地编码了组合和关系输入，因为它们对排列和对输入稀疏性的意识的不变性。本文介绍了对这个新兴领域的最新主要进步的概念回顾，旨在优化和机器学习研究人员。
translated by 谷歌翻译
我们研究了具有预处理结果数据的实验研究的最佳设计。估计平均处理效果是治疗和控制单元的加权平均结果之间的差异。许多常用的方法符合该配方，包括差分估计器和各种合成控制技术。我们提出了几种方法，用于结合重量选择一组处理的单位。观察问题的NP硬度，我们介绍了混合整数编程配方，可选择处理和控制集和单位权重。我们证明，这些提出的方法导致定性不同的实验单元进行治疗。我们根据美国劳动统计局的公开数据使用模拟，这些数据在与随机试验等简单和常用的替代品相比时，表现出平均平方误差和统计功率的改进。
translated by 谷歌翻译
近年来，在平衡（超级）图分配算法的设计和评估中取得了重大进展。我们调查了过去十年的实用算法的趋势，用于平衡（超级）图形分区以及未来的研究方向。我们的工作是对先前有关该主题的调查的更新。特别是，该调查还通过涵盖了超图形分区和流算法来扩展先前的调查，并额外关注并行算法。
translated by 谷歌翻译
在本文中，我们研究了在一组单位上进行的设计实验的问题，例如在线市场中的用户或用户组，以多个时间段，例如数周或数月。这些实验特别有助于研究对当前和未来结果具有因果影响的治疗（瞬时和滞后的影响）。设计问题涉及在实验之前或期间选择每个单元的治疗时间，以便最精确地估计瞬间和滞后的效果，实验后。这种治疗决策的优化可以通过降低其样本尺寸要求，直接最小化实验的机会成本。优化是我们提供近最优解的NP-Hard整数程序，当时在开始时进行设计决策（固定样本大小设计）。接下来，我们研究允许在实验期间进行适应性决策的顺序实验，并且还可能早期停止实验，进一步降低其成本。然而，这些实验的顺序性质使设计阶段和估计阶段复杂化。我们提出了一种新的算法，PGAE，通过自适应地制造治疗决策，估算治疗效果和绘制有效的实验后推理来解决这些挑战。 PGAE将来自贝叶斯统计，动态编程和样品分裂的思想结合起来。使用来自多个域的真实数据集的合成实验，我们证明了与基准相比，我们的固定样本尺寸和顺序实验的提出解决方案将实验的机会成本降低了50％和70％。
translated by 谷歌翻译
我们研究了通过中等数量的成对比较查询引发决策者偏好的问题，以使它们成为特定问题的高质量推荐。我们受到高赌场域中的应用程序的推动，例如选择分配稀缺资源的政策以满足基本需求（例如，用于移植或住房的肾脏，因为那些经历无家可归者），其中需要由（部分）提出引出的偏好。我们在基于偏好的偏好中模拟不确定性，并调查两个设置：a）脱机偏出设置，其中所有查询都是一次，b）在线诱因设置，其中按时间顺序选择查询。我们提出了这些问题的强大优化制剂，这些问题集成了偏好诱导和推荐阶段，其目的是最大化最坏情况的效用或最小化最坏情况的后悔，并研究其复杂性。对于离线案例，在活动偏好诱导与决策信息发现的两个半阶段的稳健优化问题的形式中，我们提供了我们通过列解决的混合二进制线性程序的形式提供了等效的重构。 -Constraint生成。对于在线设置，主动偏好学习采用多级强大优化问题的形式与决策依赖的信息发现，我们提出了一种保守的解决方案方法。合成数据的数值研究表明，我们的方法在最坏情况级别，后悔和效用方面从文献中倾斜最先进的方法。我们展示了我们的方法论如何用于协助无家可归的服务机构选择分配不同类型的稀缺住房资源的政策，以遇到无家可归者。
translated by 谷歌翻译
这项工作解决了逆线优化，其中目标是推断线性程序的未知成本向量。具体地，我们考虑数据驱动的设置，其中可用数据是对应于线性程序的不同实例的最佳解决方案的嘈杂的观察。我们介绍了一个问题的新配方，与其他现有方法相比，允许恢复较少的限制性和一般更适当的可允许成本估算。可以表明，该逆优化问题产生有限数量的解决方案，并且我们开发了一个精确的两相算法来确定所有此类解决方案。此外，我们提出了一种有效的分解算法来解决问题的大实例。该算法自然地扩展到在线学习环境，可以用于提供成本估计的快速更新，因为新数据随着时间的推移可用。对于在线设置，我们进一步开发了一种有效的自适应采样策略，指导下一个样本的选择。所提出的方法的功效在涉及两种应用，客户偏好学习和生产计划的成本估算的计算实验中进行了证明。结果表明计算和采样努力的显着减少。
translated by 谷歌翻译
给定数据点之间的一组差异测量值，确定哪种度量表示与输入测量最“一致”或最能捕获数据相关几何特征的度量是许多机器学习算法的关键步骤。现有方法仅限于特定类型的指标或小问题大小，因为在此类问题中有大量的度量约束。在本文中，我们提供了一种活跃的集合算法，即项目和忘记，该算法使用Bregman的预测，以解决许多（可能是指数）不平等约束的度量约束问题。我们提供了\ textsc {project and Hoses}的理论分析，并证明我们的算法会收敛到全局最佳解决方案，并以指数速率渐近地渐近地衰减了当前迭代的$ L_2 $距离。我们证明，使用我们的方法，我们可以解决三种类型的度量约束问题的大型问题实例：一般体重相关聚类，度量近距离和度量学习；在每种情况下，就CPU时间和问题尺寸而言，超越了艺术方法的表现。
translated by 谷歌翻译
最近已扩展了最小方形聚类（MSSC）或K-均值类型聚类的最小总和，以利用每个群集的基数的先验知识。这种知识用于提高性能以及解决方案质量。在本文中，我们提出了一种基于分支和切割技术的精确方法，以解决基数受限的MSSC。对于下边界的例程，我们使用Rujeerapaiboon等人最近提出的半决赛编程（SDP）放松。 [Siam J. Optim。 29（2），1211-1239，（2019）]。但是，这种放松只能用于小型实例中的分支和切割方法。因此，我们得出了一种新的SDP松弛，该松弛随着实例大小和簇的数量更好。在这两种情况下，我们都通过添加多面体切割来增强结合。从量身定制的分支策略中受益，该策略会实施成对的约束，我们减少了儿童节点中出现的问题的复杂性。相反，对于上限，我们提出了一个本地搜索过程，该过程利用在每个节点上求解的SDP松弛的解。计算结果表明，所提出的算法在全球范围内首次求解了大小的现实实例，比通过最新精确方法求解的算法大10倍。
translated by 谷歌翻译
随着优化软件的显着改进，几十年前似乎棘手的大规模问题的解决方案现在已成为日常任务。这将更多的现实应用程序纳入了优化器的范围。同时，解决优化问题通常是将解决方案付诸实践时较小的困难之一。一个主要的障碍是，可以将优化软件视为黑匣子，它可能会产生高质量的解决方案，但是当情况发生变化时，可以创建完全不同的解决方案，从而导致对优化解决方案的接受率低。这种可解释性和解释性的问题在其他领域（例如机器学习）引起了极大的关注，但在优化方面却不那么关注。在本文中，我们提出了一个优化框架，以得出本质上具有易于理解的解释性规则的解决方案，在哪些情况下应选择解决方案。我们专注于代表解释性规则的决策树，我们提出了整数编程公式以及一种启发式方法，以确保我们的方法即使在大规模问题上也适用。使用随机和现实世界数据的计算实验表明，固有的可解释性成本可能很小。
translated by 谷歌翻译
In model selection problems for machine learning, the desire for a well-performing model with meaningful structure is typically expressed through a regularized optimization problem. In many scenarios, however, the meaningful structure is specified in some discrete space, leading to difficult nonconvex optimization problems. In this paper, we connect the model selection problem with structure-promoting regularizers to submodular function minimization with continuous and discrete arguments. In particular, we leverage the theory of submodular functions to identify a class of these problems that can be solved exactly and efficiently with an agnostic combination of discrete and continuous optimization routines. We show how simple continuous or discrete constraints can also be handled for certain problem classes and extend these ideas to a robust optimization framework. We also show how some problems outside of this class can be embedded within the class, further extending the class of problems our framework can accommodate. Finally, we numerically validate our theoretical results with several proof-of-concept examples with synthetic and real-world data, comparing against state-of-the-art algorithms.
translated by 谷歌翻译
CS中的主要出版物场所进行的同行评审会议务必依赖每篇论文的高素质审阅者。由于这些会议的规模越来越大，它们的工作时间表以及最近明显不诚实的行为激增，现在没有其他选择以自动化的方式进行这种匹配。本文研究了一种新颖的审阅者纸匹配方法，该方法最近在第35届AAAI人工智能会议（AAAI 2021）中部署，此后已被包括ICML 2022，AAAAI 2022和IJCAI 2022的其他会议（全部或部分）采用（完全或部分） 。该方法具有三个主要元素：（1）收集和处理输入数据以识别有问题的匹配并生成审阅者纸得分； （2）制定和解决优化问题，以找到良好的审阅者纸匹配； （3）两阶段的审查过程，将审查资源从可能被拒绝的论文转移到更接近决策界的文件。本文还根据对真实数据的大量事后分析进行了对这些创新的评估，包括与AAAI先前（2020年）迭代中使用的匹配算法进行比较 - 并通过其他数值实验对此进行了补充。
translated by 谷歌翻译
随着机器学习变得普遍，减轻培训数据中存在的任何不公平性变得至关重要。在公平的各种概念中，本文的重点是众所周知的个人公平，该公平规定应该对类似的人进行类似的对待。虽然在训练模型（对处理）时可以提高个人公平性，但我们认为在模型培训（预处理）之前修复数据是一个更基本的解决方案。特别是，我们表明标签翻转是改善个人公平性的有效预处理技术。我们的系统IFLIPPER解决了限制了个人公平性违规行为的最小翻转标签的优化问题，当培训数据中的两个类似示例具有不同的标签时，发生违规情况。我们首先证明问题是NP-HARD。然后，我们提出了一种近似的线性编程算法，并提供理论保证其结果与标签翻转数量有关的结果与最佳解决方案有多近。我们还提出了使线性编程解决方案更加最佳的技术，而不会超过违规限制。实际数据集上的实验表明，在看不见的测试集的个人公平和准确性方面，IFLIPPER显着优于其他预处理基线。此外，IFLIPPER可以与处理中的技术结合使用，以获得更好的结果。
translated by 谷歌翻译
该博士学位论文的中心对象是在计算机科学和统计力学领域的不同名称中以不同名称而闻名的。在计算机科学中，它被称为“最大切割问题”，这是著名的21个KARP的原始NP硬性问题之一，而物理学的相同物体称为Ising Spin Glass模型。这种丰富的结构的模型通常是减少或重新制定计算机科学，物理和工程学的现实问题。但是，准确地求解此模型（查找最大剪切或基态）可能会留下一个棘手的问题（除非$ \ textit {p} = \ textit {np} $），并且需要为每一个开发临时启发式学特定的实例家庭。离散和连续优化之间的明亮而美丽的连接之一是一种基于半限定编程的圆形方案，以最大程度地切割。此过程使我们能够找到一个近乎最佳的解决方案。此外，该方法被认为是多项式时间中最好的。在本论文的前两章中，我们研究了旨在改善舍入方案的局部非凸照。在本文的最后一章中，我们迈出了一步，并旨在控制我们想要在前几章中解决的问题的解决方案。我们在Ising模型上制定了双层优化问题，在该模型中，我们希望尽可能少地调整交互作用，以使所得ISING模型的基态满足所需的标准。大流行建模出现了这种问题。我们表明，当相互作用是非负的时，我们的双层优化是在多项式时间内使用凸编程来解决的。
translated by 谷歌翻译
由于固有的DNN预测误差，确保解决方案可行性是开发用于解决受约束优化问题的深度神经网络（DNN）方案的关键挑战。在本文中，我们提出了一种“预防性学习”的框架，以系统地保证DNN解决方案可行性的凸起约束和一般客观函数的问题。我们首先应用预测和重建设计，不仅保证平等约束，还可以利用它们来减少DNN预测的变量的数量。然后，作为关键方法贡献，我们系统地校准了DNN训练中使用的不等式约束，从而预测预测误差并确保所得到的解决方案仍然可行。我们表征校准量大和DNN尺寸，足以确保通用可行性。我们提出了一种新的敌对样本意识到培训算法，以改善DNN的最优性能而不牺牲可行性保证。总的来说，该框架提供了两个DNN。表征足够的DNN大小的第一个可以保证通用可行性，而来自所提出的培训算法的另一个进一步提高了最优性并同时保持DNN的通用可行性。我们应用预防性学习框架来开发Deepopf +，以解决网格运行中的基本DC最佳功率流量问题。它在确保在轻负载和重载制度中的可行性和获得一致的理想加速性能时，它可以改善现有的基于DNN的方案。仿真结果对IEEE案例-30 / 118/300测试用例显示DeepoPF +与最优性损失的最优损失和最高幅度计算加速度为100 \％$ 0.5％的可行解决方案，相比之下艺术迭代求解器。
translated by 谷歌翻译
最佳套筒是将变量最佳离散化在给定离散或连续数字目标的垃圾箱中。我们提出了一种严格且可扩展的数学编程公式，用于解决二进制，连续和多级目标类型的最佳封装问题，并结合了以前未解决的约束。对于所有三种目标类型，我们介绍了凸混合组编程公式。经过精心讨论了几种算法增强功能，例如通过基于机器学习的分类器和实现方面自动确定最合适的单调趋势。新的数学编程公式是在开源Python库Optbinning中仔细实现的。
translated by 谷歌翻译
借助大量可用数据，许多企业寻求实施以数据为驱动的规范分析，以帮助他们做出明智的决定。这些规定的政策需要满足操作约束，并主动消除规则冲突，这两者在实践中无处不在。他们也需要简单且可解释，因此可以轻松地验证和实施它们。文献中的现有方法围绕构建规定决策树的变体以生成可解释的政策。但是，现有方法都无法处理约束。在本文中，我们提出了一种可扩展的方法，该方法解决了受限的规定政策生成问题。我们介绍了一种新型的基于路径的混合智能程序（MIP）公式，该计划通过列生成有效地标识了（接近）最佳策略。生成的策略可以表示为多道路拆分树，由于其较短的规则，它比二进制树更容易解释和信息。我们通过对合成数据集和真实数据集进行了广泛的实验来证明我们方法的功效。
translated by 谷歌翻译
预处理一直是优化和机器学习方面的主食技术。它通常会减少其应用于矩阵的条件数，从而加快优化算法的收敛性。尽管实践中有许多流行的预处理技术，但大多数人缺乏降低病数的理论保证。在本文中，我们研究了最佳对角线预处理的问题，以分别或同时分别或同时缩放其行或列来实现任何全级矩阵的条件数量的最大降低。我们首先将问题重新将问题重新制定为一个准凸出问题，并提供了一种基线一分配算法，该算法在实践中易于实现，其中每次迭代都包含SDP可行性问题。然后，我们建议使用$ o（\ log（\ frac {1} {\ epsilon}）））$迭代复杂度提出多项式时间潜在的降低算法，其中每个迭代均由基于Nesterov-todd方向的牛顿更新组成。我们的算法基于该问题的表述，该问题是von Neumann最佳生长问题的广义版本。接下来，我们专注于单方面的最佳对角线预处理问题，并证明它们可以作为标准双SDP问题配方，我们应用了有效的定制求解器并研究我们最佳的对角线预处理的经验性能。我们在大型矩阵上进行的广泛实验表明，与基于启发式的预处理相比，最佳对角线预处理在减少条件数方面的实际吸引力。
translated by 谷歌翻译
本研究提出了两个新的动态分配算法，将难民和寻求庇护者与东道国内的地理区域相匹配。目前在瑞士的多年来飞行员中实施的第一个，旨在通过最小不和谐的在线分配算法来最大限度地提高难民的平均预期就业水平（或利息的任何衡量结果）。尽管与后视最佳解决方案相比，所提出的算法达到了近乎最佳的预期就业，但它可能会随着时间的推移而导致定期不平衡的分配。这导致了移民资源和代理商的不良工作量低效，他们无法在地方之间移动。为了解决这个问题，第二种算法平衡了改善难民结果的目标，随着时间的推移甚至对每个地方的甚至分配。拟议方法的性能是使用来自美国最大的移民安置机构之一的真正难民移民安置数据进行说明。在此数据集上，我们发现分配平衡算法可以随着时间的推移实现接近完美的平衡，而与纯就业最大化算法相比，预期就业几乎没有损失。此外，分配平衡算法提供了许多辅助益处，包括对未知到达流量的鲁棒性，并通过更大的探索增加弹性。
translated by 谷歌翻译