Fast Continuous and Integer L-Shaped Heuristics Through Supervised Learning
Notice bibliographique
Résumé
We propose a methodology at the nexus of operations research and machine learning (ML) leveraging generic approximators available from ML to accelerate the solution of mixed-integer linear two-stage stochastic programs. We aim at solving problems where the second stage is demanding. Our core idea is to gain large reductions in online solution time, while incurring small reductions in first-stage solution accuracy by substituting the exact second-stage solutions with fast, yet accurate, supervised ML predictions. This upfront investment in ML would be justified when similar problems are solved repeatedly over time—for example, in transport planning related to fleet management, routing, and container yard management. Our numerical results focus on the problem class seminally addressed with the integer and continuous L-shaped cuts. Our extensive empirical analysis is grounded in standardized families of problems derived from stochastic server location (SSLP) and stochastic multi-knapsack (SMKP) problems available in the literature. The proposed method can solve the hardest instances of SSLP in less than 9% of the time it takes the state-of-the-art exact method, and in the case of SMKP, the same figure is 20%. Average optimality gaps are, in most cases, less than 0.1%. History: Accepted by Alice Smith, Area Editor (for this paper) for Design and Analysis of Algorithms–Discrete. Funding: Financial support from the Institut de Valorisation des Données (IVADO) Fundamental Research Project Grants [project entitled “Machine Learning for (Discrete) Optimization”]; Canada Research Chairs; the Natural Sciences and Engineering Research Council of Canada [Collaborative Research and Development Grant CRD-477938-14]; and the Canadian National Railway Company Chair in Optimization of Railway Operations at Université de Montréal is gratefully acknowledged. E. Frejinger holds a Canada Research Chair. Computations were made on the supercomputer Béluga, managed by Calcul Québec and Digital Research Alliance of Canada. The operation of this supercomputer is funded by the Canada Foundation for Innovation; the Ministère de l’Économie, de la Science et de l’Innovation du Québec; and the Fonds de Recherche du Québec – Nature et Technologies.
Récupéré en direct depuis OpenAlex et désinversé. Les résumés ne sont pas conservés dans cette base de données : les index inversés représentent 8,6 Go des 9,3 Go de texte de la base, et le serveur dispose de 13 Go libres.
Comment cette classification a été obtenuedéplier
Prédiction machine sur la base complète
Imitation des enseignantsNi prévalence calibrée, ni vérité terrain. Validation humaine à venir. Le volet Gemma est une étiquette directe du modèle pour chaque travail de la base, lue sur la notice réduite au titre. Le volet Codex est un classifieur appris des 10 348 étiquettes directes de Codex et calibré sur les taux pondérés de l'échantillon; les champs sans appui suffisant ne portent aucun appel Codex. Le mode candidate est l'union des deux volets; le consensus est leur intersection. Ces sorties portent le statut machine_predicted_unvalidated et ne sont pas des étiquettes humaines.
Scores du classifieur distillé par catégorie (deux têtes)
| Catégorie | Codex | Gemma |
|---|---|---|
| Métarecherche | 0,003 | 0,012 |
| Méta-épidémiologie (sens strict) | 0,001 | 0,001 |
| Méta-épidémiologie (sens large) | 0,002 | 0,001 |
| Bibliométrie | 0,001 | 0,001 |
| Études des sciences et des technologies | 0,001 | 0,002 |
| Communication savante | 0,002 | 0,002 |
| Science ouverte | 0,003 | 0,002 |
| Intégrité de la recherche | 0,002 | 0,003 |
| Charge utile insuffisante (le modèle a refusé de juger) | 0,004 | 0,001 |
Scores machine (provisoires)
Les deux têtes enseignantes du modèle étudiant, lues sur ce travail. Un score ordonne la base pour la relecture; il n'affirme jamais une catégorie, et le statut de validation accompagne chaque rangée tel quel.
Scores de référence d'un modèle non mature (critères de maturité non atteints, 7 itérations). Un score ordonne; il n'affirme jamais une catégorie.
score_only:v0-immature-baseline · tel quel depuis la passe de notation : score_only signifie que le nombre peut ordonner les travaux, et qu'aucune étiquette de catégorie n'en découleClassification
machine, non validéePrédiction automatique; un appel candidat d’une seule source (Gemma direct ou Codex distillé), pas un consensus.
Le détail, modèle par modèle et score par score, se trouve en fin de page sous « Comment cette classification a été obtenue ».