这个问题可以使用混合整数非线性规划或任何其他优化技术来解决吗？

Question

这是问题所在：

有限集合中有 4 个整数变量 = [1, 10, 20, 40, 100, 200]。
当所有 4 连接起来时（比如 1 || 1 || 10 || 20 = 111020），结果可以被 13 整除。

我尝试了 Python 的 pyomo 库，但找不到解决方案，因为没有模运算来确定数字是否可以被 13 整除。

Answer 1

这可以 modeled 相当 straight-forwardly 使用 MiniZinc mod 销售语言，类似于 Erwin Kalvelagen 完成的 model在评论中。主要思想是为每个数字建立因数，并将其全部相乘。 MiniZinc 原生支持 mod 运算符，但并非所有求解器都能处理它。

使用 MiniZinc IDE 版本 2.4.3 中的 built-in Gecode 6.1.1 解算器找到了 108 个针对您的实例的解。 Chuffed 和 COIN-BC built-in 求解器都无法处理 model.

这种方法 model 的主要缺点是它需要建立串联的完整值。由于求解器通常具有有限的值范围可以表示，这对值的数量和大小设置了上限。例如，Gecode 基本上可以处理 32 位整数作为值。

此处提供了针对您的问题的完整 model

include "globals.mzn";

%
% Problem data
%

% The set of allowed values
set of int: Values = {1, 10, 20, 40, 100, 200};

% The number of value to concatenate
int: n = 4;


%
% Derived data
%

% The available values as an index set
set of int: Index = 1..card(Values);
% The values as an array
array[Index] of int: values = [v | v in Values];
% The length of values in decimal notation
array[Index] of int: lengths = [ceil(log10(v+1)) | v in Values];
% A mapping table from values to the widths of the numbers
array[Index, 1..2] of int: value_to_widths = array2d(Index, 1..2, [
    [values[i], 10^lengths[i]][v_or_w]
    | i in Index, v_or_w in 1..2]);
% The numbers as an index set
set of int: N = 1..4;


%
% Variables
%

% The numbers to choose
array[N] of var Values: numbers;
% The widths of the numbers
array[N] of var int: widths;
% The factors to use for concatenation
array[1..n] of var int: factors;
% The concatenation of the numbers
var int: concatenation;


%
% Constraints
%

% For each number, find the widths of it using the mapping table
constraint forall (i in N) (
    table([numbers[i], widths[i]], value_to_widths) 
);

% Find the factors to multiply numbers with for the concatenation
constraint factors[n] == 1;
constraint forall (i in 1..n-1) (factors[i] == widths[i+1] * factors[i+1]);

% Concatenate the numbers using the factors
constraint concatenation == sum(i in N) (numbers[i] * factors[i]);

% Problem constraint, the concatenation should be evenly divisible by 13
constraint concatenation mod 13 == 0;


%
% Solve and output
%

% Find solutions using standard search
% 636 failures to find all solutions using Gecode 6.1.1
%solve satisfy;

% Find solution by setting the least significant number first
% 121 failures to find all solutions using Gecode 6.1.1
solve :: int_search(reverse(numbers), input_order, indomain_min) satisfy;

% Find the smallest concatenation using the numbers
%solve minimize concatenation;

% Find the largest concatenation using the numbers
%solve maximize concatenation;

% Output both data and variables
output [
  "values=", show(values), "\n",
  "lengths=", show(lengths), "\n",
  "v_to_w={ "] ++ [show(value_to_widths[i, 1]) ++ "->" ++ show(value_to_widths[i, 2]) ++ " "|i in Index] ++ ["}\n",
  "numbers=", show(numbers), "\n",
  "widths=", show(widths), "\n",
  "factors=", show(factors), "\n",
  "concatenation=", show(concatenation), "\n",
];

以下输出包括查找所有解决方案时的第一个和最后一个解决方案，并打印统计信息

values=[1, 10, 20, 40, 100, 200]
lengths=[1, 2, 2, 2, 3, 3]
v_to_w={ 1->10 10->100 20->100 40->100 100->1000 200->1000 }
numbers=[20, 1, 1, 1]
widths=[100, 10, 10, 10]
factors=[1000, 100, 10, 1]
concatenation=20111
----------
[... lots of more solutions printed ...]
----------
values=[1, 10, 20, 40, 100, 200]
lengths=[1, 2, 2, 2, 3, 3]
v_to_w={ 1->10 10->100 20->100 40->100 100->1000 200->1000 }
numbers=[10, 40, 200, 200]
widths=[100, 100, 1000, 1000]
factors=[100000000, 1000000, 1000, 1]
concatenation=1040200200
----------
==========
%%%mzn-stat: initTime=0.000603
%%%mzn-stat: solveTime=0.003856
%%%mzn-stat: solutions=108
%%%mzn-stat: variables=15
%%%mzn-stat: propagators=12
%%%mzn-stat: propagations=8098
%%%mzn-stat: nodes=457
%%%mzn-stat: failures=121
%%%mzn-stat: restarts=0
%%%mzn-stat: peakDepth=7
%%%mzn-stat-end
Finished in 253msec

这个问题可以使用混合整数非线性规划或任何其他优化技术来解决吗？

Could this problem be solved using mixed integer non-linear programming or any other optimization technique?

python

concatenation

nonlinear-optimization

pyomo

mixed-integer-programming