PaperlayerView exact revision on arXiv

Source-linked AI summary

Matrix Encoding Networks for Neural Combinatorial Optimization

Yeong-Dae Kwon, Jinho Choo, Iljoo Yoon, Minah Park, Duwon Park, Youngjune Gwon

arXiv:2106.11113v2cs.LG

TL;DR

Matrix-structured combinatorial optimization problems lacked a neural encoder suited to their relationship data. The paper introduces MatNet, which encodes such matrices for end-to-end solvers. It reports near-optimal ATSP and FFSP solutions and substantially better FFSP performance than conventional operations-research methods on the tested instances.

  • Problem

    Neural combinatorial optimization lacked a model for encoding matrix-type relationship data used by important problems such as ATSP and scheduling.

  • Method

    MatNet encodes matrix relationships into representations of two item classes and serves as a front-end for end-to-end reinforcement-learning solvers.

  • Results

    MatNet achieves near-optimal ATSP and FFSP solutions, while its FFSP solver substantially outperforms conventional mixed-integer programming and meta-heuristic methods on tested instances.

  • Takeaways & Limitations

    The results extend neural combinatorial optimization to matrix-structured problems and show particularly strong empirical performance for the investigated FFSP instances.

  • Takeaways & Limitations

    The experiments use end-to-end reinforcement learning, while broader real-world constraint combinations and hybrid ML–OR models require further research.

Abstract

from arXiv · show

Machine Learning (ML) can help solve combinatorial optimization (CO) problems better. A popular approach is to use a neural net to compute on the parameters of a given CO problem and extract useful information that guides the search for good solutions. Many CO problems of practical importance can be specified in a matrix form of parameters quantifying the relationship between two groups of items. There is currently no neural net model, however, that takes in such matrix-style relationship data as an input. Consequently, these types of CO problems have been out of reach for ML engineers. In this paper, we introduce Matrix Encoding Network (MatNet) and show how conveniently it takes in and processes parameters of such complex CO problems. Using an end-to-end model based on MatNet, we solve asymmetric traveling salesman (ATSP) and flexible flow shop (FFSP) problems as the earliest neural approach. In particular, for a class of FFSP we have tested MatNet on, we demonstrate a far superior empirical performance to any methods (neural or not) known to date.

1 Introduction

The paper targets matrix-structured combinatorial optimization problems, for which existing neural front-end models lack a suitable encoder. It introduces MatNet and applies it to ATSP and FFSP, reporting near-optimal solutions and especially strong FFSP performance.

  • Motivation: Existing neural combinatorial optimization models do not encode matrix-type relationship data, limiting the problems ML engineers can address.The paper highlights distance-matrix ATSP, scheduling, and assignment problems as important affected examples.
  • Contribution: MatNet encodes relationship matrices into representations of items in two classes.The matrix D stores the relationships between the two item groups.
  • Contribution: MatNet-based end-to-end reinforcement-learning models solve ATSP and FFSP, which had not previously been solved using deep neural networks.The authors report near-optimal solutions for both problem classes.
  • Results: For investigated FFSP instances, MatNet substantially outperforms conventional operations-research methods, including mixed integer programming and meta-heuristics.The paper presents this as its strongest empirical result.

2 Related work

Prior neural combinatorial optimization work encodes sequences, graphs, or fully connected node sets, but does not directly embed a single relationship matrix. MatNet addresses this matrix-specific setting through bipartite graph encoding.

  • Sequence and graph encoders: RNN-based pointer networks encode variable-length sequences of problem items and have been combined with reinforcement learning for neural optimization.These approaches process ordered inputs such as Cartesian coordinates.
  • Sequence and graph encoders: Graph neural networks learn message-passing policies for arbitrary graphs and have been applied uniformly across several graph-based optimization problems.The cited work includes graph convolutional extensions.
  • Transformer encoders: Transformer-style encoders simultaneously represent nodes in routing problems, typically using Cartesian coordinates without matrix edge weights.These models target TSP and related routing problems.
  • Matrix-specific gap: A general GNN performs worse on fixed, dense matrix-like graphs than specialized neural routing models in the cited TSP comparison.The reported comparison is above 8% error versus below 0.2% error on random 100-city instances.
  • Matrix-specific gap: The paper positions MatNet as a bipartite graph encoder for single matrices, distinct from prior work using bipartite or matrix embeddings for other purposes.Related examples include MIP variable selection and weapon-target assignment.

3 Model architecture

MatNet encodes a weighted complete bipartite graph by updating the two node classes separately and incorporating matrix edge weights into attention. Its trainable mixed-score attention preserves permutation invariance while retaining efficient matrix computation.

  • Bipartite representation: MatNet represents matrix D as weighted edges e(ai, bj) between nodes in two sets A and B.The architecture operates on a complete bipartite graph.
  • Dual graph attentional layer: Each layer uses separate update functions for A-nodes and B-nodes, allowing class-specific representation strategies.The dual structure is implemented as two sub-blocks in every graph-attentional layer.
  • Dual graph attentional layer: MatNet replaces self-attention with cross-attention between one node class and the other, using the opposite class as key-value inputs.The architecture stacks L dual graph-attentional layers.
  • Mixed-score attention: Mixed-score attention combines learned internal attention scores with external relationship scores Dij before SoftMax.This allows the matrix values to directly affect attention weights.
  • Mixed-score attention: A separate trainable element-wise MLP in each attention head learns how to combine the two scores while preserving permutation invariance.Different heads can emphasize one score type or balance both.
  • Implementation: The inserted MLP retains efficient matrix-multiplication implementation without explicit row, column, or head loops.This preserves the efficient computational form of Transformer attention.
  • Initial node representations: Zero-vector embeddings support variable numbers of A-nodes, whereas one-hot B-node embeddings require a predefined maximum Nmax.Random initial vectors remove the Nmax restriction but slightly worsen performance.

4 Asymmetric traveling salesman problem

The ATSP experiments use MatNet to encode asymmetric distance matrices and autoregressively decode tours. Across baseline comparisons, instance augmentation substantially reduces the optimality gap, reaching 0.01% for 20-city ATSP and below 1% for 100-city ATSP.

  • Problem and model: ATSP minimizes round-trip distance over a city permutation without requiring d(ai, bj) = d(aj, bi).The asymmetric distance matrix supplies the pairwise inputs to MatNet.
  • Problem and model: MatNet encodes the ATSP distance matrix with a fixed architecture across problem sizes, using stacked attention layers and separate A- and B-node embeddings.The reported configuration uses five encoding layers and 16 attention heads.
  • Decoder and training: The decoder constructs a tour autoregressively, using current and first-city representations in its query and assigning probabilities to all destination cities.The first city is included because the tour must return to its starting point.
  • Decoder and training: POMO training generates tours from different starting cities and uses their average length as the REINFORCE baseline.Inference generates parallel solutions and selects the best one.
  • Evaluation: The ATSP evaluation compares average tour length, optimality gap, and runtime on 10,000 test instances against MIP and heuristic baselines.Runtime accounting excludes program and matrix loading times.
  • Baselines: LKH3 is a state-of-the-art local-search baseline that finds optimal solutions for most tested instances in short runtimes, despite lacking an optimality guarantee.It iteratively improves tours with k-opt operations.
  • Results: 0.01% optimality gap is achieved for 20-city ATSP with 128-way instance augmentation, while the gap is below 1% for 100-city ATSP.The augmented method selects the best solution among 128 random one-hot embedding assignments.

5 Flexible flow shop problem

The FFSP section defines flexible flow-shop scheduling and describes a MatNet-based solver that encodes stage-specific processing-time matrices to generate schedules. Experiments cover three problem sizes and compare MatNet with conventional optimization methods.

  • Problem definition: FFSP schedules N jobs through S > 1 ordered stages, each containing M > 1 machines, minimizing the completion time of all jobs.Each job may use any machine within a stage, while each machine processes at most one job at a time.
  • Experimental setting: The experiments fix three stages with four machines each and represent every instance using three M-by-N processing-time matrices.Processing times are random integers between 2 and 9 for the tested instances.
  • Encoding and decoding: MatNet uses one encoder per stage matrix, producing stage-wise machine and job representations for the scheduling decisions.Three identically configured decoders select jobs for machines at each stage, with unavailable jobs masked and a skip option available.
  • Schedule generation and training: The decoder constructs a schedule by traversing stages and assigning jobs to their four machines while completing a Gantt chart.Machine-assignment order can be permuted, producing 24 trajectories used by POMO reinforcement learning.
  • Inference: Sampled solutions are significantly better than greedily chosen solutions during inference, although each stage decoder lacks information about the other stages.Inference uses POMO with the same 24 machine-order permutations used during training.
  • Comparison with baselines: MatNet-based schedules significantly outperform conventional OR approaches in both solution quality and runtime, including tests with ample single-instance time budgets.The comparison includes MIP, greedy heuristics, genetic algorithms, and particle swarm optimization.

6 Conclusion and Discussion

The paper concludes that MatNet enables deep-learning approaches for matrix-based ATSP and FFSP problems, with especially strong FFSP performance against conventional methods. It also identifies broader real-world constraint combinations and hybrid ML–OR models as directions for further work.

  • Contributions: MatNet encodes matrix-style relationship data and supports deep-learning solutions for ATSP and FFSP.The paper presents these as classical optimization problems solved using a deep learning approach.
  • Results: The MatNet-based FFSP solver significantly outperforms other algorithms, extending neural optimization beyond the narrow class of problems commonly studied.The authors characterize such strong neural heuristic performance as rare for classical optimization problems.
  • Future work: More research is needed to represent combinations of many different constraints found in real-world problems.This is the paper’s stated scope boundary for future work.
  • Discussion: The experiments use end-to-end reinforcement learning for simplicity, while the MatNet encoder could also support hybrid ML and OR models.The authors state that hybrid models may offer better performance and broader applicability.

A.1 Multiple data matrices

MatNet extends mixed-score attention to multiple relationship matrices and explores alternative update and initialization schemes. These variants trade flexibility, model size, and performance against computational or representational constraints.

  • Multiple data matrices: MatNet can encode multiple relationship matrices using mixed-score attention with an MLP that combines f+1 inputs.The additional inputs represent the f data matrices plus the internally generated attention score.
  • Alternative encoding sequences: Sequentially applying F_A and F_B, rather than updating both groups in parallel, empirically improves performance in some experiments.The alternative applies one update function first and uses the updated representations in the second update.
  • Alternative initial node embeddings: Nodes in group B need mutually distinct initial vectors, but these vectors need not be one-hot.Learnable vectors can remove the fixed N_max limit, while random per-instance vectors remove it entirely at slightly worse performance.
  • Single update function: Sharing one update function between groups A and B nearly halves model size, with relatively small performance degradation especially when the groups are similar.The change does not reduce training speed, inference speed, or GPU memory usage.
  • ATSP formulation: The ATSP appendix describes Miller–Tucker–Zemlin constraints that enforce one visit per city and prevent subtours.Constraints B.4 and B.5 impose one visit per city; B.6 ensures a single tour.

C Instance augmentation vs. sampling

The appendix compares instance augmentation with sampling for ATSP across problem sizes using 10,000 instances. Instance augmentation produces diverse solutions but takes somewhat more time.

  • Comparison: Instance augmentation and sampling are compared on ATSP instances of different sizes using 10,000 instances.The comparison includes the same results reported in the main text for two data rows.
  • Comparison: Instance augmentation takes slightly more time than sampling while generating diverse solutions through varied embeddings.Different embedding sets create different encodings of the same problem instance.

D Euclidean TSP Experiment

The Euclidean TSP experiment evaluates MatNet against established neural baselines using distance matrices derived from shared city coordinates. MatNet remains competitive despite targeting a broader class of TSP inputs.

  • Experimental setup: The comparison uses symmetric distance matrices generated from the same x,y coordinates used by other neural TSP methods.This setup gives those methods an advantage because they directly use the coordinate representation.
  • Benchmark comparison: MatNet’s Euclidean TSP solver remains competitive with the AM model trained by POMO.The AM baseline is a Transformer-based construction method specialized for Euclidean TSP, whereas MatNet handles a broader range of TSP problems.
  • Ablation study: Removing graph embedding from the QUERY token has negligible effect on the ATSP solver.The attention mechanism can still incorporate aggregate node information into node representations when useful.

F Training curves

The supplied training-curve material identifies ATSP and FFSP curve figures and documents the FFSP formulation and heuristic baselines. The FFSP instances use randomly generated processing times for unrelated parallel machines.

  • ATSP training: Figure F.1 reports the training curve of the MatNet-based ATSP solver on 100-city instances.
  • FFSP training: Figure F.2 reports the training curve of the MatNet-based FFSP solver on 100-job instances.
  • FFSP setting: The FFSP experiments use randomly generated processing-time matrices, making machines within a stage unrelated.This setting is less realistic than identical-machine models but can adapt more naturally to real-world problems.
  • FFSP formulation: The FFSP formulation assigns jobs to machines, models within-stage precedence, and tracks completion times.The cited constraints enforce machine assignment and precedence relationships.
  • Baselines: The genetic algorithm and particle swarm optimization serve as heuristic baselines with explicit solution representations and iterative search procedures.PSO uses 25 particles and 1,000 iterations per instance.

H Generalization performance on FFSP

MatNet handles variable-sized FFSP matrices and generalizes to test instances with job counts far beyond those used in training.

  • MatNet encodes matrices with an arbitrary number of rows or columns, supporting FFSP instances whose job counts vary.This flexibility matches settings where the number of jobs changes while the machine count remains fixed.
  • 1,000 test jobs were handled reasonably well by models trained on instances containing only 20, 50, or 100 jobs.Table H.1 evaluates 1,000 instances at test sizes of 20, 50, 100, and 1,000, using ×128 instance augmentation for inference.
  • Table H.1 reports generalization-test results for MatNet-based FFSP solvers across 1,000 instances.

I One-instance FFSP

In one-instance FFSP experiments, MatNet produced much better solutions within seconds, while MIP and metaheuristic baselines improved only slightly despite many more hours of search.

  • The experiments used selected FFSP instances with processing-time matrices shown for N = 20, 50, and 100.
  • MatNet produced much better FFSP solutions in seconds than MIP and metaheuristic approaches achieved after many more hours.The comparison used one manually selected instance for each FFSP size N = 20, 50, and 100.
  • The one-instance results are reported in Table I.1.
Loading 2106.11113v2…