Matrix Encoding Networks for Neural Combinatorial Optimization

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

arXiv · PDF · Open in the Atlas

Code that ran

We lifted 7 functions out of this paper's own repositories and ran 4 of them in a sandbox. "Ran" means the function executed on a synthesized input and returned a value. It is not a reproduction of the paper's results.

Repositories linked to this paper

• yd-kwon/MatNet — marked official in Papers with Code; named in the paper
• kaist-silab/symmetric_replay

Some links come from the archived Papers with Code dataset (CC BY-SA 4.0): attribution and licence.

Abstract

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 matrixstyle 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.

For agents

The same record, over MCP at https://syntology.ai/mcp:

get_harvested_code_for_paper("2106.11113")
get_code_for_paper("2106.11113")
have("2106.11113")

Connect an agent — have() is free.