Как улучшить производительность моей модели раскраски графиков в MiniZinc?

Я создал модель для решения задачи раскраски графа в MiniZinc:

include "globals.mzn";

int: n_nodes;               % Number of nodes
int: n_edges;               % Number of edges
int: domain_ub;             % Number of colors
array[int] of int: edges;   % All edges of graph as a 1D array
array[1..n_edges, 1..2] of int: edges2d = array2d(1..n_edges, 1..2, edges);

array[1..n_nodes] of var 1..domain_ub: colors;

constraint forall (i in 1..n_edges) (colors[edges2d[i,1]] != colors[edges2d[i,2]]);

solve :: int_search(colors, dom_w_deg, indomain_random)
    satisfy;

Чтобы решить большие проблемы (около 400-500 узлов), я начинаю с верхней границы количества цветов и решаю последовательные задачи удовлетворения, уменьшая количество на единицу, пока оно не станет неудовлетворительным или истечет время ожидания. Этот метод дает мне достойные результаты.

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

constraint colors[1] = 1;
constraint forall (i in 2..n_nodes) ( colors[i] in 1..max(colors[1..i-1])+1 );

Однако это ухудшает мои результаты как по скорости, так и по качеству.

Почему моя модель плохо работает после добавления дополнительных ограничений? Как мне добавить ограничения, нарушающие симметрию?


optimization constraint-programming minizinc
person recentadvances    schedule 21.06.2020    source источник
comment
Вы можете протестировать различные стратегии поиска, которые работают лучше (indomain_random может быть не так хороша с нарушением симметрии). Кроме того, какова верхняя граница цветов (domain_ub)? Если это планарный график, достаточно 4 цветов.   -  person hakank    schedule 21.06.2020
comment
@hakank Это не планарный график. Я тестировал различные стратегии поиска, и хотя input_order с indomain_min дали немного лучшие результаты, они все равно не были сопоставимы с тем, когда я не добавлял дополнительные ограничения.   -  person recentadvances    schedule 21.06.2020
comment
@hakank Я использую minizinc пакет Python для запуска модели. Для domain_ub я запускаю цикл, начиная с максимальной степени графика и уменьшая его до тех пор, пока не достигну неудовлетворительности или не истечет время ожидания.   -  person recentadvances    schedule 21.06.2020
comment
Хорошо, тогда было бы полезно, если бы вы могли добавить (небольшой) набор данных, в котором показано это поведение.   -  person hakank    schedule 21.06.2020
comment
@hakank К сожалению, я сталкиваюсь с этой проблемой для больших наборов данных. Я пытаюсь воссоздать проблему в небольшом наборе данных, но пока безуспешно.   -  person recentadvances    schedule 22.06.2020

Ответы (2)


arrow_upward
3
arrow_downward

Для нарушения симметрии в случаях, когда значения полностью симметричны, я бы рекомендовал _ 1_, которое нарушает эту симметрию. Как прокомментировал @hakank, использование indomain_random, вероятно, не является хорошей идеей при использовании с нарушением симметрии, indomain_min - более безопасный выбор.

Для раскраски графа в целом может помочь выполнение алгоритма поиска кликов и размещение all_different ограничений для каждой найденной клики. Это необходимо сделать при создании программы minizinc для каждого экземпляра. Для сравнения см. пример раскраски графа Gecode, в котором используются предварительно вычисленные клики.

person Zayenz    schedule 22.06.2020
comment
Моя первая попытка ограничения симметрии использовала seq_precede_chain(colors). Однако это не сильно помогло. По моим наблюдениям, самый быстрый способ получить решение - это добавить только основные ограничения и указать стратегию поиска. Я также рассмотрю алгоритмы поиска кликов. Спасибо за пример! - person recentadvances; 22.06.2020
comment
При нарушении симметрии всегда возникает проблема, что ограничения нарушения симметрии могут плохо работать в сочетании с используемой стратегией поиска, но всегда стоит попробовать. - person Zayenz; 23.06.2020
comment
Теперь я понимаю, что я ищу способ динамически добавлять ограничения симметрии во время поиска. Например, если поиск использует стратегию first-fail, тогда, когда решатель выбирает вторую переменную для просмотра, она должна быть динамически ограничена, чтобы иметь только 2 значения, как объяснено в это видео. Есть ли способ сделать это в MiniZinc? - person recentadvances; 30.06.2020

arrow_upward
1
arrow_downward

Я знаю, что это старый вопрос, но я работал над той же проблемой, и я хотел написать то, что я нашел по этой теме, что, возможно, это будет полезно кому-то в будущем.

Чтобы улучшить модель, решение состоит в использовании ограничения нарушения симметрии, как и вы, но в Minizinc есть глобальное ограничение value_precede, которое можно использовать в этом случае.

% A new color J is only allowed to appear after colors 0..J-1 have been seen before (in any order)
constraint forall(j in 1..n-1)(value_precede(j, j+1, map));

При изменении эвристики поиска результат не сильно улучшился, я пробовал разные конфигурации, и лучшие результаты были получены при использовании dom_w_deg и indomain_min (по сравнению с моими файлами данных).

Другой способ улучшить результаты - принять любое достаточно хорошее решение, которое меньше количества цветов в домене. Но эта модель не всегда приводит к получению оптимального результата.

include "globals.mzn";

int: n; % Number of nodes
int: e; % Number of edges
int: maxcolors = 17; % Domain of colors

array[1..e,1..2] of int: E; % 2d array, rows = edges, 2 cols = nodes per edge
array[0..n-1] of var 0..maxccolors: c;   % Color of node n

constraint forall(i in 1..e)(c[E[i,1]] != c[E[i,2]] ); % Two linked nodes have diff color
constraint c[0] == 0; % Break Symmetry, force fist color == 0

% Big symmetry breaker. A new color J is only allowed to appear after colors
% 0..J-1 have been seen before (in any order)
constraint forall(i in 0..n-2)( value_precede(i,i+1, c)  );

% Ideally solve would minimize(max(c)), but that's too slow, so we accept any good
% enough solution that's less equal our heuristic "maxcolors"
constraint max(c) <= maxcolors;
solve :: int_search(c, dom_w_deg, indomain_min, complete) satisfy;

output [ show(max(c)+1), "\n", show(c)]

Четкое и полное объяснение можно найти здесь: https://maxpowerwastaken.gitlab.io/model-idiot/posts/graph_coloring_and_minizinc/

person Daniele F    schedule 20.11.2020