稀疏优化在数独中的应用

作者：陈永鑫; 蔡邢菊^*; 姜波

来源：中国科学:数学 , 2022, 52(02): 209-222.

• 实数编码
• 稀疏优化
• ?0范数极小化模型
• ?q(0 <q <1)范数极小化模型
• ?1/2-SLP算法

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

• 单位
  南京师范大学