Combinatorial Optimization with LLMs/Transformers

Research
1

I am curious whether a well-designed Transformer can do something like a job-shop-scheduling problem (JSSP) at the high level as GA and other heuristical approaches.

The logic I am coming from is that words are sequences, and JSSP can be transformed into a sequence of tasks no matter what the precedence graph looks like. And final solution would be set of tasks, as LLM makes a set of words that make a story…

I did find some literature on this, but problems are usually very small - like few dozens of tasks with very simple/streamlined rules.

1 Like
2

Yes I’d be very interested in this as well :slight_smile:

1 Like
3

Does the data in JSSP scale up now, like millions pieces of job shop schedules?

4

I’m interested in LLM4CO too! Could you share the literature about the topic please ?

5

me too. Here are some related papers found recently. But I am doubting about the promissing performance since LLMs are not that controllable:

  1. [2310.19046] Large Language Models as Evolutionary Optimizers
  2. (ICLR24-Google DeepMind) [2309.03409] Large Language Models as Optimizers
1 Like
6

Check this updating list (GitHub - FeiLiu36/LLM4Opt: A Collection on Large Language Models for Optimization) on LLM4Opt including combinatorial optimization and other related works
Here is an ICML Oral paper on LLM4CO (GitHub - FeiLiu36/EoH: Evolution of Heuristics)

7

Interesting paper that uses LLM for end-to-end optimisation in Job-shop-scheduling problem (JSSP)
LLMs can Schedule
https://arxiv.org/pdf/2408.06993

STARJOB: DATASET FOR LLM-DRIVEN JOB SHOP
SCHEDULING
https://openreview.net/pdf?id=z4Ho599uOL

1 Like
8

Interesting paper that uses LLM for end-to-end optimisation in Job-shop-scheduling problem (JSSP)
LLMs can Schedule

STARJOB: DATASET FOR LLM-DRIVEN JOB SHOP
SCHEDULING

1 Like