稀疏优化在数独中的应用

• 作者: 陈永鑫 蔡邢菊 姜波
• 来源期刊: 中国科学（数学）
• 关键词: 实数编码 稀疏优化 l0范数极小化模型 lq(0l1/2-SLP算法
• 年，卷（期）: 2022,（2）
• 所属期刊栏目: 论文
• 页码范围: 209-222
• 页数: 14页
• 语种: 中文
• DOI: 10.1360/SSM-2020-0006

摘要

数独是一个难以求解的整数规划问题,可以通过实数编码的方式去除整数约束的限制,将整数规划模型转化为一个l0范数极小化模型.已有算法大多是求解松弛的l1范数极小化模型,只能求解部分数独问题.本文证明对于数独这样一个特殊的问题,lq(0＜q＜1)范数极小化模型等价于l0范数极小化模型,同时用l1/2-SLP(sequential linear programming)算法求解l1/2范数极小化模型.数值实验表明该方法可以求解更多的数独问题,本文从时间和成功率两方面验证了算法的高效性.