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

The Issue

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

Possible causes

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

The Program

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

Пример графика

При минимальном покрытии вершины: [{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);

minizinc optimathsat
person Mats    schedule 12.05.2019    source источник

Ответы (2)


arrow_upward
4
arrow_downward

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)"
];
person hakank    schedule 12.05.2019
comment
Спасибо, что прояснили это. Я собираюсь использовать этот код в ряде примеров - можно ли динамически установить constraint card(span) на наименьшее найденное число? - person Mats; 12.05.2019
comment
@Matsern Извините, но нет, вам нужно сначала запустить minimize, а затем добавить ограничение. Я предлагаю вам запустить это с помощью программы-оболочки, которая выполняет эти шаги. - person hakank; 13.05.2019

arrow_upward
2
arrow_downward

Альтернативным решением является использование 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 является инкрементным, что означает, что инструмент ищет другие решения без перезапуска, так что он может повторно использовать любую полезную информацию, которая была ранее сгенерирована для ускорения. вверх по поиску (например, леммы теории). [ПРЕДОСТЕРЕЖЕНИЕ: это может не иметь отношения к небольшим случаям; кроме того, другие решатели MiniZinc могут быть быстрее в зависимости от проблемы ввода]

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

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

person Patrick Trentin    schedule 13.05.2019