Using machine learning to solve combinatorial optimization (CO) problems is challenging, especially when the data is unlabeled. This work proposes an unsupervised learning framework for CO problems. Our framework follows a standard relaxation-plus-rounding approach and adopts neural networks to parameterize the relaxed solutions so that simple back-propagation can train the model end-to-end. Our key contribution is the observation that if the relaxed objective satisfies entry-wise concavity, a low optimization loss guarantees the quality of the final integral solutions. This observation significantly broadens the applicability of the previous framework inspired by Erdos' probabilistic method. In particular, this observation can guide the design of objective models in applications where the objectives are not given explicitly while requiring being modeled in prior. We evaluate our framework by solving a synthetic graph optimization problem, and two real-world applications including resource allocation in circuit design and approximate computing. Our framework largely outperforms the baselines based on na\"{i}ve relaxation, reinforcement learning, and Gumbel-softmax tricks.
翻译:使用机器学习解决组合优化(CO)问题是一项艰巨的任务, 特别是在数据没有标签的情况下。 这项工作提议了一个不受监督的CO问题学习框架。 我们的框架遵循标准的放松加四舍五入方法, 并采用神经网络来参数化宽松的解决方案, 以便简单的后向方案能够对模型端到端进行训练。 我们的主要贡献是观察到, 如果放松的目标满足了进取的调和, 低优化损失可以保证最终整体解决方案的质量。 这一观察极大地扩大了由Erdos的概率方法所启发的前一个框架的适用性。 特别是, 这一观察可以指导在没有明确给出目标但需要事先建模的应用中客观模型的设计模式。 我们通过解决合成图形优化问题来评估我们的框架, 以及两个真实世界的应用, 包括电路设计和近似计算中的资源分配。 我们的框架基本上超越了基于 NA\ {i} 放松、 强化学习 和 Gumbel- softmax 的基线 。