Synthesizing Feature Extractors: An Agentic Approach for Algorithm Selection

Algorithm selection (AS) for combinatorial problems relies on mapping problem instances to the most effective solver from a portfolio based on extracted structural features. Traditionally, designing these feature extractors demands substantial domain expertise, as seen in expert-curated tools like mzn2feat, creating a major bottleneck when new problem classes emerge. Conversely, recent deep learning approaches learn opaque neural embeddings that sacrifice interpretability for automation. This paper introduces an automated framework using Large Language Models to synthesize executable, problem-specific, and inspectable Python feature extractors directly from high-level declarative MiniZinc problem descriptions.

The core methodology employs an LLM agent operating within an automated check-fix-verify error-correcting loop. Given a MiniZinc model and data instance schemas, the agent follows a strict script-generation protocol to produce a Python script that builds a typed graph representation of the instance and computes structured properties such as graph density, variable clustering, and constraint tightness. The pipeline enforces a standardized output of exactly fifty features. Every step of the agentic loop is load-bearing; pilot ablations showed that removing validation or error-fixing steps causes synthesis success rates to collapse.

The authors evaluate the synthesized feature extractors across three combinatorial problem domains (vehicle routing, car sequencing, and fixed-length error-correcting codes) using a portfolio of five state-of-the-art solvers. Compared to traditional expert-curated features and transformer-based alternatives, the LLM-synthesized features achieve lower feature correlation, higher utilization efficiency across machine learning models, and superior algorithm selection accuracy (outperforming mzn2feat by up to 8.3 percentage points on test sets).