Integral Column Generation for Set Partitioning Problems with Side Constraints
Pourquoi ce travail est dans la base
Une base qui oublie comment elle a trouvé un travail ne peut pas être vérifiée. Voici les voies qui ont admis celui-ci.
Notice bibliographique
Résumé
The integral column generation algorithm (ICG) was recently introduced to solve set partitioning problems involving a very large number of variables. This primal algorithm generates a sequence of integer solutions with decreasing costs, leading to an optimal or near-optimal solution. ICG combines the well-known column generation algorithm and a primal algorithm called the integral simplex using decomposition algorithm (ISUD). In this paper, we develop a generalized version of ICG, denoted I 2 CG, that can solve efficiently large-scale set partitioning problems with side constraints. This new algorithm can handle the side constraints in the reduced problem of ISUD, in its complementary problem, or in both components. Computational experiments on instances of the airline crew pairing problem (CPP) and the multidepot vehicle routing problem with time windows show that the latter strategy is the most efficient one and I 2 CG significantly outperforms basic variants of two popular column generation heuristics, namely, a restricted master heuristic and a diving heuristic. For the largest tested CPP instance with 1,761 constraints, I 2 CG can produce in less than one hour of computational time more than 500 integer solutions leading to an optimal or near-optimal solution. Summary of Contribution: In this paper, we develop a new integral column generation algorithm that can solve efficiently large-scale set partitioning problems with side constraints. The latter alter the quasi-integrality property needed for primal integral algorithms. The paper adds a methodological contribution remedying this issue. This remedy should, in our opinion, boost the use of primal exact methods, especially in the column generation context. The paper also has a computational contribution. Effectively, computational experiments on instances of the airline crew pairing problem and the multidepot vehicle routing problem with time windows are extensively discussed. We compare the proposed algorithm to basic variants of two popular column generation heuristics.
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.
Prédiction distillée sur la base complète
Imitation des enseignantsNi prévalence calibrée, ni vérité terrain. Validation humaine à venir. Apprise à partir de 10 348 étiquettes directes de Codex et de 10 348 étiquettes directes de Gemma. Le mode candidate est l'union des têtes enseignantes seuillées; le consensus est leur intersection. Ces sorties portent le statut machine_predicted_unvalidated et ne sont ni des étiquettes humaines ni des étiquettes directes de modèles de pointe.
Scores Codex et Gemma par catégorie
| Catégorie | Codex | Gemma |
|---|---|---|
| Métarecherche | 0,001 | 0,000 |
| Méta-épidémiologie (sens strict) | 0,000 | 0,000 |
| Méta-épidémiologie (sens large) | 0,000 | 0,000 |
| Bibliométrie | 0,000 | 0,000 |
| Études des sciences et des technologies | 0,001 | 0,000 |
| Communication savante | 0,000 | 0,000 |
| Science ouverte | 0,000 | 0,000 |
| Intégrité de la recherche | 0,000 | 0,001 |
| Charge utile insuffisante (le modèle a refusé de juger) | 0,000 | 0,000 |
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écoule