SOS Methods vs. Metaheuristics for Multi-Objective Polynomial Optimization

This repository contains the code, data, and reproducibility artifacts for the empirical comparison reported in our paper:

Sum-of-Squares Convexity versus Metaheuristics for Multi-Objective Polynomial Optimization: An Empirical Comparison Across Synthetic and Real-World Benchmarks.

The study compares three Sum-of-Squares (SOS) based algorithms --- WCSM, PSSM, and the moment-SOS hierarchy --- against three metaheuristics --- NSGA-II, MODE, and MOEA/D --- on seven synthetic benchmark problems and one real-world application (sparse polynomial regression on the scikit-learn diabetes dataset).

Repository structure

.
├── README.md                       This file
├── INSTALL.md                      Installation instructions
├── REPRODUCE.md                    How to reproduce the paper results
├── LICENSE                         MIT
├── requirements.txt                Python dependencies
├── .gitignore
├── problems.py                     Python problem definitions (P1–P8)
├── run_metaheuristics.py           Driver: NSGA-II / MODE / MOEA/D
├── compute_metrics.py              Computes HV, spread, IGD from CSV outputs
├── statistical_tests.py            Friedman + Holm post-hoc test
├── generate_tables.py              Builds the manuscript's LaTeX tables
├── smoke_test.py                   Quick sanity check on the pipeline
│
├── matlab/                         MATLAB implementation (SOS algorithms)
│   ├── run_all_sos.m
│   ├── problems/                   p1.m … p8.m
│   ├── algorithms/                 wcsm.m, pssm.m, moment_sos.m
│   └── utils/                      simplex_weights.m, save_front.m
│
├── scripts/                        Reproducibility helpers
│   ├── build_p8_data.py            Recomputes P8 constants from sklearn diabetes
│   └── build_p8_figures.py         Recomputes P8 figures
│
├── results/                        Raw experimental outputs
│   ├── nsga2_P{1..8}_seed{1000..1029}.csv
│   ├── mode_P{1..8}_seed{1000..1029}.csv
│   ├── moead_P{1..8}_seed{1000..1029}.csv
│   ├── wcsm_P{1..8}.csv
│   ├── pssm_P{1..8}.csv             (skipped on P1, P6)
│   ├── moment_sos_P{1..8}.csv
│   ├── timings_metaheuristic.csv
│   ├── timings_sos.csv
│   ├── metrics_summary.csv
│   ├── dominance_matrix.csv
│   ├── friedman_results.csv
│   ├── posthoc_hv.csv
│   ├── posthoc_spread.csv
│   ├── posthoc_igd.csv
│   ├── reference_fronts/
│   │   └── P8.csv                  Analytical Pareto curve (200 pts)
│   └── tables/                     Auto-generated LaTeX tables
│
└── figures/                        Manuscript figures

Quick start

# 1. Clone the repo
git clone https://github.com/<your-user>/METAVSSOS.git
cd METAVSSOS

# 2. Install Python dependencies
pip install -r requirements.txt

# 3. Re-run the analysis using the bundled raw data (fast, no optimizer runs)
python compute_metrics.py
python statistical_tests.py
python generate_tables.py

To re-run the optimizers from scratch, see REPRODUCE.md.

What is included

• All raw CSV outputs from the experiments reported in the paper (~720 metaheuristic trial files plus 24 SOS output files). Reviewers can re-run the metric pipeline without re-running the optimizers.
• The analytically-computed Pareto front for P8 (results/reference_fronts/P8.csv) used as the IGD reference for the real-world problem.
• Helper scripts in scripts/ that document exactly how the P8 problem constants (Q, q, c) were derived from the scikit-learn diabetes dataset.
• Manuscript figures in both PNG and PDF.

Software environment

• Python 3.12 with pymoo 0.6.x and pymoode 0.2.x
• MATLAB R2024a with YALMIP and MOSEK 10.2 for the SOS algorithms

A MOSEK license is required to re-run the SOS experiments; free academic licenses are available from https://www.mosek.com. No MOSEK license is required to re-run the metric and statistics pipeline on the bundled raw data.

Citation

If you use this code or data, please cite our paper:

@article{TODO_REPLACE_AFTER_ACCEPTANCE,
  title   = {Sum-of-Squares Convexity versus Metaheuristics for Multi-Objective
             Polynomial Optimization: An Empirical Comparison Across Synthetic
             and Real-World Benchmarks},
  author  = {TODO},
  journal = {TODO},
  year    = {2026}
}

License

MIT — see LICENSE.

Contact

For questions about the code or data, open an issue on GitHub or contact the corresponding author.