App-28 — Learning to branch

Auditer la généralisation avant d’annoncer un gain

← Applications | ↑ Search | << App-25 Enchères WDP/VCG

Durée estimée : 75 minutes

Hommage et question scientifique

Le groupe G4 — Simon Naulet et Matis Codjia a relié deux mondes difficiles à faire dialoguer : la programmation par contraintes et l’apprentissage supervisé. Leur projet construit un mini-solveur CSP, implémente AC-3, extrait des features à chaque nœud et entraîne XGBoost à imiter dom/wdeg. Ce passage d’une heuristique écrite à une politique apprise est le geste central conservé ici. Source : PR PrCon #46, fusion 9f91222f.

Une accuracy élevée sur des lignes candidates ne suffit pourtant pas à conclure qu’un solveur est meilleur. Une politique de branchement agit dans une boucle : son choix modifie la propagation, donc les domaines, donc les nœuds futurs qu’elle devra elle-même traiter. Elle peut bien imiter l’oracle localement tout en construisant un arbre plus grand ; elle peut réduire les nœuds tout en perdre en temps si l’inférence coûte plus cher que la décision classique.

La reproduction CoursIA ne copie aucune cellule, fonction, donnée, figure ou prose étudiante. Elle reconstruit indépendamment le dispositif avec HistGradientBoostingClassifier et pose une question plus stricte : la politique apprise généralise-t-elle à de nouvelles instances et à une famille CSP entièrement absente du train, une fois son coût d’inférence compté ?

Quatre niveaux à ne pas confondre

Imitation locale — le candidat classé premier est-il celui choisi par l’oracle ?
Trajectoire de recherche — la politique ouvre-t-elle moins de nœuds ?
Coût d’exécution — le gain éventuel amortit-il le scoring à chaque nœud ?
Transfert — le comportement survit-il quand une famille entière manque au train ?

Objectifs d’apprentissage

À la fin du parcours, vous saurez construire un split groupé par instance, dériver les features locales et dom/wdeg, choisir une baseline sans regarder le test, intégrer une politique apprise dans le solveur, mesurer nœuds/temps/inférence, valider chaque solution et interpréter un résultat négatif sans le diluer.

Prérequis

CSP-6 Hybridation
MGS-16 Sélection d’algorithmes
Python 3.10+ ; numpy, pandas, scikit-learn, matplotlib

1. Pourquoi le split naïf est trompeur

À un nœud de recherche \(n\), chaque variable candidate \(x\in C_n\) produit une ligne de features et un label binaire indiquant si dom/wdeg l’a choisie. Un split aléatoire de ces lignes peut placer un candidat du même nœud dans le train et un autre dans le test. Même si les nœuds sont séparés, deux nœuds issus du même CSP partagent sa taille, sa densité, ses domaines initiaux et sa structure de contraintes.

Cette dépendance viole l’unité d’échantillonnage réelle. Le solveur sera déployé sur une nouvelle instance, pas sur une nouvelle ligne d’une instance déjà vue. Le groupe de split doit donc être instance_id, et non candidate ou node_id seulement.

L’accuracy binaire est elle aussi trompeuse : un nœud avec dix candidats contient neuf labels zéro. Prédire toujours zéro atteint 90 % sans sélectionner de variable. La métrique locale pertinente est le top-1 par nœud :

\[\operatorname{top1}=\frac{1}{|N|}\sum_{n\in N}\mathbf 1\!\left[\arg\max_{x\in C_n}s(x)=x_n^*\right].\]

Mais cette fidélité à l’oracle reste intermédiaire. Nous l’accompagnons de la taille de l’arbre, du temps mur, de la part d’inférence et de la validité de l’affectation finale.

Le protocole utilise d’abord un split groupé de 24 instances train / 12 test, puis trois évaluations leave-one-family-out : reines, coloration et carrés latins sont successivement absents du train. Cette seconde échelle teste un changement de distribution plus sévère que le simple renouvellement d’instances.

from __future__ import annotations

import json
import math
import random
import time
from collections import deque
from dataclasses import dataclass, field
from pathlib import Path
from typing import Callable

import numpy as np
import pandas as pd
from sklearn.ensemble import HistGradientBoostingClassifier


print('Imports chargés : numpy, pandas et scikit-learn')

Imports chargés : numpy, pandas et scikit-learn

2. Exemple guide — un solveur et un validateur indépendants

Le noyau expérimental utilise des domaines finis, des contraintes binaires, AC-3 et un backtracking chronologique. À chaque affectation tentée, AC-3 révise les arcs voisins jusqu’au point fixe ou jusqu’à vider un domaine. La politique de branchement ne choisit que la variable ; les valeurs restent essayées dans l’ordre croissant afin de ne pas confondre deux décisions.

Cette séparation permet une comparaison contrôlée entre quatre baselines et une politique apprise. Le compteur nodes augmente à chaque appel de recherche, avant le choix de variable. inference_seconds mesure uniquement le temps passé dans la fonction apprise ; le temps total inclut aussi propagation, copie des domaines et récursion.

Le validateur final ne fait confiance ni au statut, ni au nombre de nœuds, ni au chemin de recherche. À partir de l’affectation seule, il vérifie :

qu’une valeur est fournie pour chaque variable et seulement pour elles ;
que chaque valeur appartient au domaine initial ;
que chaque relation binaire est satisfaite dans les deux orientations enregistrées.

Une solution rapide mais incomplète n’est donc pas comptée comme un gain. Ce contrat est essentiel lorsqu’on compare des politiques susceptibles de modifier profondément la trajectoire ou d’atteindre la limite de nœuds.


Relation = Callable[[int, int], bool]
FEATURES = [
    "domain_size",
    "domain_ratio",
    "degree",
    "degree_ratio",
    "weighted_degree",
    "activity",
    "dom_wdeg",
    "progress",
    "neighbor_domain_min",
    "neighbor_domain_mean",
    "neighbor_domain_max",
]
BASELINES = ("mrv", "max_degree", "dom_wdeg", "activity")


@dataclass
class CSP:
    family: str
    instance_id: str
    domains: dict[str, set[int]] = field(default_factory=dict)
    neighbors: dict[str, set[str]] = field(default_factory=dict)
    relations: dict[tuple[str, str], list[Relation]] = field(default_factory=dict)

    @property
    def variables(self) -> list[str]:
        return list(self.domains)

    def add_variable(self, name: str, domain: range | list[int] | set[int]) -> None:
        self.domains[name] = set(domain)
        self.neighbors[name] = set()

    def add_constraint(self, left: str, right: str, relation: Relation) -> None:
        self.neighbors[left].add(right)
        self.neighbors[right].add(left)
        self.relations.setdefault((left, right), []).append(relation)
        self.relations.setdefault((right, left), []).append(lambda b, a, rel=relation: rel(a, b))

    def add_all_different(self, variables: list[str]) -> None:
        for i, left in enumerate(variables):
            for right in variables[i + 1 :]:
                self.add_constraint(left, right, lambda a, b: a != b)


def revise(csp: CSP, domains: dict[str, set[int]], left: str, right: str) -> bool:
    relations = csp.relations.get((left, right), [])
    remove = {
        value
        for value in domains[left]
        if not any(all(rel(value, other) for rel in relations) for other in domains[right])
    }
    if remove:
        domains[left] -= remove
        return True
    return False


def ac3(
    csp: CSP,
    domains: dict[str, set[int]],
    arcs: list[tuple[str, str]] | None = None,
) -> tuple[bool, set[str]]:
    queue = deque(arcs if arcs is not None else csp.relations)
    changed: set[str] = set()
    while queue:
        left, right = queue.popleft()
        if revise(csp, domains, left, right):
            changed.add(left)
            if not domains[left]:
                return False, changed
            queue.extend((neighbor, left) for neighbor in csp.neighbors[left] if neighbor != right)
    return True, changed


def features_for(
    csp: CSP,
    domains: dict[str, set[int]],
    assignment: dict[str, int],
    weights: dict[tuple[str, str], int],
    activity: dict[str, int],
    variable: str,
) -> dict[str, float]:
    remaining = [neighbor for neighbor in csp.neighbors[variable] if neighbor not in assignment]
    weighted_degree = sum(weights.get(tuple(sorted((variable, neighbor))), 1) for neighbor in remaining)
    neighbor_sizes = [len(domains[neighbor]) for neighbor in remaining]
    n_variables = len(csp.variables)
    initial_size = len(csp.domains[variable])
    return {
        "domain_size": float(len(domains[variable])),
        "domain_ratio": len(domains[variable]) / max(initial_size, 1),
        "degree": float(len(remaining)),
        "degree_ratio": len(remaining) / max(n_variables - 1, 1),
        "weighted_degree": float(weighted_degree),
        "activity": float(activity.get(variable, 0)),
        "dom_wdeg": len(domains[variable]) / max(weighted_degree, 1),
        "progress": len(assignment) / max(n_variables, 1),
        "neighbor_domain_min": float(min(neighbor_sizes, default=0)),
        "neighbor_domain_mean": float(np.mean(neighbor_sizes) if neighbor_sizes else 0),
        "neighbor_domain_max": float(max(neighbor_sizes, default=0)),
    }


class Solver:
    def __init__(
        self,
        csp: CSP,
        heuristic: str | Callable[..., str],
        collect_trace: bool = False,
        node_limit: int = 20_000,
    ) -> None:
        self.csp = csp
        self.heuristic = heuristic
        self.collect_trace = collect_trace
        self.node_limit = node_limit
        self.nodes = 0
        self.inference_seconds = 0.0
        self.trace: list[dict[str, object]] = []
        self.weights: dict[tuple[str, str], int] = {}
        self.activity: dict[str, int] = {}

    def select(self, domains: dict[str, set[int]], assignment: dict[str, int]) -> str:
        candidates = [variable for variable in self.csp.variables if variable not in assignment]
        rows = [features_for(self.csp, domains, assignment, self.weights, self.activity, var) for var in candidates]
        if callable(self.heuristic):
            started = time.perf_counter()
            chosen = self.heuristic(candidates, rows)
            self.inference_seconds += time.perf_counter() - started
        elif self.heuristic == "mrv":
            chosen = min(candidates, key=lambda var: (len(domains[var]), var))
        elif self.heuristic == "max_degree":
            chosen = min(
                candidates,
                key=lambda var: (-sum(n not in assignment for n in self.csp.neighbors[var]), var),
            )
        elif self.heuristic == "dom_wdeg":
            chosen = min(
                candidates,
                key=lambda var: (
                    features_for(self.csp, domains, assignment, self.weights, self.activity, var)["dom_wdeg"],
                    var,
                ),
            )
        elif self.heuristic == "activity":
            chosen = min(candidates, key=lambda var: (-self.activity.get(var, 0), var))
        else:
            raise ValueError(f"Unknown heuristic: {self.heuristic}")

        if self.collect_trace and len(candidates) > 1:
            node_id = f"{self.csp.instance_id}:{self.nodes}"
            for candidate, row in zip(candidates, rows):
                self.trace.append(
                    {
                        "family": self.csp.family,
                        "instance_id": self.csp.instance_id,
                        "node_id": node_id,
                        "candidate": candidate,
                        **row,
                        "label": int(candidate == chosen),
                    }
                )
        return chosen

    def solve(self) -> dict[str, int] | None:
        domains = {variable: set(values) for variable, values in self.csp.domains.items()}
        consistent, _ = ac3(self.csp, domains)
        if not consistent:
            return None
        return self._search({}, domains)

    def _search(self, assignment: dict[str, int], domains: dict[str, set[int]]) -> dict[str, int] | None:
        if len(assignment) == len(self.csp.variables):
            return dict(assignment)
        if self.nodes >= self.node_limit:
            return None
        self.nodes += 1
        variable = self.select(domains, assignment)
        for value in sorted(domains[variable]):
            next_domains = {name: set(values) for name, values in domains.items()}
            next_assignment = dict(assignment)
            next_assignment[variable] = value
            next_domains[variable] = {value}
            consistent, changed = ac3(
                self.csp,
                next_domains,
                [(neighbor, variable) for neighbor in self.csp.neighbors[variable]],
            )
            for changed_variable in changed:
                self.activity[changed_variable] = self.activity.get(changed_variable, 0) + 1
            if consistent:
                result = self._search(next_assignment, next_domains)
                if result is not None:
                    return result
            for neighbor in self.csp.neighbors[variable]:
                key = tuple(sorted((variable, neighbor)))
                self.weights[key] = self.weights.get(key, 1) + 1
        return None



print('Noyau CSP prêt : propagation AC-3, recherche et validation indépendante')

Noyau CSP prêt : propagation AC-3, recherche et validation indépendante

Le noyau sépare décision, propagation et preuve de validité

La cellule définit un solveur réellement exécuté, pas un replay de métriques. select construit les features au nœud courant ; _search applique le choix, propage puis revient en arrière ; validate_solution sera appelé après la résolution. Une politique apprise doit donc subir ses propres conséquences : un mauvais choix crée les nœuds futurs sur lesquels elle sera ensuite évaluée.

FEASIBLE n’est pas un statut d’optimalité ici, car le problème cherche seulement une première solution. Il signifie « affectation complète passée au validateur ». Les comparaisons portent sur les ressources dépensées pour atteindre cette solution, sous la même limite de 20 000 nœuds.

3. Instances déterministes et distinctes

Les 36 CSP sont générés sans réseau : douze tailles de N-reines, douze colorations plantées et douze carrés latins partiellement révélés. Chaque famille impose une géométrie différente à la recherche : contraintes diagonales denses pour les reines, graphe irrégulier pour la coloration, cliques de lignes et colonnes pour les carrés latins.

Chaque instance_id identifie une unité indivisible du split. Les graines de génération sont déterministes, mais cette reproductibilité ne transforme pas 36 problèmes en population représentative des CSP industriels. Le banc sert à éprouver le protocole et le transfert, pas à annoncer une supériorité universelle.


def make_queens(index: int) -> CSP:
    n = 8 + index
    csp = CSP("queens", f"queens-{n}")
    for row in range(n):
        csp.add_variable(f"q{row}", range(n))
    for left in range(n):
        for right in range(left + 1, n):
            distance = right - left
            csp.add_constraint(
                f"q{left}",
                f"q{right}",
                lambda a, b, d=distance: a != b and abs(a - b) != d,
            )
    return csp


def make_coloring(index: int) -> CSP:
    seed = 10_000 + index
    rng = random.Random(seed)
    n = 16 + index
    colors = 3 + index % 2
    planted = [rng.randrange(colors) for _ in range(n)]
    density = 0.28 + 0.02 * (index % 5)
    edges = [
        (left, right)
        for left in range(n)
        for right in range(left + 1, n)
        if planted[left] != planted[right] and rng.random() < density
    ]
    csp = CSP("coloring", f"coloring-{index:02d}")
    for node in range(n):
        csp.add_variable(f"v{node}", range(colors))
    for left, right in edges:
        csp.add_constraint(f"v{left}", f"v{right}", lambda a, b: a != b)
    return csp


def make_latin(index: int) -> CSP:
    seed = 20_000 + index
    rng = random.Random(seed)
    n = 4 + index % 4
    row_perm = list(range(n))
    col_perm = list(range(n))
    value_perm = list(range(n))
    rng.shuffle(row_perm)
    rng.shuffle(col_perm)
    rng.shuffle(value_perm)
    solution = {
        (row, col): value_perm[(row_perm[row] + col_perm[col]) % n]
        for row in range(n)
        for col in range(n)
    }
    reveal_rate = 0.18 + 0.03 * (index % 4)
    csp = CSP("latin", f"latin-{index:02d}")
    for row in range(n):
        for col in range(n):
            domain = [solution[(row, col)]] if rng.random() < reveal_rate else list(range(n))
            csp.add_variable(f"x{row}_{col}", domain)
    for row in range(n):
        csp.add_all_different([f"x{row}_{col}" for col in range(n)])
    for col in range(n):
        csp.add_all_different([f"x{row}_{col}" for row in range(n)])
    return csp


def build_instances(count_per_family: int = 12) -> list[CSP]:
    makers = (make_queens, make_coloring, make_latin)
    return [maker(index) for maker in makers for index in range(count_per_family)]


def validate_solution(csp: CSP, solution: dict[str, int] | None) -> bool:
    if solution is None or set(solution) != set(csp.variables):
        return False
    if any(solution[var] not in csp.domains[var] for var in csp.variables):
        return False
    return all(
        all(relation(solution[left], solution[right]) for relation in relations)
        for (left, right), relations in csp.relations.items()
    )


def run_solver(csp: CSP, heuristic: str | Callable[..., str], collect_trace: bool = False) -> tuple[dict, list[dict]]:
    solver = Solver(csp, heuristic, collect_trace=collect_trace)
    started = time.perf_counter()
    solution = solver.solve()
    elapsed = time.perf_counter() - started
    result = {
        "family": csp.family,
        "instance_id": csp.instance_id,
        "heuristic": heuristic if isinstance(heuristic, str) else "learned_policy",
        "solved": solution is not None,
        "valid": validate_solution(csp, solution),
        "nodes": solver.nodes,
        "seconds": elapsed,
        "inference_seconds": solver.inference_seconds,
    }
    return result, solver.trace



print('Générateurs déterministes prêts : reines, coloration plantée et carrés latins')

Générateurs déterministes prêts : reines, coloration plantée et carrés latins

Trois familles contrôlées, trois formes de décalage

Les N-reines font croître la taille de 8 à 19 variables avec des contraintes de colonne et de diagonale entre chaque paire. Les colorations utilisent 16 à 27 sommets, trois ou quatre couleurs et une densité variable, tout en conservant une coloration plantée. Les carrés latins alternent des ordres 4 à 7 et des taux de révélation différents.

Le générateur garantit la rejouabilité et l’existence d’une solution pour coloration/latin ; il ne garantit pas que toutes les instances aient la même difficulté. C’est pourquoi la baseline est comparée instance par instance avant agrégation, et pourquoi médiane et moyenne géométrique des ratios répondent à des questions complémentaires.

4. Dériver `dom/wdeg` et les features locales

Pour une variable non affectée \(x\), le degré pondéré courant additionne les poids des contraintes qui la relient à d’autres variables non affectées :

\[wdeg(x)=\sum_{y\in N(x),\,y\notin A}w_{xy}.\]

La règle dom/wdeg choisit le plus petit ratio

\[\frac{|D(x)|}{\max(wdeg(x),1)}.\]

Elle favorise une variable au petit domaine impliquée dans des contraintes qui ont déjà contribué à des échecs. Après une branche infructueuse, le prototype incrémente les poids des arêtes incidentes ; activity compte séparément les variables dont le domaine a été révisé par AC-3.

Les onze features décrivent quatre dimensions : taille relative du domaine, degré résiduel, mémoire des conflits (weighted_degree, activity, dom_wdeg) et état du voisinage. progress situe le nœud dans l’arbre. Elles sont locales : elles ne voient ni coût contrefactuel du choix, ni taille de sous-arbre future, ni identité brute de l’instance.

La cible reste l’imitation pointwise de dom/wdeg, mais l’évaluation est structurée par nœud. HistGradientBoostingClassifier évite une dépendance XGBoost supplémentaire. Pour chaque split, la baseline déployable est choisie par médiane des nœuds sur le train seulement parmi MRV, max-degree, dom/wdeg et activity.


def train_policy(
    trace: pd.DataFrame,
    instance_ids: set[str],
    random_state: int,
) -> HistGradientBoostingClassifier:
    rows = trace[trace["instance_id"].isin(instance_ids)]
    model = HistGradientBoostingClassifier(
        learning_rate=0.08,
        max_iter=160,
        max_leaf_nodes=31,
        min_samples_leaf=20,
        l2_regularization=0.1,
        random_state=random_state,
    )
    model.fit(rows[FEATURES], rows["label"])
    return model


def learned_heuristic(model: HistGradientBoostingClassifier) -> Callable[..., str]:
    def choose(candidates: list[str], rows: list[dict[str, float]]) -> str:
        frame = pd.DataFrame(rows, columns=FEATURES)
        scores = model.predict_proba(frame)[:, 1]
        best = max(range(len(candidates)), key=lambda index: (scores[index], -index))
        return candidates[best]

    return choose


def top1_accuracy(model: HistGradientBoostingClassifier, trace: pd.DataFrame, instance_ids: set[str]) -> float:
    rows = trace[trace["instance_id"].isin(instance_ids)].copy()
    rows["score"] = model.predict_proba(rows[FEATURES])[:, 1]
    predicted = rows.loc[rows.groupby("node_id")["score"].idxmax(), ["node_id", "label"]]
    return float(predicted["label"].mean())


def choose_train_baseline(baselines: pd.DataFrame, train_ids: set[str]) -> str:
    train = baselines[baselines["instance_id"].isin(train_ids)]
    medians = train.groupby("heuristic")["nodes"].median().sort_values(kind="stable")
    return str(medians.index[0])


def summarize_evaluation(frame: pd.DataFrame, split_name: str, baseline: str) -> dict:
    learned = frame[frame["heuristic"] == "learned_policy"].set_index("instance_id")
    selected = frame[frame["heuristic"] == baseline].set_index("instance_id")
    merged = learned.join(selected, lsuffix="_ml", rsuffix="_baseline")
    node_ratio = merged["nodes_ml"] / merged["nodes_baseline"].clip(lower=1)
    time_ratio = merged["seconds_ml"] / merged["seconds_baseline"].clip(lower=1e-9)
    strict_node_wins = int((merged["nodes_ml"] < merged["nodes_baseline"]).sum())
    strict_time_wins = int((merged["seconds_ml"] < merged["seconds_baseline"]).sum())
    return {
        "split": split_name,
        "selected_baseline": baseline,
        "instances": len(merged),
        "all_solved": bool(merged["solved_ml"].all() and merged["solved_baseline"].all()),
        "median_node_ratio": float(node_ratio.median()),
        "geomean_node_ratio": float(math.exp(np.log(node_ratio).mean())),
        "median_time_ratio": float(time_ratio.median()),
        "strict_node_wins": strict_node_wins,
        "strict_time_wins": strict_time_wins,
        "median_inference_share": float((merged["inference_seconds_ml"] / merged["seconds_ml"]).median()),
    }



print('Politique apprise et métriques de comparaison prêtes')

Politique apprise et métriques de comparaison prêtes

Imiter un oracle heuristique ne crée pas une oracle contrefactuelle

Le classifieur apprend la décision prise par dom/wdeg, pas la variable qui minimiserait réellement le sous-arbre. Même une imitation top-1 parfaite reproduirait donc les qualités et limites de son professeur. Une imitation imparfaite peut parfois gagner par hasard en s’écartant de l’oracle ; ce cas doit être mesuré dans le solveur plutôt qu’interprété comme une amélioration apprise.

choose_train_baseline évite une autre fuite : la baseline de comparaison est sélectionnée sur les seules instances train. La choisir après lecture du test donnerait au comparateur classique un avantage rétrospectif et rendrait le duel aussi contaminé que le modèle.

5. Protocole complet — du candidat à la trajectoire

Chaque split est répété avec cinq graines du modèle. Les mêmes CSP held-out sont présentés à la politique apprise et à la baseline sélectionnée. Pour chaque paire, le protocole conserve :

validation et résolution complète ;
ratio de nœuds \(n_{ML}/n_{base}\) ;
ratio de temps \(t_{ML}/t_{base}\) ;
victoires strictes en nœuds et en temps ;
part \(t_{inference}/t_{ML}\) ;
top-1 par nœud sur les traces held-out de l’oracle.

La moyenne géométrique des ratios limite l’effet d’échelle entre instances, tandis que la médiane décrit une instance centrale. Une victoire stricte exige <, pas ≤ : égaler MRV en nœuds tout en ajoutant de l’inférence n’est pas une victoire opérationnelle.


def main(output_dir: Path) -> None:
    output_dir.mkdir(parents=True, exist_ok=True)
    instances = build_instances()

    baseline_rows: list[dict] = []
    trace_rows: list[dict] = []
    for index, csp in enumerate(instances, start=1):
        for heuristic in BASELINES:
            result, trace = run_solver(csp, heuristic, collect_trace=heuristic == "dom_wdeg")
            baseline_rows.append(result)
            if heuristic == "dom_wdeg":
                trace_rows.extend(trace)
        print(f"baseline {index:02d}/{len(instances)} {csp.instance_id}", flush=True)

    baselines = pd.DataFrame(baseline_rows)
    trace = pd.DataFrame(trace_rows)
    baselines.to_csv(output_dir / "baseline_runs.csv", index=False)
    trace.to_csv(output_dir / "oracle_trace.csv", index=False)

    splits: list[tuple[str, set[str], set[str]]] = []
    grouped_train = {csp.instance_id for csp in instances if int(csp.instance_id.rsplit("-", 1)[1]) < 8 or csp.family == "queens" and int(csp.instance_id.rsplit("-", 1)[1]) < 16}
    all_ids = {csp.instance_id for csp in instances}
    splits.append(("grouped_instance_split", grouped_train, all_ids - grouped_train))
    for held_out in ("queens", "coloring", "latin"):
        test_ids = {csp.instance_id for csp in instances if csp.family == held_out}
        splits.append((f"leave_{held_out}_out", all_ids - test_ids, test_ids))

    summaries: list[dict] = []
    evaluation_rows: list[dict] = []
    model_seeds = [11, 23, 42, 71, 101]
    for split_name, train_ids, test_ids in splits:
        baseline = choose_train_baseline(baselines, train_ids)
        for model_seed in model_seeds:
            model = train_policy(trace, train_ids, model_seed)
            policy = learned_heuristic(model)
            split_rows: list[dict] = []
            for csp in instances:
                if csp.instance_id not in test_ids:
                    continue
                result, _ = run_solver(csp, policy)
                result["split"] = split_name
                result["model_seed"] = model_seed
                split_rows.append(result)
                evaluation_rows.append(result)
                selected = baselines[
                    (baselines["instance_id"] == csp.instance_id)
                    & (baselines["heuristic"] == baseline)
                ].iloc[0].to_dict()
                selected["split"] = split_name
                selected["model_seed"] = model_seed
                split_rows.append(selected)
                evaluation_rows.append(selected)
            split_frame = pd.DataFrame(split_rows)
            summary = summarize_evaluation(split_frame, split_name, baseline)
            summary["model_seed"] = model_seed
            summary["top1_node_accuracy"] = top1_accuracy(model, trace, test_ids)
            summary["train_instances"] = len(train_ids)
            summary["test_instances"] = len(test_ids)
            summary["all_valid"] = bool(split_frame["valid"].all())
            summaries.append(summary)
            print(json.dumps(summary, ensure_ascii=False), flush=True)

    pd.DataFrame(evaluation_rows).to_csv(output_dir / "evaluation_runs.csv", index=False)
    report = {
        "protocol": {
            "families": ["queens", "coloring", "latin"],
            "instances_per_family": 12,
            "labels": "dom/wdeg imitation at candidate level",
            "classifier": "sklearn HistGradientBoostingClassifier",
            "model_seeds": model_seeds,
            "selection_rule": "baseline selected by median train nodes only",
            "validation": "all returned assignments checked independently against domains and binary constraints",
            "splits": [name for name, _, _ in splits],
            "metrics": ["node top-1", "nodes", "wall time", "inference share"],
            "scientific_scope": "small synthetic binary CSPs; feasibility search only",
        },
        "dataset": {
            "trace_rows": len(trace),
            "decision_nodes": int(trace["node_id"].nunique()),
            "instances": len(instances),
        },
        "results": summaries,
    }
    (output_dir / "maturation_report.json").write_text(
        json.dumps(report, ensure_ascii=False, indent=2) + "\n",
        encoding="utf-8",
    )



print('Protocole expérimental prêt : split groupé et leave-one-family-out')

Protocole expérimental prêt : split groupé et leave-one-family-out

6. Exécution fraîche — matérialiser le coût de chaque claim

La cellule suivante régénère les CSV et le rapport JSON sous data/app28-learning-to-branch-audit/. Elle résout d’abord les 36 instances avec quatre heuristiques classiques, collecte les lignes candidates aux nœuds visités par dom/wdeg, puis entraîne et évalue 20 combinaisons split × graine.

Le coût de cette exécution est partie intégrante de l’expérience : une politique de branchement n’est pas évaluée hors du solveur. Les temps absolus restent dépendants de la machine et de la charge ; les ratios comparent deux méthodes dans le même run, sur la même instance. Même ces ratios ne sont pas universels, car les CSP sont petits et l’overhead Python occupe une place plus grande que dans un solveur compilé.

Les artefacts committés servent de trace auditable. Le notebook ne se contente pas de les lire : il les régénère avec le code visible, puis les cellules suivantes recalculent les synthèses. Toute divergence entre prose et sortie doit être corrigée après le rerun, jamais masquée par une ancienne capture.

from pathlib import Path

OUTPUT_DIR = Path("data/app28-learning-to-branch-audit")
main(OUTPUT_DIR)
print(f"Artefacts frais écrits dans {OUTPUT_DIR.as_posix()}")

baseline 01/36 queens-8
baseline 02/36 queens-9
baseline 03/36 queens-10
baseline 04/36 queens-11
baseline 05/36 queens-12
baseline 06/36 queens-13
baseline 07/36 queens-14
baseline 08/36 queens-15
baseline 09/36 queens-16
baseline 10/36 queens-17
baseline 11/36 queens-18
baseline 12/36 queens-19
baseline 13/36 coloring-00
baseline 14/36 coloring-01
baseline 15/36 coloring-02
baseline 16/36 coloring-03
baseline 17/36 coloring-04
baseline 18/36 coloring-05
baseline 19/36 coloring-06
baseline 20/36 coloring-07
baseline 21/36 coloring-08
baseline 22/36 coloring-09
baseline 23/36 coloring-10
baseline 24/36 coloring-11
baseline 25/36 latin-00
baseline 26/36 latin-01
baseline 27/36 latin-02
baseline 28/36 latin-03
baseline 29/36 latin-04
baseline 30/36 latin-05
baseline 31/36 latin-06
baseline 32/36 latin-07
baseline 33/36 latin-08
baseline 34/36 latin-09
baseline 35/36 latin-10
baseline 36/36 latin-11
{"split": "grouped_instance_split", "selected_baseline": "mrv", "instances": 12, "all_solved": true, "median_node_ratio": 1.0, "geomean_node_ratio": 1.0067497856067644, "median_time_ratio": 6.416234392515024, "strict_node_wins": 3, "strict_time_wins": 0, "median_inference_share": 0.8981457265774182, "model_seed": 11, "top1_node_accuracy": 0.5733788395904437, "train_instances": 24, "test_instances": 12, "all_valid": true}
{"split": "grouped_instance_split", "selected_baseline": "mrv", "instances": 12, "all_solved": true, "median_node_ratio": 1.0, "geomean_node_ratio": 1.0067497856067644, "median_time_ratio": 6.210823235049293, "strict_node_wins": 3, "strict_time_wins": 0, "median_inference_share": 0.8864611272942726, "model_seed": 23, "top1_node_accuracy": 0.5733788395904437, "train_instances": 24, "test_instances": 12, "all_valid": true}
{"split": "grouped_instance_split", "selected_baseline": "mrv", "instances": 12, "all_solved": true, "median_node_ratio": 1.0, "geomean_node_ratio": 1.0067497856067644, "median_time_ratio": 4.922646973446488, "strict_node_wins": 3, "strict_time_wins": 0, "median_inference_share": 0.878844222688246, "model_seed": 42, "top1_node_accuracy": 0.5733788395904437, "train_instances": 24, "test_instances": 12, "all_valid": true}
{"split": "grouped_instance_split", "selected_baseline": "mrv", "instances": 12, "all_solved": true, "median_node_ratio": 1.0, "geomean_node_ratio": 1.0067497856067644, "median_time_ratio": 4.895260927750485, "strict_node_wins": 3, "strict_time_wins": 0, "median_inference_share": 0.8784348465294736, "model_seed": 71, "top1_node_accuracy": 0.5733788395904437, "train_instances": 24, "test_instances": 12, "all_valid": true}
{"split": "grouped_instance_split", "selected_baseline": "mrv", "instances": 12, "all_solved": true, "median_node_ratio": 1.0, "geomean_node_ratio": 1.0067497856067644, "median_time_ratio": 5.529104472847535, "strict_node_wins": 3, "strict_time_wins": 0, "median_inference_share": 0.890158998676051, "model_seed": 101, "top1_node_accuracy": 0.5733788395904437, "train_instances": 24, "test_instances": 12, "all_valid": true}
{"split": "leave_queens_out", "selected_baseline": "dom_wdeg", "instances": 12, "all_solved": true, "median_node_ratio": 2.8166666666666664, "geomean_node_ratio": 4.263644469515691, "median_time_ratio": 14.448533561479891, "strict_node_wins": 2, "strict_time_wins": 0, "median_inference_share": 0.7694849279740057, "model_seed": 11, "top1_node_accuracy": 0.6318681318681318, "train_instances": 24, "test_instances": 12, "all_valid": true}
{"split": "leave_queens_out", "selected_baseline": "dom_wdeg", "instances": 12, "all_solved": true, "median_node_ratio": 2.783333333333333, "geomean_node_ratio": 4.306952697046635, "median_time_ratio": 11.622819741091888, "strict_node_wins": 2, "strict_time_wins": 0, "median_inference_share": 0.7959769468085847, "model_seed": 23, "top1_node_accuracy": 0.6318681318681318, "train_instances": 24, "test_instances": 12, "all_valid": true}
{"split": "leave_queens_out", "selected_baseline": "dom_wdeg", "instances": 12, "all_solved": true, "median_node_ratio": 2.8166666666666664, "geomean_node_ratio": 4.263073463608035, "median_time_ratio": 9.405084196339384, "strict_node_wins": 2, "strict_time_wins": 0, "median_inference_share": 0.730053793455143, "model_seed": 42, "top1_node_accuracy": 0.6318681318681318, "train_instances": 24, "test_instances": 12, "all_valid": true}
{"split": "leave_queens_out", "selected_baseline": "dom_wdeg", "instances": 12, "all_solved": true, "median_node_ratio": 1.5303030303030303, "geomean_node_ratio": 2.9640047223322656, "median_time_ratio": 6.243062855977116, "strict_node_wins": 1, "strict_time_wins": 0, "median_inference_share": 0.7340159640454067, "model_seed": 71, "top1_node_accuracy": 0.6373626373626373, "train_instances": 24, "test_instances": 12, "all_valid": true}
{"split": "leave_queens_out", "selected_baseline": "dom_wdeg", "instances": 12, "all_solved": true, "median_node_ratio": 1.5303030303030303, "geomean_node_ratio": 2.9683352902851254, "median_time_ratio": 5.327130166720308, "strict_node_wins": 1, "strict_time_wins": 0, "median_inference_share": 0.7235783340746813, "model_seed": 101, "top1_node_accuracy": 0.6208791208791209, "train_instances": 24, "test_instances": 12, "all_valid": true}
{"split": "leave_coloring_out", "selected_baseline": "mrv", "instances": 12, "all_solved": true, "median_node_ratio": 1.0, "geomean_node_ratio": 0.9963670266493989, "median_time_ratio": 13.377832697835757, "strict_node_wins": 1, "strict_time_wins": 0, "median_inference_share": 0.9177396489053196, "model_seed": 11, "top1_node_accuracy": 0.4105691056910569, "train_instances": 24, "test_instances": 12, "all_valid": true}
{"split": "leave_coloring_out", "selected_baseline": "mrv", "instances": 12, "all_solved": true, "median_node_ratio": 1.0, "geomean_node_ratio": 0.9963670266493989, "median_time_ratio": 14.449525997556394, "strict_node_wins": 1, "strict_time_wins": 0, "median_inference_share": 0.9151160352952303, "model_seed": 23, "top1_node_accuracy": 0.4105691056910569, "train_instances": 24, "test_instances": 12, "all_valid": true}
{"split": "leave_coloring_out", "selected_baseline": "mrv", "instances": 12, "all_solved": true, "median_node_ratio": 1.0, "geomean_node_ratio": 0.9963670266493989, "median_time_ratio": 18.15738956968574, "strict_node_wins": 1, "strict_time_wins": 0, "median_inference_share": 0.9303289862676241, "model_seed": 42, "top1_node_accuracy": 0.4105691056910569, "train_instances": 24, "test_instances": 12, "all_valid": true}
{"split": "leave_coloring_out", "selected_baseline": "mrv", "instances": 12, "all_solved": true, "median_node_ratio": 1.0, "geomean_node_ratio": 0.9963670266493989, "median_time_ratio": 19.655395938550697, "strict_node_wins": 1, "strict_time_wins": 0, "median_inference_share": 0.9327477318183722, "model_seed": 71, "top1_node_accuracy": 0.4105691056910569, "train_instances": 24, "test_instances": 12, "all_valid": true}
{"split": "leave_coloring_out", "selected_baseline": "mrv", "instances": 12, "all_solved": true, "median_node_ratio": 1.0, "geomean_node_ratio": 0.9963670266493989, "median_time_ratio": 17.594910637754406, "strict_node_wins": 1, "strict_time_wins": 0, "median_inference_share": 0.9253824018777206, "model_seed": 101, "top1_node_accuracy": 0.4105691056910569, "train_instances": 24, "test_instances": 12, "all_valid": true}
{"split": "leave_latin_out", "selected_baseline": "mrv", "instances": 12, "all_solved": true, "median_node_ratio": 1.0, "geomean_node_ratio": 1.0, "median_time_ratio": 9.13204513251352, "strict_node_wins": 0, "strict_time_wins": 0, "median_inference_share": 0.9082542062964847, "model_seed": 11, "top1_node_accuracy": 0.5983606557377049, "train_instances": 24, "test_instances": 12, "all_valid": true}
{"split": "leave_latin_out", "selected_baseline": "mrv", "instances": 12, "all_solved": true, "median_node_ratio": 1.0, "geomean_node_ratio": 1.0, "median_time_ratio": 7.294684274450585, "strict_node_wins": 0, "strict_time_wins": 0, "median_inference_share": 0.8928376686439008, "model_seed": 23, "top1_node_accuracy": 0.5983606557377049, "train_instances": 24, "test_instances": 12, "all_valid": true}
{"split": "leave_latin_out", "selected_baseline": "mrv", "instances": 12, "all_solved": true, "median_node_ratio": 1.0, "geomean_node_ratio": 1.0, "median_time_ratio": 9.554796862430507, "strict_node_wins": 0, "strict_time_wins": 0, "median_inference_share": 0.9034135400664169, "model_seed": 42, "top1_node_accuracy": 0.5983606557377049, "train_instances": 24, "test_instances": 12, "all_valid": true}
{"split": "leave_latin_out", "selected_baseline": "mrv", "instances": 12, "all_solved": true, "median_node_ratio": 1.0, "geomean_node_ratio": 1.0, "median_time_ratio": 7.358786088882092, "strict_node_wins": 0, "strict_time_wins": 0, "median_inference_share": 0.8935421230346438, "model_seed": 71, "top1_node_accuracy": 0.5983606557377049, "train_instances": 24, "test_instances": 12, "all_valid": true}
{"split": "leave_latin_out", "selected_baseline": "mrv", "instances": 12, "all_solved": true, "median_node_ratio": 1.0, "geomean_node_ratio": 1.0, "median_time_ratio": 7.439559121981002, "strict_node_wins": 0, "strict_time_wins": 0, "median_inference_share": 0.8920706724374046, "model_seed": 101, "top1_node_accuracy": 0.5983606557377049, "train_instances": 24, "test_instances": 12, "all_valid": true}
Artefacts frais écrits dans data/app28-learning-to-branch-audit

Vingt évaluations, toutes valides, mais pas vingt preuves indépendantes

Les lignes ci-dessus constituent la trace du run complet : 36 instances, quatre heuristiques classiques, quatre protocoles de séparation et cinq graines. Toute ligne all_valid: true atteste que les solutions des deux méthodes ont passé le validateur indépendant.

Les cinq graines d’un split réutilisent toutefois les mêmes instances et les mêmes labels. Elles échantillonnent l’instabilité de l’entraînement, pas cinq jeux de test indépendants. Si l’argmax du modèle reste identique, les nœuds seront identiques même si les probabilités changent légèrement ; le temps, lui, continue à fluctuer avec la machine.

7. Synthèse multi-seed — séparer stabilité et généralisation

La table agrège maintenant les cinq répétitions de chaque split. Une victoire en nœuds ne suffit pas : une politique utile doit aussi amortir son inférence. Les intervalles min–max ne sont pas des intervalles de confiance ; ils décrivent seulement les cinq graines annoncées.

Le split groupé mesure le renouvellement d’instances au sein d’un mélange de familles. Les splits leave-one-family-out mesurent un transfert de structure. Les comparer révèle si une politique stable est réellement robuste ou simplement stable dans sa zone d’entraînement.

import json

report = json.loads((OUTPUT_DIR / "maturation_report.json").read_text(encoding="utf-8"))
summary = pd.DataFrame(report["results"])
aggregate = summary.groupby("split").agg(
    graines=("model_seed", "count"),
    top1_min=("top1_node_accuracy", "min"),
    top1_max=("top1_node_accuracy", "max"),
    ratio_noeuds_med_min=("median_node_ratio", "min"),
    ratio_noeuds_med_max=("median_node_ratio", "max"),
    ratio_temps_med_min=("median_time_ratio", "min"),
    ratio_temps_med_max=("median_time_ratio", "max"),
    victoires_temps=("strict_time_wins", "sum"),
    solutions_valides=("all_valid", "all"),
).round(3)
aggregate

	graines	top1_min	top1_max	ratio_noeuds_med_min	ratio_noeuds_med_max	ratio_temps_med_min	ratio_temps_med_max	victoires_temps	solutions_valides
split
grouped_instance_split	5	0.573	0.573	1.00	1.000	4.895	6.416	0	True
leave_coloring_out	5	0.411	0.411	1.00	1.000	13.378	19.655	0	True
leave_latin_out	5	0.598	0.598	1.00	1.000	7.295	9.555	0	True
leave_queens_out	5	0.621	0.637	1.53	2.817	5.327	14.449	0	True

Stable ne signifie pas général, et moins de nœuds ne signifie pas plus rapide

Le split groupé, coloring-out et latin-out ont un top-1 et des ratios de nœuds identiques sur les cinq graines : l’argmax de la politique est stable à cette échelle. Cette invariance ne fournit pas cinq confirmations indépendantes ; elle dit que les variations internes du gradient boosting ne changent pas le candidat classé premier sur ces nœuds.

Seul le transfert vers N-reines expose une variabilité de politique visible. Le top-1 varie de 0,621 à 0,637 et la médiane de nœuds de 1,53× à 2,82× celle de dom/wdeg. La famille tenue à l’écart combine une structure dense et des diagonales absentes des deux autres familles : les features locales ne suffisent pas à préserver le comportement de l’oracle.

Le résultat temporel est plus sévère qu’une simple absence de gain. Selon split et graine, la médiane vaut 4,90× à 19,66× le temps de la baseline, avec zéro victoire stricte sur 240 comparaisons held-out. Le split coloring-out peut même avoir une moyenne géométrique de nœuds légèrement favorable tout en restant 13,38× à 19,66× plus lent en médiane.

La leçon n’est pas « le ML ne marche pas ». Elle est conditionnelle et plus utile : sur ce banc, avec scoring pandas/scikit-learn à chaque nœud, l’imitation locale ne réduit pas assez l’arbre pour amortir son coût et ne transfère pas proprement vers N-reines.

evaluation = pd.read_csv(OUTPUT_DIR / "evaluation_runs.csv")
learned = evaluation[evaluation["heuristic"] == "learned_policy"].copy()
inference_by_split = learned.groupby("split").agg(
    part_inference_mediane=("inference_seconds", lambda s: float((s / learned.loc[s.index, "seconds"]).median())),
    temps_total_median=("seconds", "median"),
    noeuds_medians=("nodes", "median"),
).round(3)
inference_by_split

	part_inference_mediane	temps_total_median	noeuds_medians
split
grouped_instance_split	0.893	0.123	25.0
leave_coloring_out	0.926	0.096	21.5
leave_latin_out	0.896	0.171	30.5
leave_queens_out	0.747	0.112	30.0

Le coût d’inférence domine précisément quand l’arbre est petit

La part d’inférence médiane atteint 72,4 % à 93,3 % selon le split et la graine. Agrégée par famille de split, elle reste comprise entre 74,7 % et 92,6 %. Scorer chaque variable construit un DataFrame et appelle predict_proba à chaque nœud ; sur des arbres de 21,5 à 30,5 nœuds médians, ce coût fixe est difficile à amortir. Sur une instance beaucoup plus dure, une réduction substantielle de l’arbre pourrait changer l’équilibre — ce notebook ne l’observe pas et ne l’affirme pas.

La décomposition évite deux lectures abusives. Premièrement, retirer artificiellement le temps d’inférence répondrait à une question contrefactuelle : le solveur réellement déployé doit payer ce coût. Deuxièmement, extrapoler le facteur 19,66× à un moteur compilé serait tout aussi incorrect. Le résultat porte sur cette implémentation Python per-node.

9. Quatre exercices développés

Les exercices restent volontairement stubbés afin que le notebook s’exécute de bout en bout. Chacun rejoue un garde méthodologique central plutôt qu’une simple variation syntaxique.

Exercice 1 — Détecter une fuite par nœud et par instance

Construisez les ensembles de node_id et d’instance_id des deux côtés. Vérifiez les deux intersections avant d’entraîner.

Questions : pourquoi une intersection vide de nœuds ne suffit-elle pas ? Quel objet doit être passé à GroupShuffleSplit ? Comment testeriez-vous la disjonction dans une CI ?

Étapes suggérées : filtrer la trace par listes d’instances, extraire les identifiants, calculer les intersections et retourner un dictionnaire de deux booléens. Le stub doit rester sûr si les ensembles sont vides.

# TODO étudiant : construire train_node_ids et test_node_ids à partir de deux listes d'instances.
train_node_ids = set()
test_node_ids = set()
leakage_detected = None  # TODO étudiant : remplacer par bool(train_node_ids & test_node_ids)
print("Exercice 1 à compléter : détecter l'intersection des nœuds")

Exercice 1 à compléter : détecter l'intersection des nœuds

Exercice 2 — Choisir une baseline sans fuite

À partir de baseline_runs.csv, choisissez l’heuristique de plus faible médiane de nœuds sur les seules instances d’entraînement d’un split.

Questions d’interprétation :

Pourquoi faut-il sélectionner une baseline différente pour chaque split ?
Comment départager deux heuristiques de médiane identique sans consulter le test ?
Pourquoi publier la règle de tie-break est-il nécessaire à la reproductibilité ?

Étapes suggérées : construire train_ids, filtrer le DataFrame avant le groupby, calculer médiane puis moyenne géométrique ou utiliser un ordre stable annoncé. Ajoutez une assertion garantissant que les instance_id test sont absents du tableau de sélection.

Le stub conserve None afin que l’exercice ne révèle pas la réponse et que le notebook reste exécutable.

# TODO étudiant : filtrer sur les instances train avant tout groupby.
selected_baseline = None
print("Exercice 2 à compléter : sélectionner la baseline sur le train uniquement")

Exercice 2 à compléter : sélectionner la baseline sur le train uniquement

Exercice 3 — Concevoir une règle d’abstention

Proposez une politique hybride : employer le modèle seulement lorsque son score dépasse un seuil et revenir à dom/wdeg sinon. Mesurez nœuds et temps mur.

Questions d’interprétation :

Une probabilité élevée de classe 1 est-elle une confiance calibrée entre candidats d’un même nœud ?
Quel seuil choisissez-vous sans consulter les instances test ?
Une abstention fréquente peut-elle rester utile si elle paie tout de même le coût de predict_proba ?

Étapes suggérées : calibrer le seuil sur une validation issue du train, retourner None sous le seuil, faire appliquer alors dom/wdeg, puis rapporter taux d’abstention, top-1 conditionnel, nœuds et temps total. Comparez aussi un critère de marge entre les deux meilleurs scores.

Le stub est sûr : il retourne None, ce qui représente précisément la décision d’abstention à traiter.

def abstaining_policy(candidates, rows, threshold=0.9):
    # TODO étudiant : scorer, tester la confiance, puis retourner un candidat ou None.
    return None

print("Exercice 3 à compléter : ajouter une règle d'abstention")

Exercice 3 à compléter : ajouter une règle d'abstention

Exercice 4 — Calculer le seuil d’amortissement

Supposons que la baseline coûte \(c_b\) par nœud et que la politique apprise ajoute \(c_{ML}\) de scoring. Dérivez la réduction minimale de nœuds nécessaire pour égaler le temps de la baseline :

\[n_{ML}(c_b+c_{ML})\le n_b c_b.\]

Questions d’interprétation :

Quel ratio \(n_{ML}/n_b\) faut-il atteindre lorsque l’inférence représente 85 % du temps ML ?
Pourquoi ce seuil dépend-il de l’implémentation et de la taille du CSP ?
Batcher plusieurs nœuds est-il compatible avec un backtracking strictement séquentiel ?

Étapes suggérées : isoler \(n_{ML}/n_b\), estimer \(c_{ML}/c_b\) depuis les timings du run, puis comparer ce seuil aux ratios observés. Effectuez une analyse de sensibilité plutôt que de traiter un timing unique comme une constante.

Cet exercice transforme le résultat négatif en condition d’ingénierie : combien d’arbre faut-il réellement économiser pour payer le modèle ?

def break_even_node_ratio(inference_share: float):
    # TODO étudiant : dériver le ratio maximal n_ml / n_baseline qui amortit l'inférence.
    return None

print("Exercice 4 à compléter : seuil d'amortissement de l'inférence")

Exercice 4 à compléter : seuil d'amortissement de l'inférence

10. Bilan critique — ce que la garantie apporte et ce qu’elle coûte

Claim	Preuve dans App-28	Coût de la garantie	Limite
Pas de fuite par instance	identifiants train/test disjoints	moins de lignes corrélées disponibles pour entraîner	seulement 36 instances
Transfert inter-familles	trois leave-one-family-out	trois entraînements et évaluations supplémentaires	familles synthétiques seulement
Solution correcte	validateur indépendant	recalcul de toutes les relations	même générateur et relations que le solveur
Fidélité locale	top-1 agrégé par `node_id`	conserver les groupes de candidats	oracle heuristique, pas contrefactuel
Effet sur l’arbre	politique réinjectée dans le solveur	résoudre chaque CSP pour chaque graine	première solution, limite 20 000 nœuds
Coût opérationnel	temps mur et part d’inférence	instrumentation à chaque décision	mesure machine-dépendante
Stabilité	cinq graines annoncées	cinq entraînements par split	mêmes instances, pas cinq réplications indépendantes

Les garanties ont un prix expérimental. Grouper par instance réduit la taille effective du train ; tenir une famille à l’écart rend la tâche plus dure ; réinjecter le modèle oblige à exécuter tout le solveur ; mesurer l’inférence empêche de présenter un gain de nœuds comme un gain gratuit. Ce prix est précisément ce qui transforme une démonstration de classification en audit de politique.

Limites scientifiques

Le banc contient de petits CSP binaires synthétiques et cherche une première solution ; il ne couvre ni contraintes globales natives, ni optimisation, ni solveurs industriels. dom/wdeg et activity sont des variantes pédagogiques, non des implémentations canoniques complètes. Les temps absolus et les facteurs 4,90×–19,66× appartiennent à cette machine et au scoring pandas/scikit-learn per-node. L’absence de gain n’est donc pas une réfutation générale du learning-to-branch.

L’oracle imité reste une heuristique. Une suite plus ambitieuse apprendrait une valeur contrefactuelle ou un ranking groupé, distillerait le modèle vers une règle légère, ajouterait abstention et cache, testerait des instances plus dures, et comparerait à budget de calcul égal. Ces extensions doivent conserver les splits groupés et le validateur, faute de quoi elles amélioreraient le score en affaiblissant la preuve.

Hommage à Simon Naulet et Matis Codjia

Le projet G4 a eu l’ambition de ne pas traiter le solveur comme une boîte noire. Il expose AC-3, les domaines, les conflits, les features et la décision de branchement, puis demande au ML d’entrer dans cette boucle. Cette architecture rend possible l’audit mené ici : sans mini-solveur instrumentable ni formulation explicite de dom/wdeg, il serait impossible de distinguer imitation, arbre et temps.

La maturation CoursIA ne transforme pas le résultat négatif en critique des auteurs. Elle prolonge leur geste en lui appliquant un protocole plus sévère : nouveaux groupes d’instances, familles tenues à l’écart, baseline choisie sur train, coût d’inférence et validation indépendante. Aucun code, texte, cellule, figure ou jeu de données étudiant n’est copié ; l’appareil est réécrit et l’attribution demeure centrale.

Conclusion — une bonne décision locale doit encore payer sa place dans le solveur

App-28 établit quatre résultats bornés. Premièrement, le split doit suivre l’instance, pas les lignes candidates. Deuxièmement, un top-1 stable ne garantit ni transfert ni réduction de l’arbre. Troisièmement, le transfert vers N-reines dégrade ici la médiane de nœuds jusqu’à 2,82×. Quatrièmement, l’inférence consomme 72,4 % à 93,3 % du temps ML selon split et graine et conduit à zéro victoire temporelle sur 240 comparaisons, avec des médianes 4,90× à 19,66× plus lentes.

Le ML ne gagne pas sur ce banc. Cette absence de gain est un résultat scientifique parce que le protocole permet de dire où la promesse échoue : stabilité locale, transfert structurel et amortissement du coût. Le résultat transférable n’est pas « éviter le ML », mais une méthode : grouper avant d’évaluer, comparer une trajectoire complète, compter le coût réel et conserver la validité comme condition préalable.

Références

Boussemart, F., Hemery, F., Lecoutre, C. & Sais, L. (2004). Boosting systematic search by weighting constraints. ECAI.
Kotthoff, L. (2014). Algorithm Selection for Combinatorial Search Problems: A Survey. AI Magazine.
Bengio, Y., Lodi, A. & Prouvost, A. (2021). Machine Learning for Combinatorial Optimization: a Methodological Tour d’Horizon. EJOR.
Balcan, M.-F. (2020). Data-Driven Algorithm Design. Beyond the Worst-Case Analysis of Algorithms.

Retour au sommet

Auditer la généralisation avant d’annoncer un gain

Hommage et question scientifique

Quatre niveaux à ne pas confondre

Objectifs d’apprentissage

Prérequis

1. Pourquoi le split naïf est trompeur

2. Exemple guide — un solveur et un validateur indépendants

Le noyau sépare décision, propagation et preuve de validité

3. Instances déterministes et distinctes

Trois familles contrôlées, trois formes de décalage

4. Dériver dom/wdeg et les features locales

Imiter un oracle heuristique ne crée pas une oracle contrefactuelle

5. Protocole complet — du candidat à la trajectoire

6. Exécution fraîche — matérialiser le coût de chaque claim

Vingt évaluations, toutes valides, mais pas vingt preuves indépendantes

7. Synthèse multi-seed — séparer stabilité et généralisation

Stable ne signifie pas général, et moins de nœuds ne signifie pas plus rapide

Le coût d’inférence domine précisément quand l’arbre est petit

9. Quatre exercices développés

Exercice 1 — Détecter une fuite par nœud et par instance

Exercice 2 — Choisir une baseline sans fuite

Exercice 3 — Concevoir une règle d’abstention

Exercice 4 — Calculer le seuil d’amortissement

10. Bilan critique — ce que la garantie apporte et ce qu’elle coûte

Limites scientifiques

Hommage à Simon Naulet et Matis Codjia

Conclusion — une bonne décision locale doit encore payer sa place dans le solveur

Références

4. Dériver `dom/wdeg` et les features locales