Je me demandais s'il y a une bonne façon (de préférence à l'aide de saut) pour obtenir toutes les solutions optimales d'un programme linéaire (au cas où il existe plusieurs solutions optimales).
Exemple P>
minimiser la distance statistique (distance de Kolmogorov) entre deux probabilités Distributions. P>
Q1 = [0.75,0,0,0.25] Q2 = [0.25,0,0,0.75]
3 Réponses :
Je ne sais pas sur Julia, mais il y a un outil appelé ppl que vous pouvez utiliser Pour déterminer tous les sommets de la solution polyédron après avoir résolu le programme linéaire.
Voir ma réponse ici à une question similaire: Trouver toutes les solutions de base alternatives à l'aide de linéaires existants Outil de programmation .
Les solveurs LP ne sont pas conçus pour énumérer toutes les solutions optimales. Une fois que vous connaissez la valeur d'objectif optimale, vous pouvez définir le polyèdre contenant toutes les solutions optimales, puis utiliser un algorithme de dénombrement de sommet pour collecter le très grand ensemble de points extrêmes de ce polyèdre. Toutes les solutions optimales sont des combinaisons convexes de ces points extrêmes. De Julia, vous pouvez utiliser le wrapper pour CDD .
Vous connaissez-vous un exemple de travail minimal de PolyHEDRA.JL + CDD? Je ne trouve rien sur la façon d'utiliser PolyHedra dans les documents.
Je recommande d'ouvrir un problème sur le référentiel correspondant.
Il existe un moyen intéressant d'énumérer toutes les solutions LP optimales possibles (ou plutôt toutes les bases LP optimales) à l'aide d'un solveur MIP standard. Fondamentalement, l'algorithme est la suivante: pour un exemple, voir ici .
Merci! Nous allons essayer cette approche :) semble très simple, curieux combien de bfs nous trouverons!
Maintenant que j'essaie de mettre en œuvre un tel système, je ne suis pas tout à fait sûr si je reçois tout ce que vous dites; Devons-nous assumer que nos solutions sont des solutions intestinales 0-1? Ou utilisons-nous des entiers 0-1 pour garder une trace des points de base réalisables que nous connaissons déjà?
Qu'est-ce qui vous conduit à croire que les valeurs de solution pour X ne peuvent être que 0-1?
Ce n'est pas ce que je crois. Cependant, on m'a conduit à croire que cela devrait être en quelque sorte le cas lorsque vous regardez
Dans le cas simple, je peux assumer mes variables Q [i] sont 0-1 sur les points extrêmes, je peux donner ces informations à mon solveur. Dans ce cas, les coupes que vous avez proposées: Sum_ {i s.t. connus de [i] = 1} Q [i} <= n - 1, travaillez comme un charme. Dans le cas où 0 <= q [i] <= 1 sur les points extrêmes, il n'est pas clair pour moi quelles coupes à faire, pour trouver tous les points extrêmes. Intuitivement, la coupe devrait passer par un autre point extrême, pour vous assurer que nous n'avons pas une solution sur un sommet entre les points extrêmes.
Je pense que vous avez totalement manqué tout le point sur cet algorithme. Les variables x sont continues. Les variables bêta (utilisées pour coder le statut de base) sont binaires. Nous utilisons des coupes sur les variables de base bêta.
Vous pouvez probablement résoudre le LP, puis essayer de maximiser le coefficient de Bhattacharyyya compte tenu de la valeur de fonction objective de la LP que vous avez résolue. Même si vous avez toutes les solutions optimales (sommets), il n'est pas clair comment vous allez trouver les faces optimales du polyèdre sous-jacent et comment vous allez effectuer la recherche (sur ces visages) afin de maximiser le coefficient de Bhattacharyyyya. Si la solution optimale est "au milieu", ce qui peut se produire car la fonction est concave, les sommets optimaux eux-mêmes ont peu d'usage.
J'ai essayé de modifier la question directement, mais apparemment je ne peux pas; Dans votre programme linéaire, la valeur absolue doit être décomposée pour chaque terme de la fonction objectif, c'est-à-dire
min somme a [i] sous réserve deA [i]> = p [i] - Q [i] eta [i]> = q [i] - p [i] - p [i] pour chaque1 <= iJ'ai réparé l'erreur, merci ;-)
Notez qu'il peut y avoir un grand nombre de sommets: par exemple, le klee-minty cube est un d x d lp avec des sommets 2 ^ D. Cependant, je ne sais pas combien de personnes peuvent avoir le même c. X .