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