Быстрые точные решатели для хроматического числа

Question

Поиск хроматического числа графика является проблемой NP-Hard, поэтому в теории не существует быстрого решателя. Есть ли общедоступное программное обеспечение, которое может быстро вычислить точное хроматическое число графика?

Я пишу скрипт Python, который вычисляет хроматическое число многих графиков, но он занимает слишком много времени для даже небольших графов. Графики Я работаю с широким спектром графиков, которые могут быть разреженными или плотными, но обычно менее 10 000 узлов. Я сформулировал проблему как целочисленную программу и передал ее в Gurobi для решения. У вас есть рекомендации по программному обеспечению, различным рецептурам IP или другим настройкам Gurobi, чтобы ускорить это?

import networkx as nx 
from gurobipy import * 

# create test graph 
n = 50 
p = 0.5 
G = nx.erdos_renyi_graph(n, p) 

# compute chromatic number -- ILP solve 
m = Model('chrom_num') 

# get maximum number of variables necessary 
k = max(nx.degree(G).values()) + 1 

# create k binary variables, y_0 ... y_{k-1} to indicate whether color k is used 
y = [] 
for j in range(k): 
    y.append(m.addVar(vtype=GRB.BINARY, name='y_%d' % j, obj=1)) 

# create n * k binary variables, x_{l,j} that is 1 if node l is colored with j 
x = [] 
for l in range(n): 
    x.append([]) 
    for j in range(k): 
     x[-1].append(m.addVar(vtype=GRB.BINARY, name='x_%d_%d' % (l, j), obj=0)) 

# objective function is minimize colors used --> sum of y_0 ... y_{k-1} 
m.setObjective(GRB.MINIMIZE) 
m.update() 

# add constraint -- each node gets exactly one color (sum of colors used is 1) 
for u in range(n): 
    m.addConstr(quicksum(x[u]) == 1, name='NC_%d' % u) 

# add constraint -- keep track of colors used (y_j is set high if any time j is used) 
for u in range(n): 
    for j in range(k): 
     m.addConstr(x[u][j] <= y[j], name='SH_%d_%d' % (u,j)) 

# add constraint -- adjacent nodes have different colors 
for u in range(n): 
    for v in G[u]: 
     if v > u: 
      for j in range(k): 
       m.addConstr(x[u][j] + x[v][j] <= 1, name='ADJ_%d_%d_COL_%d' % (u,v,j)) 

# update model, solve, return the chromatic number 
m.update() 
m.optimize() 
chrom_num = m.objVal 

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

Answer 1

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

Решения SAT получают пропозициональную булеву формулу в Конъюнктивной нормальной форме и выводят, является ли эта формула выполнимой. Следующая проблема COL_k находится в NP:

Вход: График G и натуральное число k.

Выход: G является k-цветным.

Для решения COL_k вы кодируете его как пропозициональную булеву формулу с одной пропозициональной переменной для каждой пары (u, c), состоящей из вершины u и цвета 1 < = c < = k. Вам нужно написать предложения, которые гарантируют, что каждая вершина окрашена хотя бы одним цветом. Вы также нуждаетесь в предложениях, чтобы обеспечить правильность каждого края. Затем вы просто выполняете двоичный поиск, чтобы найти значение k такое, что G является k-раскрашиваемым, но не (k-1) -цветным. Существуют различные бесплатные решатели SAT. Я успешно использовал Lingeling, но вы можете найти много других на SAT competition website. Все они используют один и тот же формат ввода и вывода. Google «Руководство пользователя MiniSAT: как использовать Solver MiniSAT SAT» для объяснения этого формата.

Вы также можете использовать решатель Max-SAT, снова обратитесь к Max-SAT competition website. Они могут решить проблему Partial Max-SAT, в которой предложения разделены на жесткие предложения и мягкие предложения. Здесь решатель находит максимальное количество мягких предложений, которые могут быть удовлетворены, а также удовлетворяющие всем жестким предложениям, см. Формат ввода на веб-сайте конкурса Max-SAT (в разделе rules-> details).

Вы можете сформулировать проблему с хроматическим числом как одну проблему с Max-SAT (в отличие от нескольких проблем SAT, как указано выше). В этом смысле Max-SAT лучше подходит. С другой стороны, создается впечатление, что решатели SAT обычно работают лучше, чем решатели Max-SAT. У меня нет опыта с подобным решателем, поэтому я не могу сказать ничего больше.