Solutions minimales maximales de LP

La programmation linéaire est, bien sûr, de nos jours très bien comprise. Nous avons beaucoup de travail qui caractérise la structure des solutions réalisables et la structure des solutions optimales. Nous avons la forte dualité, les algorithmes poly-temps, etc.

Mais que sait- on des solutions minimales maximales de LP? Ou, de manière équivalente, des solutions minimales maximales?

(Ce n'est pas vraiment une question de recherche, mais peut-être que nous pouvons avoir quelque chose de moins technique pour les vacances. Je suis juste curieux, et après quelques recherches sur Google, j'ai le sentiment que je dois manquer les bons mots clés. Cela semble évident. problème à étudier, mais je n'ai trouvé que quelques articles sporadiques qui mentionnent le problème.)

Pour garder les choses simples, concentrons-nous sur l' emballage et la couverture des LP . Dans un LP d'emballage nous donne un non-négatif matrice . Un vecteur est réalisable si et . Nous disons que est maximal s'il est réalisable et que nous ne pouvons augmenter goulûment aucun composant. Autrement dit, si et , alors n'est pas faisable. Et enfin, est une solution minimale maximale , si elle minimise la fonction objectif $A$ $x$ $x \ge 0$ $Ax \le 1$ $x$ $y \ge 0$ $y \ne 0$ $x + y$ $x$ $\sum_i x_i$ parmi toutes les solutions maximales.

(Vous pouvez définir une solution minimale maximale d'un LP couvrant d'une manière analogue.)

À quoi ressemble l'espace des solutions maximales minimales? Comment trouver de telles solutions? Est-il difficile de trouver de telles solutions? Comment pouvons-nous rapprocher ces solutions? Qui étudie de telles choses et quel est le bon terme pour cela?

Ces questions étaient à l'origine motivées par des ensembles dominants et des correspondances maximales minimales . Il est bien connu (et assez facile à voir) qu'une correspondance maximale minimale est un ensemble dominant de bord minimal; à l'inverse, étant donné un ensemble dominant de bord minimal, il est facile de construire une correspondance maximale minimale.

Ce sont donc essentiellement le même problème. Les deux problèmes sont NP-dur et APX-dur. Il existe un algorithme trivial à 2 approximations: toute correspondance maximale.

Cependant, leurs relaxations LP "naturelles" sont très différentes. Si vous prenez le problème d'ensemble dominant et formez une relaxation LP naturelle, vous obtenez un LP couvrant. Cependant, si vous prenez le problème de trouver une correspondance maximale minimale et essayez de trouver une relaxation LP, alors qu'obtenez-vous? Eh bien, bien sûr, les appariements fractionnaires sont des solutions réalisables d'un LP d'emballage; alors les correspondances fractionnelles maximales sont des solutions maximales de ces LPs, et les correspondances fractionnelles maximales minimales sont donc des solutions maximales minimales de ces LPs. :)

cc.complexity-theory ds.algorithms reference-request linear-programming optimization Jukka Suomela
la source

Votre définition du maximum comme «nous ne pouvons pas augmenter goulûment n'importe quel composant» ressemble beaucoup à Nash Equilibrium. Y a-t-il un lien caché avec la théorie des jeux ici?

Derrick Stolee

N'est-il pas vrai que pour chaque solution maximale dans l'exemple LP d'emballage, ?. Ensuite, nous recherchons essentiellement une solution minimale (dans -norm) de système d'équations linéaires.

x^{'}

$x'$

A x^{'} = 1

$Ax'=1$

L_{\infty}

$L_{\infty}$

Imran Rauf

@Imran: Non, je ne pense pas que ce soit correct. Une solution maximale (et une solution maximale) existe toujours, même si nous n'avons pas de solution pour .

A x = 1

$Ax = 1$

Jukka Suomela

Connaissez-vous les programmes linéaires de goulot d' étranglement , dans lesquels l'aspect minimax est tout dans la fonction objectif?

Mike Spivey

Maximalité et minimalité: Ce sont des types d'optimalité de Pareto.
Complexité: Je pense que trouver une solution minimale maximale est difficile à NP. Je réduirais le problème de domination de l'indépendance (alias le problème de jeu indépendant maximal minimal) dans les graphes bipartis. Ce problème (plus précisément sa version décisionnelle) est connu pour être NP-complet (DG Corneil et Y. Perl, Clustering and domination in perfect graphs. Discrete Applied Mathematics 9 (1984) 27-39). Puisqu'un graphe bipartite est parfait, son polytope d'ensemble indépendant est déterminé par les inégalités de clique, et le nombre de cliques dans un graphe bipartite est polynomial. Par conséquent, nous pouvons explicitement noter un système d'inégalités linéaires Ax <= 1, x> = 0 pour le polytope d'ensemble indépendant. Les solutions extrêmes correspondent aux ensembles indépendants, et les solutions extrêmes extrêmes correspondent aux ensembles indépendants maximaux.

Yoshio Okamoto
la source

Solutions minimales maximales de LP

Réponses: