MPaGE uses LLMs to automatically design heuristics for multi-objective combinatorial optimization (MOCO), balancing runtime, solution quality, and semantic diversity. It combines the SEMO paradigm with Pareto Front Grid guidance and LLM-based heuristic generation.

Paper: MPaGE: Pareto-Grid-Guided Large Language Models for Fast and High-Quality Heuristics Design in Multi-Objective Combinatorial Optimization

MPaGE partitions the objective space into grids, keeps leading individuals from promising regions, and uses LLMs to cluster heuristics by semantic structure. Variation is performed across clusters to promote diversity and reduce redundancy.

• Python 3.8+
• OpenAI API key (or compatible endpoint)

git clone https://github.com/langkhachhoha/MPaGE.git
cd MPaGE
pip install -r requirements.txt

Create two files in the project root with your API key:

• secret.txt — main LLM for heuristic generation
• secret_cluster.txt — LLM for semantic clustering (can be the same key)

Each file: one line, the API key only.

python main.py

Edit main.py to switch problems and tune parameters:

Problems (uncomment one):

• BITSPEvaluation — Bi-objective TSP (default)
• TRITSPEvaluation — Tri-objective TSP
• BICVRPEvaluation — Bi-objective CVRP
• BIKPEvaluation — Bi-objective Knapsack

LLM (OpenAI example):

llm = HttpsApiOpenAI(
    base_url='https://api.openai.com',
    api_key=llm_api_key,
    model='gpt-4o-mini',  # or 'gpt-4', 'gpt-3.5-turbo'
    timeout=30
)

MPaGE parameters:

Results are written to logs/YYYYMMDD_HHMMSS_Problem_MPaGE/:

• run_log.txt — execution log
• population/generation_*.json — population per generation
• samples/samples_0~*.json — generated heuristics

Metrics: hypervolume, runtime, Pareto front size.

Evaluation on four MOCO benchmarks:

Add a new directory under llm4ad/task/optimization/ with:

• evaluation.py — fitness evaluation
• get_instance.py — data loading
• template.py — heuristic template and problem description
• paras.yaml — parameters

See existing problems (bi_tsp_semo, bi_cvrp, etc.) as reference.

@misc{ha2025paretogridguidedlargelanguagemodels,
  title={Pareto-Grid-Guided Large Language Models for Fast and High-Quality Heuristics Design in Multi-Objective Combinatorial Optimization},
  author={Minh Hieu Ha and Hung Phan and Tung Duy Doan and Tung Dao and Dao Tran and Huynh Thi Thanh Binh},
  year={2025},
  eprint={2507.20923},
  archivePrefix={arXiv},
  primaryClass={cs.NE},
  url={https://arxiv.org/abs/2507.20923},
}