MiniZinc Geocode не печатает все решения для CSP с включенными «всеми» решениями - PullRequest
Новая
       25

MiniZinc Geocode не печатает все решения для CSP с включенными «всеми» решениями

1 голос
/ 12 мая 2019
Проблема

С solve minimize Я получаю только одно решение, хотя существует несколько оптимальных решений.Я включил распечатку нескольких решений в конфигурациях решателя.Другие оптимальные решения находятся с solve satisfy вместе с неоптимальными решениями.

Возможные причины

Может ли быть так, что кардинальная функция card() ранжируется по значению перечисления, где размер равен двумнаборы равны?Другими словами, что card(A, B) > card(B, C)?Если да, нужно ли переключать представление моих вершин?

Программа

Я создаю программу MiniZinc для нахождения минимального покрытия вершин данного графа.График в этом примере выглядит следующим образом:

Example graph

При минимальном разрешении вершинного покрытия: [{A, B, C, E}, {A, B, E, F}, {A, C, D, E}, {B, C, D, E}, {B, C, D, F}, {B, D, E, F}]. Мой код выводит только {A, B, C, E}.

Файл данных: 

VERTEX = {A, B, C, D, E, F};

edges = [|1, 0, 1, 0, 0, 0, 0, 0, 0
         |1, 1, 0, 1, 1, 0, 0, 0, 0
         |0, 1, 0, 0, 0, 1, 1, 0, 0
         |0, 0, 1, 1, 0, 0, 0, 1, 0
         |0, 0, 0, 0, 1, 1, 0, 1, 1
         |0, 0, 0, 0, 0, 0, 1, 0, 1|];

Программа расчета: 

% Vertices in graph
enum VERTEX;

% Edges between vertices
array[VERTEX, int] of int: edges;

int: num_edges = (length(edges) div card(VERTEX));

% Set of vertices to find
var set of VERTEX: span;

% Number of vertices connected to edge resulting from span
array[1..num_edges] of var 0..num_edges: conn;

% All edges must be connected with at least one vertex from span
constraint forall(i in 1..num_edges)
           (conn[i] >= 1);

% The number of connections to each edge is the number of vertices 
% in span with a connection to that edge
constraint forall(i in 1..num_edges)
           (conn[i] = sum([edges[vert,i]| vert in span]));

% Minimize the number of vertices in span
solve minimize card(span);

Ответы [ 2 ]

4 голосов
/ 12 мая 2019

solve minimize показывает только одно оптимальное решение (в некоторых случаях могут также отображаться промежуточные значения).

Если вам нужны все оптимальные решения, вы должны использовать solve satisfy и , добавить ограничение с оптимальным значением: 

constraint card(span) = 4;

Затем модель выведет все 6 оптимальныхрешения: 

card(cpan): 4
span: {A, B, C, E}
conn: [2, 2, 1, 1, 2, 2, 1, 1, 1]
----------
card(cpan): 4
span: {B, C, D, F}
conn: [1, 2, 1, 2, 1, 1, 2, 1, 1]
----------
card(cpan): 4
span: {A, C, D, E}
conn: [1, 1, 2, 1, 1, 2, 1, 2, 1]
----------
card(cpan): 4
span: {B, C, D, E}
conn: [1, 2, 1, 2, 2, 2, 1, 2, 1]
----------
card(cpan): 4
span: {A, B, E, F}
conn: [2, 1, 1, 1, 2, 1, 1, 1, 2]
----------
card(cpan): 4
span: {B, D, E, F}
conn: [1, 1, 1, 2, 2, 1, 1, 2, 2]
----------
==========

Примечание: я добавил раздел output, чтобы показать все значения: 

output [
   "card(cpan): \(card(span))\n",
   "span: \(span)\n",
   "conn: \(conn)"
];
2 голосов
/ 13 мая 2019

Альтернативным решением является использование OptiMathSAT (v. 1.6.3) .

При запросе всех решений в режиме оптимизации решатель возвращает все решения (относительно выходных переменных) с одинаковым оптимальным значением.

Пример: 

~$ mzn2fzn test.mzn test.dzn                                        # your instance
~$ optimathsat -input=fzn -opt.fzn.all_solutions=True < test.fzn 
% allsat model
span = {2, 4, 5, 6};
conn = array1d(1..9, [1, 1, 1, 2, 2, 1, 1, 2, 2]);
----------
% allsat model
span = {1, 3, 4, 5};
conn = array1d(1..9, [1, 1, 2, 1, 1, 2, 1, 2, 1]);
----------
% allsat model
span = {1, 2, 3, 5};
conn = array1d(1..9, [2, 2, 1, 1, 2, 2, 1, 1, 1]);
----------
% allsat model
span = {1, 2, 5, 6};
conn = array1d(1..9, [2, 1, 1, 1, 2, 1, 1, 1, 2]);
----------
% allsat model
span = {2, 3, 4, 5};
conn = array1d(1..9, [1, 2, 1, 2, 2, 2, 1, 2, 1]);
----------
% allsat model
span = {2, 3, 4, 6};
conn = array1d(1..9, [1, 2, 1, 2, 1, 1, 2, 1, 1]);
----------
=========

Основное преимущество по отношению к. подход, представленный в принятом ответе, заключается в том, что OptiMathSAT имеет значение incremental , что означает, что инструмент ищет другие решения без перезапуска, так что он может повторно использовать любую полезную информацию, которая была ранее сгенерирована, для ускорения поиск (например, теоретические леммы). [CAVEAT: это может быть не актуально для небольших случаев; Кроме того, другие решатели MiniZinc могут работать быстрее, в зависимости от проблемы ввода]

Примечание: обратите внимание, что OptiMathSAT не печатает метки каждого VERTEX, поскольку компилятор mzn2fzn удаляет эти метки при компиляции файла. Однако сопоставление чисел и меток должно быть очевидным.

Раскрытие информации: Я один из разработчиков этого инструмента.

...