MiniZinc выберите подмножество продуктов - проблема категории - PullRequest
Новая
       16

MiniZinc выберите подмножество продуктов - проблема категории

0 голосов
/ 03 сентября 2018

после просмотра курса базового моделирования, я пытаюсь классифицировать свою проблему, чтобы выбрать подходящее представление модели на MiniZinc.

У меня есть ассортимент из 10 продуктов, каждый из которых имеет свои 4 специальных свойства / атрибута (таблица 4x10). Эта таблица имеет фиксированные значения. Пользователь предоставит в качестве входных данных 4 параметра. Ограничения будут созданы таким образом, чтобы пользовательские входные параметры определяли значения атрибутов продукта.

Переменная решения будет подмножеством продуктов, которые соответствуют вводу пользователя.

Насколько я понимаю, это проблема выбора подмножества из набора Объектов, есть ли какой-нибудь пример предложения, которое соответствует приведенному выше описанию модели Minizinc, чтобы посмотреть?

1 Ответ

0 голосов
/ 06 сентября 2018

Я (все еще) не совсем уверен в точной спецификации проблемы, но вот модель, которая идентифицирует все продукты, которые "ближе всего" к входным данным. Я определил «ближайший» просто как сумму абсолютных разностей между каждой характеристикой продукта и массивом input (рассчитывается функцией score). 

int: k; % number of products
int: n; % number of features

array[1..k, 1..n] of int: data;
array[1..n] of int: input;


% decision variables
array[1..k] of var int: x; % the closeness score for each product
array[1..k] of var 0..1: y; % 1: this products is nearest (as array)
% var set of 1..k: y;  % products closest to input (as set)
var int: z; % the minimum score

function var int: score(array[int] of var int: a, array[int] of var int: b) =
  let  {
     var int: t = sum([abs(a[i]-b[i]) | i in index_set(a)])
  } in
    t
;

solve minimize z;

constraint
  forall(i in 1..k) (
    x[i] = score(data[i,..], input) /\
    (y[i] = 1 <-> z = x[i]) % array 
    % (i in y <-> x[i] = z) % set
  )
  /\
  minimum(z, x)
 ;

 output [
  "input: \(input)\n",
  "z: \(z)\n",
  "x: \(x)\n",
  "y: \(y)\n\n"
]
++
[
  % using array representation of y 
  if fix(y[i]) = 1 then 
    "nearest: ix:\(i) \(data[i,..])\n" else  "" endif
  | i in 1..k
];

% data
k = 10;
n = 4;

% random features for the products
data = array2d(1..k,1..n,
 [
 3,6,7,5,
 3,5,6,2,
 9,1,2,7,
 0,9,3,6,
 0,5,2,4, % score 5
 1,8,7,9,
 2,0,2,3, % score 5
 7,5,9,2,
 2,8,9,7,
 3,6,1,2]);

 input = [1,2,3,4];
 % input = [7,5,9,2]; % exact match for product 8

Вывод: 

 input: [1, 2, 3, 4]
 z: 5
 x: [11, 10, 13, 10, 5, 15, 5, 17, 16, 10]
 y: [0, 0, 0, 0, 1, 0, 1, 0, 0, 0]

 nearest: ix:5 [0, 5, 2, 4]
 nearest: ix:7 [2, 0, 2, 3]
...