Environnement de programmation en nombres entiers
Résolvez un petit programme linéaire en nombres entiers par séparation et évaluation exactes, et consultez chaque nœud de recherche. Le meilleur point n'est déclaré optimal que lorsque tout l'arbre a été exploré.
Les programmes sont limités à 4 000 caractères et 40 lignes, 8 variables et 8 contraintes portant sur au moins deux variables ; la limite de nœuds va de 1 à 5 000 et la recherche s'arrête aussi après 3 000 000 d'étapes arithmétiques exactes. Tous les calculs sont effectués sur votre appareil dans un processus d'arrière-plan limité à 15 secondes. Téléchargements : rapport JSON et CSV des nœuds. Première ligne : maximize ou minimize, puis la fonction objectif. Ensuite, une contrainte par ligne. Jusqu’à 4 000 caractères. Vérifiez les réglages avant de lancer le traitement.
Votre résultat
Environnement de programmation en nombres entiers
- Écrivez l'objectif sur la première ligne, par exemple maximize 5x + 4y.
- Ajoutez une contrainte par ligne, des bornes telles que x, y >= 0 et, éventuellement, des lignes comme integer x ou binary z.
- Définissez la limite de nœuds et lancez la recherche.
- Consultez le statut, la meilleure solution courante, la meilleure borne et l'écart, puis téléchargez le rapport JSON ou le CSV des nœuds.
À savoir
Les programmes sont limités à 4 000 caractères et 40 lignes, 8 variables et 8 contraintes portant sur au moins deux variables ; la limite de nœuds va de 1 à 5 000 et la recherche s'arrête aussi après 3 000 000 d'étapes arithmétiques exactes. Tous les calculs sont effectués sur votre appareil dans un processus d'arrière-plan limité à 15 secondes. Téléchargements : rapport JSON et CSV des nœuds.
Séparation et évaluation
Chaque nœud résout exactement la relaxation linéaire par la méthode du simplexe. Une variable entière fractionnaire est divisée en deux branches, x <= floor et x >= ceiling. Les nœuds sont élagués si leur relaxation est irréalisable ou ne peut pas améliorer le meilleur point entier trouvé. Méthode : Wolsey, Integer Programming, 2e édition, chapitre 7 (2020).
Signification de « démontré »
Lorsque chaque nœud a été résolu ou élagué à l'aide d'une borne exacte, la meilleure solution courante est démontrée optimale ou le problème est démontré irréalisable. Si la limite de nœuds ou le budget d'étapes interrompt d'abord la recherche, cette solution reste seulement le meilleur point trouvé jusqu'ici ; le rapport indique la meilleure borne et l'écart entre les deux.
Règles de saisie
Les variables sont entières, sauf celles indiquées par integer x, y ; les autres sont alors continues. Les contraintes portant sur une seule variable deviennent des bornes. Une relaxation non bornée interrompt la recherche, car le programme entier peut alors être non borné ou irréalisable.