组合优化问题的求解方法和系统.pdf

(19)国家知识产权局(12)发明专利申请(10)申请公布号CN114595641A(43)申请公布日2022.06.07(21)申请号202210495655.5G06F111/04(2020.01)(22)申请日2022.05.09G06F111/06(2020.01)(71)申请人支付宝（杭州）信息技术有限公司地址310000浙江省杭州市西湖区西溪路556号8层B段801-11(72)发明人王贵阳刘子奇沈文博周俊华致刚(74)专利代理机构北京汇思诚业知识产权代理有限公司11444专利代理师周放(51)Int.Cl.G06F30/27(2020.01)G06K9/62(2022.01)G06N3/04(2006.01)G06N3/08(2006.01)权利要求书2页说明书13页附图4页(54)发明名称组合优化问题的求解方法和系统(57)摘要本说明书提供的组合优化问题的求解方法和系统，通过分支定界算法求解组合优化问题的实施例，并将求解实施例过程中的每个分支节点的约束和松弛解以及节点对应的强分支作为样本数据，来训练决策模型。所述求解方法和系统在对目标组合优化问题求解过程中，基于分支定界算法，在每个分支节点，将分支节点对应的约束和松弛解输入至训练好的决策模型中，并输出当前节点对应的强分支，从而基于决策模型来模拟分支定界过程中的分支过程，快速找到分支节点中的强分支，无需对每个分支进行求解，大大缩短计算时间，从而加快组合优化问题的求解速度。CN114595641ACN114595641A权利要求书1/2页1.一种组合优化问题的求解方法，包括：获取目标组合优化问题的目标优化模型，所述目标优化模型包括优化目标函数、目标约束以及决策变量，所述决策变量中的至少部分为整数规划变量；基于分支定界法对所述目标优化模型进行求解，确定目标解，包括对每个分支节点：基于预先训练好的决策模型确定当前分支节点对应的目标强分支，所述决策模型是基于历史优化模型在通过分支定界算法求解过程中的每个样本分支节点的样本数据及其对应的样本决策训练得到的，所述样本数据包括当前样本分支节点对应的样本约束以及样本变量的松弛解，所述样本决策包括所述当前样本分支节点对应的样本强分支；以及输出所述目标解。2.如权利要求1所述的组合优化问题的求解方法，其中，所述目标组合优化问题为目标人群圈定问题，所述历史优化模型与所述目标优化模型为同类模型。3.如权利要求1所述的组合优化问题的求解方法，其中，所述样本数据包括二部图结构。4.如权利要求3所述的组合优化问题的求解方法，其中，所述二部图结构包括所述当前样本分支节点对应的多个样本约束、多个样本变量的松弛解以及连接所述多个样本约束和所述多个样本变量的松弛解的边。5.如权利要求1所述的组合优化问题的求解方法，其中，所述决策模型为图卷积神经网络模型。6.如权利要求1所述的组合优化问题的求解方法，其中，在所述决策模型的训练过程中，基于仿射变换对所述样本数据进行初始化。7.如权利要求1所述的组合优化问题的求解方法，其中，在所述决策模型的训练过程中，基于最小化交叉熵损失函数对所述决策模型进行训练。8.如权利要求1所述的组合优化问题的求解方法，其中，所述基于预先训练好的决策模型确定当前分支节点对应的目标强分支，包括：确定所述当前分支节点对应的当前优化模型，所述当前优化模型包括所述优化目标函数、当前约束以及所述决策变量；基于松弛算法，确定所述当前优化模型对应的所述决策变量的当前松弛解；以及将所述当前约束以及所述当前松弛解输入至所述决策模型中，确定所述当前分支节点对应的所述目标强分支。9.如权利要求8所述的组合优化问题的求解方法，其中，所述将所述当前约束以及所述当前松弛解输入至所述决策模型中，确定所述当前分支节点对应的所述目标强分支，包括：确定所述当前分支节点对应的两个分支；将所述当前约束以及所述当前松弛解输入至所述决策模型中，确定所述当前分支节点对应的所述两个分支的概率；以及将所述两个分支中概率高的一个分支作为所述目标强分支。10.一种组合优化问题的求解系统，包括：至少一个存储介质，存储有至少一个指令集，用于对组合优化问题进行求解；以及至少一个处理器，同所述至少一个存储介质通信连接，其中，当所述组合优化问题的求解系统运行时，所述至少一个处理器读取所述至少一2CN114595641A权利要求书2/2页个指令集，并且根据所述至少一个指令集的指示执行权利要求1‑9中任一项所述的组合优化问题的求解方法。3CN114595641A说明书1/13页组合优化问题的求解方法和系统技术领域[0001]本说明书涉及整数规划技术领域，尤其涉及一种组合优化问题的求解方法和系统。背景技术[0002]很多组合优化问题都可以被形式化建模成为（混合）整数规划问题来进行求解。组合优化问题的特