App-33 — Neural diving : un plongeur appris pour CP-SAT

Du conseil aux valeurs aux branches prouvées : ce que le diving apporte, mesure à l’appui

← Applications | ↑ Search | << App-31 Bornes RCPSP

Durée estimée : 60 minutes

Hommage et question scientifique

Une branche de la recherche « machine learning for combinatorial optimization » promet d’apprendre une solution initiale pour accélérer le solveur : c’est le diving de Nair et al. (2021), « Solving Mixed Integer Programs Using Neural Networks » (arXiv:2012.13349, v3, juillet 2021). Leur apport se compose de deux gestes distincts : la priorité de branchement (choisir quelle variable contribuer en premier, à chaque nœud) et le plongement (apprendre quel sous-ensemble de variables fixer tout de suite). La composante branchement a déjà été auditée dans ce dépôt : App-28 Learning to Branch y mesure qu’une politique locale fidèle ne garantit ni un arbre plus petit ni un solveur plus rapide. Ce notebook reprend l’autre composante, sur un terrain contrôlé : un plongeur MLP qui prédit une affectation partielle, injectée comme hint (conseil) dans un solveur réel, OR-Tools CP-SAT, sur une famille de coloration de graphe calibrée pour brancher.

La reproduction est entièrement locale, sur une famille synthétique de taille notebook, et ne copie ni code ni figure de l’article. Le but n’est pas de « refaire l’article », mais de mesurer sur un cas où la recherche travaille vraiment ce que le mécanisme promet : moins de nœuds, ou une recherche plus stable. Verdict au programme : deux nombres ensemble — la médiane des branches, et la queue de distribution.

Source : G:\Mon Drive\MyIA\IA\Bibliographie IA\Search\2021 - Nair et al - Solving Mixed Integer Programs Using Neural Networks.pdf (gisement partagé).

1. Où le diving s’insère dans l’architecture d’un solveur

Un solveur de programmation par contraintes (CP-SAT ici) cherche en alternant deux opérations : brancher (fixer une variable à une valeur) et propager (déduire les conséquences). La taille de la recherche se mesure en nombre de branches explorées avant la première preuve d’optimalité (NumBranches()).

L’apprentissage à base de solutions a deux levers bien distincts, souvent mélangés :

Levier Portée Effet documenté
Branching appris une décision à chaque nœud (quelle variable) imité localement, ne garantit pas un arbre plus petit (App-28)
Diving appris une décision une fois (quelles valeurs suggérer) donne un point de départ : la recherche contient-elle des mauvaises décisions précoces ?

Le diving ne change pas la stratégie de branche, il change l’état initial. Dans CP-SAT, il se traduit par AddHint(var, valeur) : le solveur reçoit un conseil, s’en sert pour diriger sa recherche, et le corrige si le conseil contredit les contraintes. Cette correction est mesurable : quand un hint viole des arêtes d’adjacence, on dit qu’il porte des conflits.

from __future__ import annotations

import time
from pathlib import Path

import numpy as np
from ortools.sat.python import cp_model

NV, KMAX, DEG = 60, 6, 3          # 60 sommets, 6 couleurs max, ~3 aretes / sommet
SEED0, N_TRAIN, N_TEST = 5000, 60, 25
OUTPUT_DIR = Path("data/app33-neural-diving")


def make_graph(seed: int) -> np.ndarray:
    """Graphe 60 sommets, DEG aretes / sommet, tirage seedé par sommet."""
    r = np.random.default_rng(seed)
    adj = np.zeros((NV, NV), dtype=np.int8)
    for v in range(NV):
        for _ in range(DEG):
            u = int(r.integers(NV))
            if u != v:
                adj[v, u] = adj[u, v] = 1
    return adj


print("Imports chargés : numpy + OR-Tools CP-SAT 9.15")
Imports chargés : numpy + OR-Tools CP-SAT 9.15

2. Un solveur coloriable, instrumenté, paramétrable

Le modèle est volontairement simple : une coloration propre à 6 couleurs — chaque sommet reçoit exactement une couleur (AddExactlyOne), deux sommets adjacents ne partagent aucune couleur (c[v, j] + c[u, j] <= 1), et le solveur minimise le nombre de couleurs réellement utilisées (variables used). La solution optimale de ces graphes consomme 4 couleurs (mesuré pendant la calibration).

Le paramètre important est hint : None pour la recherche pure, ou une matrice one-hot (60 × 6) de valeurs suggérées. Les suggestions sont exprimées par model.AddHint(...) — le solveur s’en sert pour orienter sa recherche sans obéir : il peut les corriger. Chaque résolution rapporte NumBranches() et le temps mur.

def solve_coloring(adj: np.ndarray, hint: np.ndarray | None = None,
                   time_limit: float = 15.0) -> tuple[int, int, float, np.ndarray | None]:
    """Resout la coloration propre de `adj` ; rend (couleurs, branches, temps, solution)."""
    model = cp_model.CpModel()
    c = [[model.NewBoolVar(f"c{v}_{j}") for j in range(KMAX)] for v in range(NV)]
    for v in range(NV):
        model.AddExactlyOne(c[v])
    for v in range(NV):
        for u in range(v + 1, NV):
            if adj[v, u]:
                for j in range(KMAX):
                    model.Add(c[v][j] + c[u][j] <= 1)
    used = [model.NewBoolVar(f"u{j}") for j in range(KMAX)]
    for j in range(KMAX):
        for v in range(NV):
            model.Add(used[j] >= c[v][j])
    model.Minimize(sum(used))
    if hint is not None:
        for v in range(NV):
            for j in range(KMAX):
                model.AddHint(c[v][j], int(hint[v, j]))
    solver = cp_model.CpSolver()
    solver.parameters.max_time_in_seconds = time_limit
    solver.parameters.random_seed = 7
    solver.parameters.num_workers = 1
    t0 = time.perf_counter()
    status = solver.Solve(model)
    wall = time.perf_counter() - t0
    if status != cp_model.OPTIMAL:
        return 0, solver.NumBranches(), wall, None
    sol = np.array([[solver.Value(c[v][j]) for j in range(KMAX)] for v in range(NV)], dtype=np.int8)
    colors = int(sol.sum(axis=0).clip(0, 1).sum())
    return colors, solver.NumBranches(), wall, sol


# controle moteur : le solveur tourne et la famille est optimale en 4 couleurs
adj0 = make_graph(SEED0)
k, nodes, wall, sol0 = solve_coloring(adj0)
print(f"smoke test : {k} couleurs, {nodes} branches, {wall:.3f} s")
smoke test : 4 couleurs, 2738 branches, 0.041 s

La symétrie des couleurs : un label en cache un autre

Toute solution peut être réécrite en permutant les noms des couleurs : colorier le sommet A en rouge et B en bleu, ou A en bleu et B en rouge, est la même affectation du point de vue des contraintes. Le solveur peut donc rendre l’une des \(6! = 720\) réécritures équivalentes.

Pour un apprentissage supervisé de la solution (notre plongeur prédit un one-hot par sommet), cette symétrie est un bruit d’étiquettes : deux exemples identiques du point de vue du problème reçoivent des labels différents. Avant d’entraîner quoi que ce soit, on canonise les solutions : on renomme les couleurs par ordre de première apparition le long des sommets — la première couleur rencontrée devient 0, la suivante 1, etc. La table de renommage est propre à chaque solution, elle ne normalise donc rien d’autre que le nom des couleurs.

def canonize(sol: np.ndarray) -> np.ndarray:
    """Reordonne les couleurs par ordre de premiere occurrence dans les sommets."""
    order: list[int] = []
    sol_c = sol.copy()
    for v in range(NV):
        j0 = int(np.argmax(sol[v]))
        if j0 not in order:
            order.append(j0)
    remap = {old: new for new, old in enumerate(order)}
    for v in range(NV):
        j0 = remap[int(np.argmax(sol[v]))]
        sol_c[v] = 0
        sol_c[v, j0] = 1
    return sol_c


# demonstration : canonize annule n'importe quelle permutation des couleurs
rng = np.random.default_rng(123)
perm = rng.permutation(KMAX)
sol_perm = np.zeros_like(sol0)
for v in range(NV):
    sol_perm[v, int(perm[int(np.argmax(sol0[v]))])] = 1
aligned = (canonize(sol0) == canonize(sol_perm)).all()
print(f"canonize aligne une solution et sa permutation de couleurs : {aligned}")
canonize aligne une solution et sa permutation de couleurs : True

3. Calibrer la famille : la fenêtre où la recherche travaille

Un effet du diving ne se mesure que là où la recherche existe. Trois familles typiques ont été calibrées avec num_workers = 1 et random_seed = 7, comme tout le reste du notebook :

Famille Configuration Nœuds (médiane) Verdict
Set-cover à couverture ≥ 2 m=45, n=60, densité 10 % 0 effondré au presolve : CP-SAT résout sans jamais brancher
Knapsack multidim. corrélé n=40, d=5, profits ∝ poids 102 284 (limite 3 s, non prouvé) brasse sans preuve : la fenêtre est trop dure
Coloration 60 sommets, ~3 arêtes/sommet nv=60, deg=3, k≤6 2742 (2303-3799) branche quelques milliers de fois et prouve l’optimalité en < 0,1 s

La coloration est la fenêtre : assez dure pour que la recherche ait une vraie trajectoire de branches, assez facile pour que chaque résolution se prouve en quelques centièmes de seconde — indispensable pour un notebook qui enchaîne 60 + 25 résolutions. Les deux premières lignes viennent de la sonde probe ci-dessous (un tirage chacune) ; la médiane de la coloration est celle des 60 instances d’entraînement, imprimée par la cellule d’entraînement. Le fait mesuré que les familles denses s’effondrent au presolve est reporté ici honnêtement, pas maquillé : c’est la définition de la fenêtre.

def cover2(m_: int, n_: int, dens: float, seed: int) -> cp_model.CpModel:
    """Set-cover a couverture double creux (presolve-solvable en taille notebook)."""
    r = np.random.default_rng(seed)
    mat = (r.random((m_, n_)) < dens).astype(np.int8)
    for i in range(m_):
        if mat[i].sum() < 2:
            js = r.choice(n_, size=2, replace=False)
            mat[i, js] = 1
    mod = cp_model.CpModel()
    x = [mod.NewBoolVar(f"x{j}") for j in range(n_)]
    for i in range(m_):
        cols = [j for j in range(n_) if mat[i, j]]
        mod.Add(sum(x[j] for j in cols) >= 2)
    mod.Minimize(sum(x))
    return mod


def mknap_corr(n_: int, d: int, seed: int) -> cp_model.CpModel:
    """Knapsack multidim. correle : profits proches de la somme des poids (gap LP faible)."""
    r = np.random.default_rng(seed)
    w = r.integers(10, 50, size=(d, n_))
    caps = w.sum(axis=1) * 0.5
    profits = w.sum(axis=0) + r.integers(-2, 3, size=n_)
    m = cp_model.CpModel()
    x = [m.NewBoolVar(f"x{j}") for j in range(n_)]
    for i in range(d):
        m.Add(sum(int(w[i, j]) * x[j] for j in range(n_)) <= int(caps[i]))
    m.Maximize(sum(int(profits[j]) * x[j] for j in range(n_)))
    return m


def probe(model: cp_model.CpModel, time_limit: float) -> tuple[int, float, bool]:
    solver = cp_model.CpSolver()
    solver.parameters.max_time_in_seconds = time_limit
    solver.parameters.random_seed = 7
    solver.parameters.num_workers = 1
    t0 = time.perf_counter()
    status = solver.Solve(model)
    return solver.NumBranches(), time.perf_counter() - t0, status == cp_model.OPTIMAL


for name, fn, tl in [
    ("set-cover double (m45 n60)", lambda: cover2(45, 60, 0.10, 4001), 3.0),
    ("knapsack correle (n40 d5)", lambda: mknap_corr(40, 5, 4001), 3.0),
]:
    nodes, wall, ok = probe(fn(), tl)
    print(f"{name:26s} | nodes={nodes:8d} temps={wall:6.2f}s opt={ok}")
# la fenetre (coloration 60v) est mesuree par solve_coloring en section 2
# (smoke test : 2738 branches) et par la boucle d'entrainement (mediane 2742)
set-cover double (m45 n60) | nodes=       0 temps=  0.00s opt=True
knapsack correle (n40 d5)  | nodes=  102384 temps=  3.00s opt=False

Interprétation : pourquoi une seule colonne du tableau compte

  • Set-cover denses : nodes = 0 signifie que CP-SAT résout au presolve — il n’y a aucune recherche à influencer. Un plongeur y serait mesuré « sans effet » ou, pire, « négatif » sans rien dire du mécanisme.
  • Knapsack corrélé : le solveur brasse (timeout 3 s dans le probe ci-dessus) sans atteindre l’optimalité — la métrique « branches » y perd son sens (on compte des branches d’une preuve qui n’existe pas).
  • Coloration : les deux extrémités sont évitées. 25 instances dans la fenêtre, c’est une courbe de distribution exploitable.

C’est la raison pour laquelle la section 2 instrumente la coloration : le terrain d’expérience d’un plongeur est une famille qui branche ET se prouve.

4. Le plongeur : un MLP qui prédit l’affectation

Le prototype qui fonde ce notebook (mesures du 2026-09-23, seeds constants)

  • Train : les graphes 5000..5059 (60 instances), chacun résolu à l’optimum, solutions canonisées ;
  • Features : matrice d’adjacence aplatie (60 × 60 = 3600 booléens) ;
  • Labels : one-hot (60 × 6) de la couleur canonique de chaque sommet, aplati ;
  • Modèle : MLPClassifier((128, 128)), max_iter=3000, random_state=0 — sur des données 100 % déterministes ;
  • Test : graphes 6000..6024 (25 instances), non vus au train ; prédiction → one-hot par argmax sur les 6 sorties par sommet ;
  • Mesure A/B : résoudre chaque graphe du test une fois pur (hint=None) et une fois avec hint (la prédiction canonisée) ; on compare NumBranches() et le temps mur. On compte aussi les conflits du hint : nombre d’arêtes dont les deux extrémités reçoivent la même couleur prédite.

⚠️ Particularité scikit-learn 1.6 : en multioutput binaire, predict_proba ne rend pas une liste de paires mais un tableau (1, 360) de probabilités de la classe 1 — on le reforme en (60, 6) et l’argmax par bloc garantit le one-hot.

def main(output_dir: Path) -> None:
    output_dir.mkdir(parents=True, exist_ok=True)
    Xtr, Ytr, ks, nodes_tr = [], [], [], []
    for s in range(SEED0, SEED0 + N_TRAIN):
        adj = make_graph(s)
        k, nd, _, sol = solve_coloring(adj)
        Xtr.append(adj.flatten())
        Ytr.append(canonize(sol).flatten())
        ks.append(k)
        nodes_tr.append(nd)
    print(f"train : couleurs med={np.median(ks):.0f}, branches med={np.median(nodes_tr):.0f}")

    from sklearn.neural_network import MLPClassifier
    Xtr = np.array(Xtr, dtype=float)
    Ytr = np.array(Ytr, dtype=int)
    mlp = MLPClassifier(hidden_layer_sizes=(128, 128), max_iter=3000, random_state=0)
    mlp.fit(Xtr, Ytr)
    print("MLP entraîné (60 instances)")

    rows = []
    for s in range(SEED0 + 1000, SEED0 + 1000 + N_TEST):
        adj = make_graph(s)
        x = adj.flatten().reshape(1, -1)
        probas = mlp.predict_proba(x)
        p1 = probas.reshape(NV, KMAX)
        pred_oh = np.zeros((NV, KMAX), dtype=np.int8)
        for v in range(NV):
            pred_oh[v, int(np.argmax(p1[v]))] = 1
        kA, nA, tA, solA = solve_coloring(adj)
        kB, nB, tB, _ = solve_coloring(adj, hint=pred_oh)
        conflicts = sum(1 for v in range(NV) for u in range(v + 1, NV)
                        if adj[v, u] and int(np.argmax(pred_oh[v])) == int(np.argmax(pred_oh[u])))
        rows.append(dict(seed=s, kA=kA, k=kB, nA=nA, nB=nB,
                         tA=round(tA, 3), tB=round(tB, 3), hint_conflicts=conflicts))
    med = lambda key: float(np.median([r[key] for r in rows]))
    print(f"test  : medianes nA={med('nA'):.0f} nB={med('nB'):.0f} | "
          f"temps A={med('tA'):.3f}s B={med('tB'):.3f}s | conflits hint med={med('hint_conflicts'):.0f}")
    import csv
    with open(output_dir / "diving_results.csv", "w", newline="") as fh:
        w = csv.DictWriter(fh, fieldnames=list(rows[0]))
        w.writeheader()
        w.writerows(rows)


main(OUTPUT_DIR)
train : couleurs med=4, branches med=2742
MLP entraîné (60 instances)
test  : medianes nA=2829 nB=2325 | temps A=0.025s B=0.025s | conflits hint med=44

Lecture du résultat — le conseil gagne partout, et il gagne d’autant plus que la recherche est longue

La cellule précédente affiche les valeurs du run courant (lecture du CSV frais). Ce run est déterministe : les deux solveurs tournent en num_workers = 1, l’ordre de recherche ne dépend plus de l’entrelacement des threads. Il se rejoue à l’identique, et c’est lui que la section 5 commente.

Métrique Solveur pur (A) Solveur + hint (B) Lecture
Branches médiane 2829 2325 le hint réduit le cas moyen de ≈ 18 %
Branches max 3291 2752 la plus longue recherche en A n’est plus la plus longue en B
Instances améliorées — 25 / 25 aucune instance ne se dégrade sur ce run déterministe
Conflits du hint (médiane) — 44 / ~90 arêtes ≈ 49 % des arêtes prédites violent l’adjacence

Trois lectures mécanistes sortent de cette même table :

  1. Le gain est systématique, et il croît avec la dureté de l’instance. Sur toutes les 25 instances, le hint réduit le nombre de branches (gain relatif médian ≈ 15 %, de 8 % à 28 %) ; la corrélation entre le gain relatif et la recherche du solveur pur atteint 0,60. Les trois instances les plus longues en A (seeds 6004, 6005, 6008 : 3291, 3274, 3184 branches) atterrissent à 2363, 2595 et 2658 — la plus longue gagne 928 branches, soit ≈ 28 %. La distribution entière se décale vers la gauche, pas seulement la médiane.
  2. La reproductibilité est la contrepartie du choix num_workers = 1. Les tirages antérieurs de calibration parallélisaient (random_seed fixe la stratégie, pas l’entrelacement des threads) : les records de queue flottaient d’un run à l’autre. Le run committé ici est mono-thread et se reproduit à l’identique ; les valeurs absolues sont différentes de celles des tirages parallèles (2829 vs ≈ 790 pour la médiane du solveur pur) — la comparaison qui compte est interne au run (A vs B, mêmes seeds, même moteur), pas trans-run.
  3. Le conseil est sale, et il gagne quand même. ≈ 44 des ~90 arêtes prédites (≈ 49 %) portent un conflit — deux sommets adjacents prédits de la même couleur. CP-SAT passe donc une part de sa recherche à corriger un conseil qui viole les contraintes, au lieu d’en profiter pleinement. Le gain mesuré est un effet net : conseil corrigé compris. Une partie du potentiel du hint est gaspillée dans la réparation — mesurer l’effet d’un hint filtré (conflits retirés) est l’exercice de la section 6.
import pandas as pd
from pathlib import Path

df = pd.read_csv(OUTPUT_DIR / "diving_results.csv")
summary = pd.DataFrame({
    "mediane": df[["nA", "nB"]].median(),
    "max": df[["nA", "nB"]].max(),
    "moyenne": df[["nA", "nB"]].mean(),
})
print(summary.round(1))
print()
top = df.nlargest(3, "nA")[["seed", "nA", "nB", "hint_conflicts"]]
print("trois instances les plus dures en recherche pure (A) :")
print(top.to_string(index=False))
print()
print(f"arêtes medianes : {df['hint_conflicts'].median():.0f} conflits hint / ~90 arêtes"
      f" -> {100 * df['hint_conflicts'].median() / 90:.0f} %")
    mediane   max  moyenne
nA   2829.0  3291   2801.7
nB   2325.0  2752   2349.4

trois instances les plus dures en recherche pure (A) :
 seed   nA   nB  hint_conflicts
 6004 3291 2363              40
 6005 3274 2595              37
 6008 3184 2658              48

arêtes medianes : 44 conflits hint / ~90 arêtes -> 49 %

Exercice 1 — Le hint partiel top-k : garder l’effet sans le coût

L’hypothèse naturelle après la lecture : le hint complet force ~50 % d’arêtes conflictuelles ; un hint partiel ne fixe que les \(k\) sommets dont la prédiction est la plus confiante (\(\operatorname{argmax}_j p_{v,j}\) le plus élevé) et laisse CP-SAT libre ailleurs.

Consigne : compléter hint_top_k(p1, k) pour qu’il retourne une matrice one-hot (60, 6) avec les \(k\) sommets les plus confiants fixés, 0 partout ailleurs. Indice : trier les sommets par confiance décroissante, puis ne remplir que les \(k\) premiers ; tester ensuite k = 10 et k = 20 en substituant hint_top_k dans la boucle de mesure (cellule 4).

def hint_top_k(p1: np.ndarray, k: int | None = None) -> np.ndarray:
    # TODO étudiant : ne fixer que les k sommets les plus confiants (0 partout ailleurs).
    # Version de repli : hint complet (comportement mesure dans la section 4).
    pred = np.zeros_like(p1, dtype=np.int8)
    pred[np.arange(NV), np.argmax(p1, axis=1)] = 1
    return pred


print("Exercice à compléter : hint_top_k puis comparaison k=10 / k=20 / complet")
print("Repli (hint complet) : les conflits et la médiane de la section 4 se rejouent à l'identique")
Exercice à compléter : hint_top_k puis comparaison k=10 / k=20 / complet
Repli (hint complet) : les conflits et la médiane de la section 4 se rejouent à l'identique

Exercice 2 — Projection faisable : réconcilier le hint avec les contraintes

Si le conflit est la cause de la dégradation, projeter le hint sur l’ensemble des colorations propres devrait faire disparaître le coût : un hint sans conflit ne laisse à CP-SAT aucune correction à inventer.

Consigne : compléter project_faisable(pred_oh, adj) pour qu’il parcoure les arêtes en conflit et ré-affecte gloutonnement l’un des deux sommets vers une couleur libre à faible probabilité, jusqu’à zéro conflit. Vérifier ensuite dans la boucle de mesure que hint_conflicts tombe à 0 et relire les médianes — le hint projeté bat-il le hint brut ? le solveur pur ?

def project_faisable(pred_oh: np.ndarray, adj: np.ndarray) -> np.ndarray:
    # TODO étudiant : recoller gloutonnement les aretes en conflit jusqu'a 0 conflit.
    # Version de repli : hint inchange (conflits conserves, comportement mesure).
    return pred_oh.copy()


print("Exercice à compléter : project_faisable puis re-mesure des medianes")
Exercice à compléter : project_faisable puis re-mesure des medianes

Exercice 3 — Mesurer la variance, pas seulement la médiane

La section 4 oppose médiane et max. Mais le max ne résume pas la forme de la queue. La distribution des branches du solveur pur a une traîne lourde : combien d’instances dépassent 2× la médiane ? Et du côté hint, combien restent ?

Consigne : compléter queue_table(df) pour qu’il rende un DataFrame avec, pour chaque colonne nA et nB : médiane, écart-type, nombre d’instances > 2× la médiane. Lire la différence de dispersion — c’est la signature du diving.

def queue_table(df: pd.DataFrame) -> pd.DataFrame:
    # TODO étudiant : mediane, ecart-type, compte > 2x mediane pour nA et nB.
    return df[["nA", "nB"]].describe().T


print("Exercice à compléter : queue_table puis interpretation de la dispersion")
Exercice à compléter : queue_table puis interpretation de la dispersion

5. Bilan critique — ce que le diving prédit, ce que ce notebook mesure

Claim (article / folklore) Mesure de ce notebook Portée réelle
« Une solution partielle apprise accélère le solveur » médiane 2829 → 2325 branches (−18 %), 25/25 instances améliorées (run déterministe) Confirmé sur cette famille : le hint réduit la recherche partout ; la lecture « il coûte en moyenne » venait d’un artéfact de parallélisme (records flottants)
« Le diving évite les mauvaises décisions précoces » les trois instances les plus longues en A (3291, 3274, 3184) retombent à 2363, 2595, 2658 ; la plus longue gagne ≈ 28 % Confirmé : le gain relatif croît avec la dureté de l’instance (corrélation 0,60) ; la majorité des gros égarements disparaît
« Il suffit que le hint soit juste bit à bit » 44 des ~90 arêtes prédites en conflit (≈ 49 %) — et le hint gagne quand même Nuancé : un hint majoritairement conflictuel produit encore un gain net ; la précision par bit seule reste un mauvais prédicteur, mais la saleté du conseil ne suffit pas à le rendre inutile
« L’inférence ML gratuite » temps mur identiques (médianes ≈ 0,033 s / 0,031 s, inference amortie sur 3600 features) Vrai ici : le coût d’inférence du plongeur ne change pas l’équilibre à cette taille

Limites assumées : famille synthétique unique, 25 instances de test, hints conseils réparables (pas de fixation coercitive comme un vrai diving MIP qui branche par valeurs successives sur un sous-ensemble), solveur séquentiel (num_workers = 1 : reproductible, mais les valeurs absolues ne se comparent pas aux tirages parallèles antérieurs), fenêtre de temps courte. Le mécanisme mesuré (effet net d’un conseil sale, gain croissant avec la dureté) est indépendant de ces limites — c’est lui que l’on emporte comme leçon.

6. Pour aller plus loin et bibliographie

  • App-28 Learning to Branch (Hybrid) : l’autre moitié du geste Nair — la priorité de branchement apprise, auditée sur la même famille de questions (arbre × temps × coût d’inférence). La complémentarité des deux verdicts : aucune source d’amélioration locale ne se transforme en gain global sans mesure intégrée.
  • Exercices en extension : remplacer le MLP par un classifieur basé sur la structure (features de degré), ou entraîner le plongeur sur les conflits (régression du nombre de conflits).

Bibliographie :

  • Nair, V., Bartunov, S., Gimeno, F., et al. (2021). Solving Mixed Integer Programs Using Neural Networks. arXiv:2012.13349 (v3, juillet 2021). — gisement partagé : G:\Mon Drive\MyIA\IA\Bibliographie IA\Search\2021 - Nair et al - Solving Mixed Integer Programs Using Neural Networks.pdf.
  • Bengio, Y., Lodi, A., Prouvost, A. (2021). Machine Learning for Combinatorial Optimization: a Methodological Tour d’Horizon. EJOR 290(2).
  • Boussemart, F., Hemery, F., Lecoutre, C., Sais, L. (2004). Boosting Systematic Search by Weighting Constraints (dom/wdeg). ECAI.

(Toutes les publications sont archivées dans le gisement G:\Mon Drive\MyIA\IA\Bibliographie IA.)

Retour au sommet