Pith. sign in

REVIEW 3 major objections 5 minor 14 references

Graph-Supported Dynamic Algorithm Configuration for Multi-Objective Combinatorial Optimization

T0 review · 3 major / 5 minor · reviewed 2026-08-07 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read A deep reinforcement learning agent that reads the current solution population as a graph can dynamically configure multi-objective evolutionary algorithms, beating static tuning and earlier DRL-based configuration and generalizing across…

desk verdict A real graph-state contribution for DRL-based MOEA configuration, but the headline win over static baselines is weakened by test-set tuning. read the letter →

arxiv 2505.16471 v2 pith:TBKYEBGP submitted 2025-05-22 cs.NE cs.LG

Robbert Reijnen , Yaoxin Wu , Zaharah Bukhsh , Yingqian Zhang This is my paper · ORCID
classification cs.NEcs.LG MSC 90C2790C2968T20
keywords dynamicalgorithmconfigurationmulti-objectivecombinatorialoptimizationgraphneuralnetworkdeepreinforcementlearningevolutionaryhypervolumerewardflexiblejobshopschedulingcapacitatedvehiclerouting
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

GS-MODAC claims that the state of a multi-objective evolutionary search is best represented as a graph of the current solutions in objective space, and that a deep reinforcement learning agent trained on that graph can choose the algorithm's parameters from one generation to the next more effectively than static tuning or earlier DRL-based configuration. The target problems are combinatorial—flexible job-shop scheduling and capacitated vehicle routing—where earlier dynamic configuration approaches, built for continuous benchmarks, lose traction. The paper's proposed answer is to let a graph neural network learn the state from normalized objective values and Pareto-front structure, with an instance-agnostic reward based on hypervolume improvement, so no hand-crafted state features are needed. If the results hold, automatic dynamic parameter control becomes practical for a class of NP-hard problems where tuning is currently expensive and static settings waste performance.

What carries the argument

The central object is the graph state: each solution is a node whose features are its normalized objective values, and edges connect only solutions lying on the same non-dominated front, so the graph carries the hierarchy of Pareto fronts without any hand-crafted convergence or diversity metrics. Two graph convolutional network layers followed by global mean pooling turn the population into one embedding; this embedding is concatenated with the normalized remaining generation budget and passed through a linear layer to produce the means of the continuous action distributions for PPO. The reward is built on the hypervolume indicator: when the current hypervolume beats the best seen so far, the agent receives the difference between the squared percentage improvements over the initial hypervolume, with the ideal hypervolume obtained from a doubled-budget run, so reward values are comparable across instances of different scale.

What would settle it

Retrain the same pipeline on Penta-FJSP with 25 jobs and 5 machines using the same normalized node features but with the graph edges removed, so the state is just the pooled node features plus the budget scalar; if the mean test hypervolume stays near $5.62\times 10^{12}$, the graph structure is not doing the work, whereas a drop toward the SMAC3 or irace level would confirm the graph state as the operative component.

Watch

Extended reading notes

Core claim

On its own terms, GS-MODAC discovers that the evolving population of a multi-objective heuristic can be encoded as a graph—one node per solution holding normalized objective values, edges linking solutions on the same Pareto front (the set of mutually non-dominated solutions)—and that a graph convolutional network embedding of this graph, together with a remaining-budget scalar, is a sufficient state for a PPO agent to set crossover and mutation rates (or particle-swarm coefficients) that beat static configurators and a multi-agent DRL baseline. The reward pays off only when the population's hypervolume improves, and it equals the difference between squared percentage improvements relative to the initial and ideal hypervolumes, which makes the reward scale-free across instances and emphasizes the harder late-stage gains. On the five-objective, 25-job flexible job-shop problem, the trained policy's mean and maximum hypervolumes are 8.2% and 5.7% better than the strongest baselines, and the same policy transfers to larger vehicle-routing instances, an assembly-and-setup-time variant, and objective pairs not seen in training.

Load-bearing premise

The load-bearing premise is that a graph whose nodes are normalized objective values and whose edges only connect solutions that do not dominate each other carries enough information about the search state for the agent to choose good parameter updates; if the missing cross-front and absolute-scale information matters, the claimed generalization collapses.

Editorial extensions

If this is right

  • Practitioners can drop hand-designed state features, because the graph state is constructed directly from normalized objective values and Pareto-front membership.
  • A trained policy transfers to larger instances of the same problem with only a slight performance decline, and still matches or beats the best baselines.
  • A policy trained on one scheduling setting also transfers to a more constrained variant with assembly constraints and sequence-dependent setup times, outperforming static configurators tuned on that variant.
  • The framework is not tied to one base algorithm: it configures both NSGA-II and MOPSO.
  • The added cost is small—state construction and policy inference account for about 2.0% of total runtime on the smallest scheduling instances—so the dynamic control is cheap relative to the search itself.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • A direct ablation the paper does not run would isolate whether the graph edges matter: retrain with the same normalized node features but no edges, or with edges between all pairs of solutions, and compare test hypervolumes on Penta-FJSP.
  • The graph-state idea is not tied to evolutionary computation; any iterative multi-objective method that maintains a set of candidate solutions—local search, simulated annealing, or beam search—could use the same normalized-objective graph as the state for a controller.
  • The reward's dependence on a doubled-budget run to obtain the ideal point suggests a practical extension: replace that fixed reference with an adaptive or learned estimate so the method applies when extra compute is unavailable.
  • If the size-transfer results generalize, a single policy trained on a mixture of small instances could serve as a default parameter controller for an entire problem family, removing the need to retune per instance size.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

3 major / 5 minor

Summary. The paper proposes GS-MODAC, a deep reinforcement learning method for dynamic algorithm configuration of multi-objective evolutionary algorithms. The method represents the current population's solutions in objective space as a graph whose nodes carry normalized objective values and whose edges connect solutions within the same Pareto front; a GCN encodes this graph, and PPO trains a policy that outputs continuous crossover and mutation parameters (or MOPSO coefficients) at each generation. The reward is based on squared hypervolume improvements relative to an initial nadir point and an approximate ideal point. Experiments cover bi-, tri-, and penta-objective FJSP variants and bi-objective CVRP, with comparisons against NSGA-II with default parameters, SMAC3, irace, and MADAC, plus transfer tests to larger instances, more constrained scheduling variants, different objective sets, and a different MOEA.

Significance. If the reported results hold, this is a useful contribution to dynamic algorithm configuration for multi-objective combinatorial optimization. The paper introduces a graph-based state representation that is independent of the number of objectives, an instance-agnostic reward, and demonstrates transfer across problem sizes, objective counts, constrained variants, and to a second MOEA. The code is publicly available, which is a reproducibility strength. The main empirical claims, however, are currently weakened by a baseline tuning protocol that gives SMAC3 and irace access to the test instances, and by the absence of an ablation isolating the contribution of the graph structure itself.

major comments (3)
  1. [Section 4 (Baselines); Table 1] The static baselines SMAC3 and irace are tuned 'using the generated test instances for each given instance size' and then evaluated on those same instances. This is not a standard deployable evaluation protocol: the two static tuners receive test-set information during configuration, so their reported performance is optimistically biased. Since RQ1 and the abstract's 'outperforms' claim rest on Table 1, the headline margins (e.g., Penta-FJSP 25j5m: mean +8.2%, max +5.7% over the best baselines) cannot be taken at face value. The authors should retune SMAC3 and irace on training/validation instances and evaluate on held-out instances, and should report whether the differences persist under that protocol.
  2. [Section 3.1 (States); Appendix E] The graph-based state is the central novelty, but the ablations do not isolate the contribution of the graph structure. Removing the budget feature and reducing the GCN to one layer produce performance changes of roughly 0.8-3.4%, and replacing GCN with Transformer or GAT yields similar results, yet no ablation compares the proposed graph state to an edge-free node embedding, a fully connected graph, or a hand-crafted vector of objective-space statistics. Consequently, the claim that the graph topology rather than the GNN embedding of normalized objective values drives the reported gains is not supported. An ablation that varies the graph construction while keeping the encoder and reward fixed would address this directly.
  3. [Section 4.1; Table 1] The paper marks results as 'significantly outperform[ing]' via a Wilcoxon rank-sum test (p < 0.05) but does not state the unit of the test (per instance, per run, or per instance-mean), whether the test is paired, or whether any multiple-comparison correction is applied across the many entries in Table 1. Several reported improvements are within one standard deviation (e.g., Bi-FJSP 10j5m: 3.92 x 10^4 vs 3.89 x 10^4 with standard deviations around 2 x 10^3). The authors should report the test unit, effect sizes, and correction procedure, or restrict significance claims to comparisons where such a test is clearly defined.
minor comments (5)
  1. [Section 4 (Baselines)] The text refers to 'CVPR' in one place; this should read 'CVRP'.
  2. [Section 4 (Training)] Number formatting is inconsistent (e.g., '1.000,000 steps' and '10.000 runs'); please use uniform separators for readability.
  3. [Figure 2] The figure caption does not state which instance is shown, whether the curves are averaged over runs, or whether error bars or confidence bands are included; please add this information.
  4. [Appendix C, Table 5] The text says GS-MODAC finds a significantly higher number of 'best' solutions, but no significance test is reported for these additional metrics, and the table mixes mean/min/max rows without explaining which quantity is used for each claim.
  5. [Appendix G] The comparison with P-MOCO uses only the best HV value, not mean and standard deviation, and is limited to CVRP; the conclusion about P-MOCO's inferior generalization should be presented as preliminary given this restricted evidence.

Circularity Check

0 steps flagged · score 2.0 of 10

No circular derivation; central claim rests on held-out test instances and external baselines, with only minor non-load-bearing self-citation.

full rationale

GS-MODAC's derivation chain is not circular. The graph state is an encoding of the current population's normalized objective values with edges within Pareto fronts; the GNN and PPO policy are trained on a hypervolume-improvement reward and evaluated on held-out instances, so the reported hypervolumes are not a fit renamed as a prediction. The reward's hypervolume terms are a training signal, not a fitted parameter, and the evaluation instances do not enter GS-MODAC's training. The self-citations (Reijnen et al. 2022; 2023a; 2023b) are used for related work and for the NSGA-II implementation; they are not load-bearing for the core claim, and no uniqueness theorem is imported from the authors' prior work. The main caveat is an experimental-design weakness, not circularity: Section 4 states that SMAC3 and irace are tuned 'using the generated test instances for each given instance size,' and Table 1 then evaluates on those same instances. That gives the static baselines test-set information during configuration, which biases against GS-MODAC and makes the comparison non-standard, but it does not make GS-MODAC's advantage definitional or forced. Ablations (Appendix E) and alternative metrics (Appendix C) provide independent, non-circular evidence for the graph component and the reward design.

Assumptions & free parameters 4 free parameters · 4 assumptions · 0 invented entities

The method introduces no new physical or formal entities; the GNN state is a learned representation, and the reward, state, and action design choices are empirical. The principal commitments are modeling assumptions about the graph state and reward normalization.

free parameters (4)
  • Action ranges for NSGA-II = crossover [0.6, 1.0], mutation [0.0, 0.1]
    Chosen from rules of thumb (Coello et al. 2007), used for all methods; the RL agent's actions map linearly to these ranges.
  • Double-budget multiplier for HV_ideal = 2x budget
    The reward function defines HV_ideal as the hypervolume from a single run of the underlying EA with doubled generations; this factor is chosen ad hoc and affects reward scaling.
  • Population and generation budget = 50 solutions, 50 generations
    Fixed search budget used for all target EAs and baselines; chosen by hand.
  • GNN architecture hidden size = 64 units, 2 GCN layers
    Model capacity choice; ablation only varies number of GCN layers and compares Transformers/GAT, not the hidden size.
assumptions (4)
  • domain assumption The Pareto-front graph constructed from normalized objective values is a sufficient state representation for dynamic configuration
    Section 3.1 States: the entire state is a graph with edges within fronts plus a budget scalar; no cross-front edges or solution structure are included.
  • domain assumption A single run with doubled budget yields a reliable HV_ideal normalization
    Section 3.1 Rewards: HV_ideal is computed once per instance by running the same EA with doubled generations; stochasticity of this run is not accounted for.
  • standard math Hypervolume with a nadir reference point is a faithful measure of solution quality across instances
    Used in Definition 4 and throughout; standard in multi-objective optimization.
  • standard math PPO with fixed hyperparameters from Schulman et al. (2017) is a sufficient RL trainer for this task
    Section 3.2; no tuning of the RL algorithm is reported.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Graph-Supported Dynamic Algorithm Configuration for Multi-Objective Combinatorial Optimization." pith.science (2026). https://pith.science/paper/TBKYEBGP

@misc{pith2026250516471,
  author       = {Pith},
  title        = {Pith review of: Graph-Supported Dynamic Algorithm Configuration for Multi-Objective Combinatorial Optimization},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/TBKYEBGP}},
  note         = {Machine review of arXiv:2505.16471}
}
read the original abstract

Deep reinforcement learning (DRL) has been widely used for dynamic algorithm configuration, particularly in evolutionary computation, which benefits from the adaptive update of parameters during the algorithmic execution. However, applying DRL to algorithm configuration for multi-objective combinatorial optimization (MOCO) problems remains relatively unexplored. This paper presents a novel graph neural network (GNN) based DRL to configure multi-objective evolutionary algorithms. We model the dynamic algorithm configuration as a Markov decision process, representing the convergence of solutions in the objective space by a graph, with their embeddings learned by a GNN to enhance the state representation. Experiments on diverse MOCO challenges indicate that our method outperforms traditional and DRL-based algorithm configuration methods in terms of efficacy and adaptability. It also exhibits advantageous generalizability across objective types and problem sizes, and applicability to different evolutionary computation methods.

Figures

Figures reproduced from arXiv: 2505.16471 by the authors.

Figure 1
Figure 1. The GS-MODAC framework. The framework integrates a DRL agent with a graph-based representation of the [PITH_FULL_IMAGE:figures/full_fig_p004_1.png] view at source ↗
Figure 2
Figure 2. Comparison of GS-MODAC, SMAC3, and NSGA-II solution methods: (a) Average convergence rates and (b) [PITH_FULL_IMAGE:figures/full_fig_p008_2.png] view at source ↗
Figure 3
Figure 3. Chromosome Representation FJSP MOGA (Zhang et al., 2011) 30% using Local Method, and 10% using Random Method. Machine Selection crossovers are in 50% two-point and 50% uniform crossover. To solve the multi-objective FJSP variant using the GA formulation from Zhang et al. (2011), we employ Non-dominated Sorting Genetic Algorithm-II (NSGA-II) for selection (Deb et al., 2002). NSGA-II for CVRP. Subsequently, we apply a… view at source ↗

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

14 extracted references · 11 canonical work pages

  1. [2]

    D., Das, S., and Jalaian, B

    Biswas, S., Saha, D., De, S., Cobb, A. D., Das, S., and Jalaian, B. A. Improving differential evolution through bayesian hyperparameter optimization. In 2021 IEEE Congress on Evolutionary Computation (CEC), pp. 832–

    work page 2021

  2. [4]

    Kipf, T. N. and Welling, M. Semi-supervised classifica- tion with graph convolutional networks. arXiv preprint arXiv:1609.02907,

    arXiv

  3. [10]

    M., Zam- baldi, V ., Jaderberg, M., Lanctot, M., Sonnerat, N., Leibo, J

    Sunehag, P., Lever, G., Gruslys, A., Czarnecki, W. M., Zam- baldi, V ., Jaderberg, M., Lanctot, M., Sonnerat, N., Leibo, J. Z., Tuyls, K., et al. Value-decomposition networks for cooperative multi-agent learning. arXiv preprint arXiv:1706.05296,

    arXiv

  4. [12]

    Machine Selection crossovers are in 50% two-point and 50% uniform crossover

    30% using Local Method, and 10% using Random Method. Machine Selection crossovers are in 50% two-point and 50% uniform crossover. To solve the multi-objective FJSP variant using the GA formulation from Zhang et al. (2011), we employ Non-dominated Sorting Genetic Algorithm-II (NSGA-II) for selection (Deb et al., 2002). NSGA-II for CVRP.Subsequently, we app...

    work page 2011

  5. [14]

    The results, presented in Table 10, compare the best obtained HV values, aligned with the experimental setup of Lin et al

    We evaluate its performance based on the setup described in Section 4, utilizing the same instances and reference points recorded in the publication. The results, presented in Table 10, compare the best obtained HV values, aligned with the experimental setup of Lin et al. (2022). Table 10: Comparison of Hypervolume (HV) values achieved by NSGA-II, and by ...

    work page 2022

  6. [100]

    Table 6: Performance comparison of the proposed method for dynamic algorithm configuration of Multi-Objective Particle Swarm Optimization (MOPSO) Algorithm. Bi-CVRP - 20 Bi-CVRP - 50 Bi-CVRP - 100 Method mean max std mean max std mean max std MOPSO 3.21×101 3.75×101 3.47 5.82×101 6.90×101 5.65 8.67×101 9.75×101 5.87 GS-MODAC 3.28×101 3.77×101 3.20 6.27×10...

    work page 2022

  7. [1998]

    11 Graph-Supported Dynamic Algorithm Configuration for Multi-Objective Combinatorial Optimization A. Test problem configurations The Flexible Job Shop Scheduling Problem (FJSP) is a popular scheduling problem where multiple jobs, each composed of several operations that must be completed in a specific order, must be scheduled to a set of machines. The pro...

    work page 2011

  8. [2007]

    Coello, C. C. and Lechuga, M. S. Mopso: A proposal for multiple objective particle swarm optimization. In Proceedings of the 2002 Congress on Evolutionary Com- putation. CEC’02 (Cat. No. 02TH8600) , volume 2, pp. 1051–1056. IEEE,

    work page 2002

Show all 14 references
  1. [2011]

    Pareto set learning for neural multi-objective combinatorial optimization

    Lin, X., Yang, Z., and Zhang, Q. Pareto set learning for neural multi-objective combinatorial optimization. arXiv preprint arXiv:2203.15386,

    arXiv

  2. [2014]

    F., Eimer, T., Hutter, F., and Lindauer, M

    Biedenkapp, A., Bozkurt, H. F., Eimer, T., Hutter, F., and Lindauer, M. Dynamic algorithm configuration: Foun- dation of a new meta-algorithmic framework. In ECAI 2020, pp. 427–434. IOS Press,

    2020

  3. [2016]

    Ma, Z., Guo, H., Gong, Y .-J., Zhang, J., and Tan, K. C. To- ward automated algorithm design: A survey and practical guide to meta-black-box-optimization. arXiv preprint arXiv:2411.00625,

    arXiv

  4. [2017]

    Learning step-size adaptation in cma-es

    Shala, G., Biedenkapp, A., Awad, N., Adriaensen, S., Lin- dauer, M., and Hutter, F. Learning step-size adaptation in cma-es. In Parallel Problem Solving from Nature–PPSN XVI: 16th International Conference, PPSN 2020, Leiden, The Netherlands, September 5-9, 2020, Proceedings, P...

    2020

  5. [2021]

    Deep reinforcement learning for adaptive parameter control in differential evolution for multi-objective optimization

    Reijnen, R., Zhang, Y ., Bukhsh, Z., and Guzek, M. Deep reinforcement learning for adaptive parameter control in differential evolution for multi-objective optimization. In 2022 IEEE Symposium Series on Computational Intelli- gence (SSCI), pp. 804–811. IEEE,

    2022

  6. [2022]

    Job shop scheduling benchmark: Environments and instances for learning and non-learning methods

    Reijnen, R., van Straaten, K., Bukhsh, Z., and Zhang, Y . Job shop scheduling benchmark: Environments and instances for learning and non-learning methods. arXiv preprint arXiv:2308.12794, 2023a. Reijnen, R., Zhang, Y ., Bukhsh, Z., and Guzek, M. Learn- ing to adapt genetic alg...

    arXiv

Pith tools

Reviewed August 7, 2026 · model on record in the stance chip above.