human
Quand les diagrammes de décision sont-ils la bonne façon de modéliser et résoudre un problème
gpt
Les diagrammes de décision (DD) sont les plus efficaces lorsqu'ils peuvent représenter de manière compacte un ensemble important (voire exponentiel) de solutions. Cela est réalisé en fusionnant les états équivalents dans chaque couche. Pour rendre les diagrammes de décision évolutifs, nous pouvons utiliser des diagrammes de décision relaxés qui permettent de fusionner des nœuds qui ne sont pas nécessairement équivalents. Les diagrammes de décision relaxés fournissent des bornes duales sur la fonction objectif - une largeur plus grande peut produire une borne plus forte.
La relation entre la taille du diagramme de décision et la structure combinatoire sous-jacente du problème est bien étudiée dans la littérature informatique ; voir par exemple le manuel de Wegener. La caractéristique la plus importante qui influence la taille est l'ordre des variables. Nous pouvons utiliser cela pour établir quelques lignes directrices générales sur quand un DD peut réussir pour l'optimisation combinatoire :

* Le problème a une structure séquentielle, et les décisions pour l'étape $i$ dépendent uniquement des décisions prises aux étapes $i-k$ à $i-1$, pour un petit $k$.
* La largeur induite du graphe de contrainte du problème est petite.
* Pour un modèle MIP, la matrice de contrainte a une petite largeur de bande.
* Pour les problèmes de type sac à dos, le 'budget' maximum est relativement petit.

Notez que dans certains des cas ci-dessus, une caractérisation précise de 'petit' peut donner des bornes (pseudo-)polynomiales sur la taille du DD exact. En pratique, les DD relaxés auront toujours une taille polynomiale.
Il existe plusieurs domaines d'optimisation combinatoire dans lesquels les diagrammes de décision ont été appliqués avec succès :

* Problèmes de séquencement et de routage. Par exemple, l'ordonnancement sur une seule machine avec des temps de configuration, des fenêtres de temps et/ou des contraintes de précédence, qui peut également être appliqué aux problèmes de voyageur de commerce contraints. Une représentation similaire de diagramme de décision a été utilisée par Grubhub pour résoudre des problèmes de ramassage et de livraison.
* Décomposition et intégration dans les modèles MIP. Les diagrammes de décision ont été utilisés pour représenter des sous-problèmes dans des modèles MIP qui sont autrement difficiles à linéariser. Par exemple, pour représenter des fonctions objectif non linéaires, des plannings d'employés contraints ou la conception de circuits non linéaires. Les DD ont également été utilisés dans la génération de colonnes.
* Problèmes de théorie des graphes. Les exemples incluent la couverture d'ensemble, l'ensemble indépendant maximum et la coupe maximale.
* Programmation par contraintes. La propagation de contraintes basée sur les diagrammes de décision (relaxés) peut être beaucoup plus efficace que la propagation des domaines de variables individuelles. Cela a été démontré pour la première fois sur des contraintes alldifferent chevauchantes.