Oct, 2022

SurCo：学习用于组合非线性优化问题的线性代理

PDF
TL;DR提出一种通过学习线性代理成本来优化实际应用中的组合优化问题的方法，该方法结合了基于梯度的方法的灵活性和线性组合优化的结构，通过 SurCo-hybrid、SurCo-prior 和 SurCo-zero 三种变体的实验结果表明，该方法能够产生低成本的解决方案，具有可比或更快的求解时间。
combinatorial optimizationnonlinear cost functionssurrogate costsmixed integer linear programmingend-to-end learning
发现论文，激发创造
  • 自动学习紧凑的质量感知代理，用于优化问题

    通过将优化问题表示为元变量的线性组合，我们学习了大规模优化问题的低维代理模型。通过端到端地训练低维代理模型和预测模型，我们实现了训练和推断时间的大幅减少，同时通过关注优化中的重要变量和在更平滑的空间中学习来提高性能。

    Jun, 2020

  • 图上组合优化求解器稳健性评估的通用框架

    本文提出第一个对组合优化求解器的实用鲁棒性度量方法，并针对 14 个算法和 CO 问题进行了广泛的实验，在给定时间限制下，发现目前的最先进算法（如 Gurobi）在指定的难例上的性能下降了超过 20％，使人们对组合优化求解器的鲁棒性产生担忧。

    Dec, 2021

  • 学习鲁棒组合优化：算法与应用

    该论文研究了利用神经网络在 robust combinatorial optimization 中解决 minimax optimization 问题的新方法 Learning for Robust Combinatorial Optimization (LRCO)，并通过在车载边缘计算中解决任务分配问题进行模拟，证明了 LRCO 能够大大减少最坏情况的成本和提高鲁棒性，同时具有非常低的运行时复杂度。

    Dec, 2021

  • 利用一阶替代函数进行优化

    本文研究迭代最小化目标函数代理的优化方法，通过算法变体和收敛性分析，提出一种统一的视角来看待加速近端梯度、区块坐标下降或 Frank-Wolfe 算法等一阶优化技术，并引入一种新的增量方案，实验证明与大规模机器学习优化问题中的最先进解算器匹配或超越其性能。

    May, 2013

  • 景观替代品：在部分信息下学习数学优化的决策损失

    通过使用可学习的景观代理（Landscape Surrogate）作为优化器的替代品，可以在学习集成优化中加速优化过程，提供相对稠密和平滑的梯度，在合成问题和真实世界问题中实现优化目标，同时降低对优化器的调用次数，并在计算复杂度高的高维问题上优于现有方法。

    Jul, 2023

  • 自我改进学习的可扩展神经组合优化

    提出了一种自我改进学习（Self-Improved Learning, SIL）方法，用于提高神经组合优化（neural combinatorial optimization, NCO）的可扩展性，包括有效的模型训练和解决大规模问题实例的线性复杂度注意机制。在旅行推销员问题（Travelling Salesman Problem, TSP）和容量车辆路径问题（Capacitated Vehicle Routing Problem, CVRP）上进行的全面实验证明了该方法的出色可扩展性。

    Mar, 2024

  • 预测与优化的对比损失和解决方案缓存

    本文提出了基于噪声对比法的伪损失函数方法和解决缓存方案的方法，以优化组合优化问题的预测和优化方法中的训练时间和准确性的平衡。实验证明，该方法在计算成本的一小部分之内即可与现有技术匹配。

    Nov, 2020

  • 组合优化的无监督学习需要元学习

    提出了一种基于元学习的训练流程，用于寻找未来遇到的问题实例的良好初始化而不是直接给出答案。该方法在各种评估设置下都取得了良好的实证性能。

    Jan, 2023

  • 学习代理损失

    本文提出了一种针对非可微和非可分解损失函数的优化方法，使用代理神经网络逐渐逼近真实损失函数，并通过联合双层优化学习预测模型和代理损失函数，实现了高效学习代理损失函数的效果。

    May, 2019

  • 利用平滑凸代理实现结构化预测的一般理论

    本文提出了一个理论框架来进行结构化预测，其将多标签，排序回归和图匹配等任务的损失统一了起来，并可以获得条件随机场和二次代理等现有代理方法上的新结果。

    Feb, 2019