🧩 Constraint Solving POTD:Problem of the Day: Constraint Programming and Large Language Models — Learning Solver Strategies

[github-actions[bot]]

Problem Statement

The Challenge: Given a combinatorial optimization problem instance (e.g., TSP, graph coloring, scheduling), train a machine-learning model to predict which solver strategies (variable-ordering heuristics, propagation techniques, search restarts) will solve it efficiently.

Concrete Instance:
Imagine you have 100 instances of the job-shop scheduling problem with varying numbers of jobs and machines. For each instance, you have:

• Instance features: number of jobs n, number of machines m, average processing time, variance of operation durations
• Solver strategies to choose: depth-first search (DFS), restarts (Luby, geometric), variable-ordering heuristics (first-unbound, minimum-remaining-values, impact-based)
• Outcomes: solution time, memory usage, proof of optimality

Goal: Train a model to predict which strategy (or ensemble of strategies) will minimize solve time for a new, unseen instance.

Input/Output:

• Input: Instance features {n, m, density, time_variance, ...} + strategy identifier
• Output: Predicted solve time; actual categorization: "fast" (< 1s), "medium" (1–10s), "hard" (> 10s)

Why It Matters

Algorithm selection and portfolio approaches:
In competitive optimization, no single algorithm beats all others on every instance. Practitioners use algorithm selection (ASLIB framework) or per-instance solver portfolios to route each problem to its best-suited solver strategy. CP systems like Gurobi, CPLEX, and Choco now integrate ML-guided heuristics to accelerate search.

Practical impact:

• Cloud solvers: Route customer optimization jobs to the best strategy automatically
• AutoML for optimization: Users provide constraints and data; the system selects the solver and strategy
• Hybrid CP/ML workflows: Neural networks predict heuristic parameters on-the-fly during branch-and-bound

Modeling Approaches

1. Supervised Classification (ML-native approach)

Paradigm: Feature extraction + classifier (random forest, gradient boosting, neural networks)

Decision variables: None in the CP sense; the model directly predicts from features to a strategy label.

Process:

1. Extract instance features (size, density, structure)
2. For each strategy, measure solve time on the instance
3. Label instance: y = argmin_s(time_s) (best strategy)
4. Train classifier f: features → strategy

Trade-offs:

• ✅ Scalable, uses standard ML pipelines, easy to integrate
• ❌ Ignores constraint structure; treats the instance as a black box
• ❌ Doesn't leverage CP-specific domain knowledge

2. Constraint-based Strategy Selection (Hybrid approach)

Paradigm: CP or SAT encoding that selects the best strategy subject to performance guarantees

Decision variables:

• select_s ∈ {0, 1} for each strategy s (which strategy(ies) to use)
• time_s ∈ R+ (predicted solve time for strategy s, computed by ML model)
• cost ∈ R+ (total cost: time + memory + overhead)

Constraints:

Σ_s select_s = 1  (pick exactly one strategy)
cost = Σ_s select_s · time_s  (compute total cost)
cost ≤ deadline  (optional: enforce deadline)

Post-processing: For each candidate strategy, run an ML regression to predict solve time; CP picks the strategy that minimizes cost.

Trade-offs:

• ✅ Allows hard constraints (e.g., memory limits, time budgets)
• ✅ Can combine multiple strategies (portfolio)
• ❌ Adds overhead; predictions must be fast
• ❌ Coupling CP solver and ML model adds complexity

3. Reinforcement Learning with Reward Shaping (Learning approach)

Paradigm: RL agent learns a policy π: (state, features) → action (strategy/heuristic)

State representation: Current search tree size, remaining unbound variables, constraint propagation strength, etc.

Actions: Switch solver strategy, adjust restart frequency, change variable ordering

Reward: r(t) = -solve_time - λ·memory - λ'·overhead

Trade-offs:

• ✅ Adaptive: learns from solving each instance
• ✅ Can discover novel strategies not in the predefined set
• ❌ High sample complexity; training takes many solver runs
• ❌ Difficult to guarantee safety or interpretability

Example: Supervised Classification with Features

import pandas as pd
from sklearn.ensemble import RandomForestClassifier

# Instance features (extracted from problem structure)
features = pd.DataFrame({
    'n_jobs': [10, 15, 20],
    'n_machines': [5, 5, 10],
    'density': [0.8, 0.9, 0.7],
    'time_variance': [2.5, 1.8, 3.2],
    'critical_path_ratio': [0.6, 0.55, 0.65]
})

# Labels: best strategy for each instance
# (discovered by running all strategies and recording the fastest)
labels = ['DFS', 'Restart-Luby', 'DFS']

# Train classifier
clf = RandomForestClassifier(n_estimators=100)
clf.fit(features, labels)

# Predict strategy for a new instance
new_instance = [[12, 6, 0.75, 2.2, 0.58]]
predicted_strategy = clf.predict(new_instance)  # e.g., 'Restart-Luby'
confidence = clf.predict_proba(new_instance).max()
print(f"Use strategy: {predicted_strategy} (confidence: {confidence:.2%})")

Key Techniques

1. Footprint Features & Problem Structure Extraction

Feature engineering matters: static features (problem size, density) + dynamic features (constraint propagation speed, search tree profile) improve predictions. The Algorithm Selection for Combinatorial Optimization (ASLIB) framework standardizes this process.

2. Model Ensembles and Warm-Starting

Rather than picking one strategy, solver portfolios (e.g., SAT-RACE, ASlib) run multiple solvers in parallel with different strategies and return the first successful result. ML can predict which subset of strategies is most likely to succeed, reducing overhead.

3. Ranking and Regression Over Classification

Instead of predicting "which is best," use regression to predict solve time for each strategy independently, then select the minimum. This captures uncertainty and allows tie-breaking by secondary criteria (e.g., memory usage).

4. Active Learning and Curriculum Training

Don't train uniformly on all instances. Active learning identifies uncertain instances where the model is confused (e.g., multiple strategies have similar predicted times) and acquires labels for those instances first, prioritizing learning where it matters.

Challenge Corner

Q1: Transfer Learning Across Problem Classes
A model trained on TSP instances may struggle with graph-coloring problems due to different structure. How would you design a feature representation that generalizes across problem families? What meta-features capture solvability across diverse constraint types?

Q2: Explainability Under Time Pressure
In practice, users want to know why a strategy was selected (especially if it fails). How would you design an interpretable model or extract decision rules that explain strategy selection in human-readable terms? Can you use SHAP values or rule-based learning to approximate an opaque neural network predictor?

Q3: Fairness in Strategy Selection
If you train your model on instances from one domain (e.g., industrial scheduling), it may overfit to that domain's characteristics. How would you detect and mitigate domain bias? Should you explicitly regularize for robustness across unseen problem structures?

References

1. Leite et al. (2012) — "Algorithm Selection for Combinatorial Search Problems: A Survey" (Data Mining and Knowledge Discovery). Foundational paper on algorithm selection; defines feature extraction and meta-learning.

2. Xu et al. (2008) — "SATzilla: Portfolio-based Algorithm Selection for SAT" (JAIR). Classic SAT solver portfolio that uses ML to predict solver performance; pioneered per-instance algorithm selection.

3. Bengio et al. (2021) — "Machine Learning for Combinatorial Optimization: A Methodological Survey" (EJOR). Modern survey covering supervised learning, RL, and hybrid CP/ML approaches for optimization.

4. Hutter & Leite (2017) — "Learning Curve Prediction with Bayesian Neural Networks" (ICML). Techniques for predicting solution quality and solve time curves; useful for strategy selection under partial information.

5. AutoML/Hyperband Literature — Successive halving and bandit-based algorithm selection (Li et al., 2018) provide efficient portfolio management when you have limited budget for strategy exploration.

Generated by 🧩 Constraint Solving — Problem of the Day · copilot · haiku45 · ~7 AIC · ⌖ ~10 AIC · ⊞ 7.3K · ◷

• expires on Nov 10, 2026, 3:31 AM UTC-08:00

[github-actions[bot]]

This discussion has been marked as outdated by Constraint Solving — Problem of the Day.

A newer discussion is available at Discussion #74638.