Contre-expertiser une garantie d'approximation en salle de test
Aperçu
En quoi consiste ce défi.
Formalisez un problème d'affectation, testez une garantie d'approximation, implémentez un arrondi linéaire et obtenez un certificat vérifiable.
Le brief
Ce que vous ferez, et ce que vous démontrerez.
La garantie « à moins de 5 pour cent de l'optimum » attribuée à l'heuristique gloutonne est-elle démontrable, et quelle borne peut-on honnêtement affirmer à sa place avant d'engager l'investissement ?
Earning criteria — what you'll demonstrate
- Passer d'une description industrielle à une formulation en programmation linéaire en nombres entiers, puis à sa relaxation, en justifiant chaque variable et chaque contrainte
- Utiliser la dualité et la valeur de la relaxation comme borne inférieure certifiée plutôt que comme simple heuristique de comparaison
- Distinguer une garantie d'approximation au sens du pire cas d'une performance empirique moyenne, et construire une instance adverse pour le démontrer
- Concevoir et évaluer un algorithme d'approximation par arrondi de la solution fractionnaire, en analysant son facteur de garantie
- Communiquer une incertitude algorithmique à une direction industrielle sans la dissoudre en un chiffre unique rassurant
Adéquation au programme
Où cela s'inscrit dans votre cursus.
Renforce les mêmes compétences que celles attendues par votre diplôme.
Cursus associés bientôt disponibles.
Compétences
Les compétences que vous démontrerez.
Chacune apparaît sur votre certificat vérifié.
Débouchés
Les métiers auxquels ce défi vous prépare.
De vrais intitulés. De vraies passerelles de compétences. Choisissez celui qui se rapproche le plus de votre trajectoire.
Les parcours de carrière que ce défi construit
Métiers de référenceConsultant en Recherche Opérationnelle
Contre-expertiser le livrable d'un autre cabinet, reformuler le problème et produire une borne défendable est exactement ce que fait un consultant en recherche opérationnelle sur un dossier industriel contesté.
Ce défi renforce
- linear-programming-duality
- approximation-algorithms
- analytical-reasoning
Analyste de Décision
Vous transformez une incertitude algorithmique en information de décision utilisable pour un investissement de plusieurs millions d'euros, en séparant explicitement le démontré de l'observé.
Ce défi renforce
- analytical-reasoning
- 6-pager-writing
- algorithm-analysis
Analyste en Recherche Opérationnelle
Le défi couvre le cœur du métier : modéliser un atelier en programmation linéaire, résoudre la relaxation, arrondir, puis mesurer et communiquer l'écart obtenu sur des instances réelles anonymisées.
Ce défi renforce
- linear-programming-duality
- algorithm-analysis
- approximation-algorithms
Chercheur en Apprentissage Automatique
La discipline exercée ici — refuser une affirmation de performance non démontrée, construire un contre-exemple, distinguer garantie de pire cas et moyenne empirique — est la compétence de fond attendue d'un profil de recherche.
Ce défi renforce
- approximation-algorithms
- ai-assisted-research-synthesis
- analytical-reasoning