java - CPLEX 中的数独求解器

Question

我正在尝试解决我创建的数独程序。这是目标函数

IloNumExpr numExpr = cplex.linearNumExpr();
cplex.addMaximize(numExpr);

我想做的是添加一个约束或新的目标函数，允许 9x9 数独矩阵中的四个角点按照 5 > 7 > 4 > 的顺序具有特殊偏好6 > 8 > 2 > 3 > 9 > 1

关于完成这个需要什么数学公式有什么想法吗？

Answer 1

您可以通过向目标函数添加元素来强加偏好顺序。

假设您有类型的变量

选择[行][列][数字]

如果 choose[2][3][8] = 1 表示正方形 (2,3) 的值为 8。

四个角是:1,1; 1,9;9,1; 9,9

基本上，您需要将以下内容添加到现有的目标函数中。

9 x choose[1][1][5] + 8 x choose[1][1][7] + 7 x choose[1][1][4] + ... + 2 x choose[1][1][9] + 1 x choose[1][1][1]
9 x choose[1][9][5] + 8 x choose[1][9][7] + 7 x choose[1][9][4] + ... + 2 x choose[1][9][9] + 1 x choose[1][9][1]
9 x choose[9][1][5] + 8 x choose[9][1][7] + 7 x choose[9][1][4] + ... + 2 x choose[9][1][9] + 1 x choose[9][1][1]
9 x choose[9][9][5] + 8 x choose[9][9][7] + 7 x choose[9][9][4] + ... + 2 x choose[9][1][9] + 1 x choose[9][9][1]

在 CPLEX 中

//偏好顺序:5 > 7 > 4 > 6 > 8 > 2 > 3 > 9 > 1

  int[]  preferenceOrder;
  preferenceOrder[1] = 9;
  preferenceOrder[2] = 8;  
  preferenceOrder[8] = 2; 
  preferenceOrder[9] = 1;
  cplex.addMaximize(cplex.scalProd(preferenceOrder, choose));

为什么这有效？

CPLEX 求解器尝试最大化 obj 函数的值。在其他条件相同的情况下，它将首先尝试使 choose[1][1][5] 为 1，然后尝试将其设为 7，依此类推。