@mostajs/ro-pla

Auteur : Dr Hamid MADANI [email protected] · Licence : AGPL-3.0-or-later Statut : ⚠️ proposition / scaffold (0.0.1) — non implémenté, périmètre à valider.

Programmation linéaire & recherche opérationnelle (PL/RO) pour l'écosystème @mostajs/*. Modélise et résout des problèmes d'optimisation, de satisfaction de contraintes et de modélisation stochastique :

• Programmation linéaire (PL) : optimiser une fonction objectif linéaire sous contraintes linéaires (simplexe).
• Programmation en nombres entiers / mixte (PLNE/MIP) : variables entières, branch & bound.
• Décomposition de Dantzig-Wolfe : résolution de PL structurées à grande échelle (blocs + contraintes liantes) par génération de colonnes.
• Programmation par contraintes (CSP) : variables à domaines finis, contraintes (allDifferent, linéaires, table), propagation + backtracking.
• Chaînes de Markov : matrices de transition, distribution stationnaire, régime transitoire — base de la théorie des files d'attente (M/M/c) pour estimer attentes et dimensionner les guichets.
• Métaheuristiques (optimisation approchée de gros problèmes non linéaires / combinatoires) : algorithme génétique, recuit simulé, recherche tabou, essaims particulaires, colonies de fourmis.
• Apprentissage (modèles prédictifs / surrogates / contrôle) : réseaux de neurones (perceptron multicouche), et — proposé — apprentissage par renforcement pour les politiques d'affectation/ordonnancement.

Usages : affectation (tickets ↔ guichets, agents ↔ tâches), ordonnancement / planning, allocation de ressources (capacité, exclusion, précédence), dimensionnement et prévision d'attente (files M/M/c), prévision d'affluence (réseau de neurones sur l'historique des tickets).

⚠️ Note de conception : les réseaux de neurones / apprentissage relèvent d'un paradigme distinct (ML) de la RO exacte ; ils sont regroupés ici pour l'instant mais pourraient être extraits dans un module frère (@mostajs/ml) si le périmètre grossit. À trancher avant le 1.0.0.

Familles de méthodes (carte)

| Famille | Méthodes | Pour quoi | |---|---|---| | Exact — PL/PLNE | simplexe, branch & bound, branch & cut, Dantzig-Wolfe (génération de colonnes), Benders, relaxation lagrangienne | optimum prouvé, problèmes structurés | | Exact — combinatoire | CSP (propagation + backtracking), programmation dynamique, flots de réseau (max-flow, min-cost flow), Hongrois (affectation), plus courts chemins | affectation, routage, ordonnancement | | Métaheuristiques | génétique, recuit simulé, tabou, PSO, ACO, GRASP, NSGA-II (multi-objectif) | gros problèmes, bon « assez vite » | | Stochastique | chaînes de Markov, MDP, files M/M/c (Erlang), simulation à événements discrets, Monte-Carlo | incertitude, files, dimensionnement | | Apprentissage | réseaux de neurones (MLP), apprentissage par renforcement, optimisation bayésienne | prévision, politiques apprises |

Positionnement (vs @mostajs/rules)

@mostajs/rules évalue des conditions/gardes (inférence : « est-ce vrai ? »). @mostajs/ro-pla optimise / résout / modélise (« quelle solution satisfait les contraintes et optimise l'objectif ? », « quel est l'état stationnaire ? »). Responsabilités distinctes, complémentaires.

API envisagée (à figer en 0.1.0)

import { lp, model, markov } from "@mostajs/ro-pla";

// Programmation linéaire : maximiser 3x + 2y
const sol = lp()
  .maximize({ x: 3, y: 2 })
  .subjectTo([
    { x: 1, y: 1, "<=": 4 },
    { x: 1, y: 3, "<=": 6 },
  ])
  .solve();                        // { x, y, objective }

// CSP : affectation
const m = model();
const a = m.intVar("a", [1, 2, 3]);
const b = m.intVar("b", [1, 2, 3]);
m.allDifferent([a, b]);
const csp = m.solve();             // { assignment: { a, b } }

// Chaîne de Markov : distribution stationnaire
const chain = markov([
  [0.9, 0.1],
  [0.5, 0.5],
]);
const pi = chain.stationary();     // vecteur de probabilités stationnaires

Périmètre prévu

• 0.1.0 : PL (simplexe primal), CSP domaines finis (allDifferent, linéaires, table), propagation AC-3 + backtracking, chaînes de Markov (stationnaire, régime transitoire), solve / solveAll.
• 0.2.0 : PLNE/MIP (branch & bound), optimisation CSP, heuristiques (MRV/LCV), files M/M/c (formules d'Erlang), algorithme génétique + recuit simulé.
• 0.3.0 : réseaux de neurones (MLP : forward, rétropropagation), affectation par algorithme hongrois / flots de coût minimal.
• ≥ 0.4.0 : décomposition de Dantzig-Wolfe (génération de colonnes), recherche tabou / PSO, NSGA-II (multi-objectif), simulation à événements discrets, contraintes globales (cumulative/scheduling), dualité / sensibilité.

Reste à produire (DEVRULES §4 / §14)

Les 14 livrables (état de l'art — simplex.js, javascript-lp-solver, MiniZinc, OR-Tools, Choco ; théorie des files / Erlang —, audit, plan dev/test, llms.txt détaillé, CHANGELOG, doc technique, chapitre de livre…) sont à rédiger au démarrage. Ce dépôt ne contient que le squelette §5.