← Назад к портфолио EN

Графовая нейросеть для оценки разрешимости LP-задач

Инженерный прототип — ПО RiverLogic Value Chain Optimization (VCO)

Решение задачи линейного программирования (LP) только для того, чтобы установить её неразрешимость, само по себе может быть затратным. Этот прототип исследует, может ли небольшая графовая нейросеть дёшево оценивать разрешимость LP-задачи ещё до полного решения — лёгкий фильтр перед солвером VCO компании RiverLogic.

Подход

Идея: оценивать разрешимость LP-задач с помощью графовой свёрточной нейросети (GCNN) вместо запуска полного солвера. Представление LP-задачи в виде двудольного графа — научно обоснованный подход (arXiv:2012.13349, arXiv:2302.05636), и использование такого графового представления для приближённых оценок задачи также подтверждается недавними работами (Qian et al., 2024). Преобразование из матричного представления в двудольный граф (и обратно) тривиально, а готовые к использованию реализации GCNN уже существуют в PyTorch Geometric.

Данные

Для демонстрации мы заранее решили не использовать датасет реальных моделей клиентов — это потребовало бы отдельных согласований на использование данных и т.п. — а вместо этого сгенерировали синтетические: ~5000 LP-задач для обучающей выборки и ~2000 — для тестовой, с соотношением 50/50 между разрешимыми и неразрешимыми экземплярами. Поскольку это было обучение с учителем, эталонные метки разрешима/неразрешима были получены реальным решением каждой сгенерированной задачи через SciPy linprog(). Для продакшена потребовался бы репрезентативный датасет реальных моделей клиентов и промышленный LP-солвер.

Результаты

Уже в этом первом, черновом прогоне обученная модель достигла ~92% точности — с запасом на улучшение при дополнительном времени на исследования и эксперименты. Показательнее самой точности: проекция обученных эмбеддингов модели через t-SNE показывает, что разрешимые и неразрешимые LP-экземпляры разделяются на отдельные кластеры — это чёткое свидетельство того, что GCNN действительно отличает разрешимые LP от неразрешимых, а не просто подстраивается под синтетические метки (есть отдельные выбросы, которые требуют дальнейшего изучения). Предварительная оценка разрешимости настолько небольшой GCNN-моделью оказалась решаемой задачей.

По нашему опыту, полное решение VCO-моделей промышленными LP-солверами может занимать несколько часов — матричные представления таких моделей для LP-солверов весьма значительны. Такая дешёвая предварительная проверка может сэкономить клиентам существенное время и вычислительные ресурсы, отсеивая неразрешимые или грубо некорректные модели ещё до полного решения.

2D-проекция t-SNE эмбеддингов GCNN, показывающая разделение разрешимых и неразрешимых экземпляров на отдельные кластеры
2D-проекция t-SNE обученных эмбеддингов GCNN.
3D-проекция t-SNE эмбеддингов GCNN
3D-проекция t-SNE тех же эмбеддингов.

Модель

Структура экспериментальной модели, для справки (дальнейшее исследование/тюнинг потребовались бы в продакшен-треке):

import torch
from torch.nn import Linear
import torch.nn.functional as F
from torch_geometric.nn import GCNConv
from torch_geometric.nn import global_mean_pool, global_add_pool


class GCN(torch.nn.Module):
    def __init__(self, num_node_features, hidden_channels, num_classes):
        super(GCN, self).__init__()
        self.conv1 = GCNConv(num_node_features, hidden_channels)
        self.conv2 = GCNConv(hidden_channels, hidden_channels)
        self.conv3 = GCNConv(hidden_channels, hidden_channels)
        self.conv4 = GCNConv(hidden_channels, hidden_channels)
        self.lin = Linear(hidden_channels, num_classes)

    def forward(self, x, edge_index, edge_weight, batch):
        # 1. Obtain node embeddings
        x = self.conv1(x, edge_index, edge_weight)
        x = x.relu()
        x = self.conv2(x, edge_index, edge_weight)
        x = x.relu()
        x = self.conv3(x, edge_index, edge_weight)
        x = x.relu()
        x = self.conv4(x, edge_index, edge_weight)
        x = x.relu()
        # 2. Readout layer
        x = global_mean_pool(x, batch)  # [batch_size, hidden_channels]
        # 3. Apply a final classifier
        x = F.dropout(x, p=0.5, training=self.training)
        x = self.lin(x)
        return x

Или собственное print()-представление модели, что удобнее для чтения — обратите внимание, насколько она компактна для такого результата:

GCN(
  (conv1): GCNConv(4, 16)
  (conv2): GCNConv(16, 16)
  (conv3): GCNConv(16, 16)
  (conv4): GCNConv(16, 16)
  (lin): Linear(in_features=16, out_features=2, bias=True)
)

Источники