Pourquoi le relâchement complémentaire est-il important?

Le relâchement complémentaire (CS) est couramment enseigné lorsque l'on parle de dualité. Il établit une belle relation entre la primale et la double contrainte / variables d'un point de vue mathématique.

Les deux principales raisons d'appliquer CS (comme enseigné dans les cours d'études supérieures et les manuels):

Pour vérifier l'optimalité du LP
Pour aider à résoudre le double

Compte tenu de la puissance de calcul actuelle et des algorithmes polynomiaux pour la résolution des LP, CS est-il toujours pertinent d'un point de vue pragmatique? Nous pourrions toujours résoudre les duels et aborder les deux points ci-dessus. Je suis d'accord pour dire qu'il est "plus efficace" de résoudre le double avec l'aide de CS mais est-ce bien cela? Ou y a-t-il plus à CS que ce que l'on voit? Où est exactement CS utile au-delà des deux points ci-dessus ? J'ai souvent vu des textes faisant allusion au concept de CS en parlant d'algorithmes d'approximation mais je n'arrive pas à comprendre son rôle là-bas.

ds.algorithms approximation-algorithms linear-programming primal-dual Doctorat
la source

Ce n'est pas mon domaine d'expertise, mais il semble que vous vous demandiez pourquoi nous enseignons les propriétés de X même si la décision de X est facile à calculer. Par exemple, pourquoi enseignons-nous la caractérisation "pas de cycles impairs = bipartite" de la bipartité alors que nous avons des algorithmes polynomiaux de temps pour vérifier la bipartité. C'est ce que vous demandez, dans un certain sens?

Robin Kothari

Pas exactement. Je comprends "pourquoi" vous l'enseignez. Je souhaite savoir à partir d'un POV pratique comment est-il utilisé lors de la résolution de LP et / ou de la conception d'algorithmes d'approximation. Quelle est la perception que nous obtenons autre que les relations mathématiques entre les variables et les contraintes.

PhD

Eh bien, je pense que cela peut aider à obtenir des solutions "analytiques" ... qui pourraient être plus difficiles à obtenir avec un ordinateur.

usul

Je ne "comprends" pas la question. Juste parce que nous utilisons des calculatrices et des ordinateurs pour ajouter et multiplier des nombres, avons-nous encore besoin de connaître les propriétés des nombres?

Chandra Chekuri

@ChandraChekuri - Je ne veux pas dire ça. J'essaie juste de comprendre ce qui est si génial avec ce théorème et ce qui le rend important. Je ne veux pas l'accepter comme "c'est comme ça" mais j'aimerais avoir une compréhension plus profonde de son importance par rapport à la dualité LP

PhD

La souplesse complémentaire est essentielle dans la conception d'algorithmes primal-dual. L'idée de base est:

Commencez avec une solution double réalisable . $y$
$x$ $(x, y)$
$x$ $y$

$s$ $t$ $s$ $t$

Les algorithmes primo-doubles sont agréables pour de nombreuses raisons. D'un point de vue philosophique, ils fournissent plus d'informations qu'un algorithme générique. Ils donnent généralement des algorithmes de temps fortement polynomiaux, alors que nous n'avons toujours pas de solveurs LP fortement polynomiaux. Ils sont souvent plus pratiques que les algorithmes génériques. Cela est particulièrement vrai si nous ne pouvons pas écrire explicitement le LP et notre seul autre choix est l'algorithme ellipsoïde, ce qui est le cas avec la correspondance non bipartite et l'algorithme primal-dual d'Edmonds.

$y$ $x$ $y$ $x_i > 0$ $y_j > 0$ $x$ $\alpha$ $\alpha$

Sasho Nikolov
la source

Pourquoi le relâchement complémentaire est-il important?

Réponses: