Applications de de la programmation en nombres entiers et la décomposition aux problèmes d'ordonnancement : le problème de la planification stratégique des mines et le problème de bin packing avec délais
Bibliographic record
Abstract
Dans les problèmes de planification, l'objectif est d'attribuer des plages horaires à un ensemble d'activités. Dans ces problèmes, il existe généralement des contraintes de précédence entre les activités qui dictent l'ordre dans lequel elles peuvent être exécutées et des contraintes de ressources qui limitent le nombre d'activités pouvant être exécutées simultanément. Dans cette thèse, nous développons des méthodologies de programmation en nombres entiers, basées sur des méthodes de décomposition, pour deux classes très différentes de problèmes d'ordonnancement. Il s'agit du problème de planification stratégique des mines à ciel ouvert (SOPMP) et du problème de bin packing avec délais (BPPTL).Etant donné une représentation discrétisée d'un gisement appelé modèle de bloc, le SOPMP que nous considérons consiste à définir les blocs à extraire, quand les extraire, comment ou s'il faut les traiter, de manière à respecter les contraintes opérationnelles et maximiser la valeur actualisée nette. Ces problèmes sont connus pour être difficiles en raison de l'ampleur des problèmes réels de planification minière. Ils sont également importants dans l'industrie minière. Chaque grande opération minière dans le monde doit résoudre ce problème au moins une fois par an.Dans le chapitre 2, nous commençons par étudier un algorithme lagrangien développé par Dan Bienstock et Mark Zuckerberg (qu'on appellera algorithme BZ) en 2009 pour résoudre la relaxation LP de grandes instances de SOPMP. Dans cette étude, nous généralisons les classes de problèmes qui peuvent être résolus avec l'algorithme BZ, et montrons qu'il peut être exprimé comme un algorithme de génération de colonnes. Nous prouvons, pour les classes générales de problèmes de programmation en nombres entiers mixtes, que la relaxation BZ fournit une borne qui se situe entre la relaxation LP et les bornes de Dantzig-Wolfe. Nous développons en outre des accélérations de calcul qui améliorent les performances de l'algorithme BZ dans la pratique.Dans le chapitre 3, nous traitons le problème du calcul d'une solution entière réalisable pour SOPMP. En utilisant l'algorithme BZ développé au chapitre 2, nous développons des heuristiques pour ce problème. En outre, nous développons des algorithmes de prétraitement qui réduisent la taille du problème et intégrons l'algorithme BZ dans un algorithme de branch-and-cut qui utilise deux nouvelles classes de plans sécants. En comparant la valeur de l'heuristique à la borne de relaxation LP, l'écart moyen calculé est proche de 10%. Cependant, lors de l'application des techniques de prétraitement et des plans sécants, il se réduit à 1,5% au nœud racine. Quatre heures de branchement réduisent encore ce pourcentage à 0,6%.Le chapitre 4 présente le BPPTL. Il s'agit d'une généralisation du problème de bin packing, dans lequel les containers doivent être affectés à des créneaux horaires qui respectent des contraintes de délai entre les articles. Deux formulations de programmation en nombres entiers sont proposées : une formulation compacte qui modélise exactement le problème, et une formulation étendue qui modélise une relaxation. Pour deux cas particuliers du problème, le cas avec un nombre illimité de bin par période et le cas avec un bin par période et des délais non négatifs, nous renforçons la formulation étendue avec une famille spéciale de contraintes. Nous proposons un algorithme de branch-and-cut-and-price (BCP) pour résoudre cette formulation, avec séparation des solutions entières et fractionnaires, et une heuristique de strong diving. Les expérimentations confirment que l'algorithme BCP est plus performant que la résolution de la formulation compacte avec un solveur commercial. En utilisant cette approche, nous avons pu résoudre de manière optimale 70% d'une classe d'instances précédemment ouvertes de ce problème.
Fetched live from OpenAlex and de-inverted. Abstracts are not stored in this database: the inverted indexes are 8.6 GB of the frame’s 9.3 GB of text, and the host has 13 GB free.
How this classification was reachedexpand
Full frame distilled prediction
Teacher imitationNot calibrated prevalence, not ground truth. Human validation pending. Learned from the 10,348 direct Codex labels and 10,348 direct Gemma labels. Candidate is the union of thresholded teacher heads; consensus is their intersection. These outputs are machine_predicted_unvalidated and are not human labels or direct frontier model labels.
Codex and Gemma teacher scores by category
| Category | Codex | Gemma |
|---|---|---|
| Metaresearch | 0.002 | 0.000 |
| Meta-epidemiology (narrow) | 0.000 | 0.001 |
| Meta-epidemiology (broad) | 0.000 | 0.000 |
| Bibliometrics | 0.000 | 0.000 |
| Science and technology studies | 0.000 | 0.000 |
| Scholarly communication | 0.001 | 0.000 |
| Open science | 0.000 | 0.000 |
| Research integrity | 0.001 | 0.001 |
| Insufficient payload (model declined to judge) | 0.000 | 0.000 |
Machine scores (provisional)
The two teacher heads of the student model, read on this work. A score orders the frame for review; it never asserts a category, and the validation status ships verbatim with every row.
Baseline scores from an immature model (maturity gate not passed, 7 training rounds). Scores rank; they never assert a category.
score_only:v0-immature-baseline · verbatim from the scoring run: score_only means the number may rank works, and no category label ships from itClassification
machine, unvalidatedMachine predicted; a candidate call from one teacher head, not a consensus.
How this classification was reached, model by model and score by score, is at the end of the page under "How this classification was reached".