Trouver un plan de coupe qui divise un polyèdre uniformément

Disons que nous avons un polyèdre sous forme standard:

\begin{aligned} A x = b \\ x \geq 0 \end{aligned}

$\begin{equation*} \begin{array}{rl} \mathbf{A}\mathbf{x} = \mathbf{b} \\\\ \mathbf{x} \ge 0 \end{array} \end{equation*}$

Existe-t-il des méthodes connues pour trouver un hyperplan qui divise le polyèdre de manière à ce que le nombre de sommets de chaque côté de l'hyperplan soit approximativement le même? (c'est-à-dire un algorithme qui minimise la différence absolue des cardinalités des sommets des deux côtés de la division). $\mathbf{d} \mathbf{x} +d_0= 0$

Existe-t-il également des résultats connus concernant la complexité de ce problème?

Addendum: restreindre les types de coupes:

Voici une variante du problème d'origine dans l'espoir qu'il soit plus facile à résoudre que l'original:

Existe-t-il un moyen de calculer ou d'estimer efficacement pour quelle coordonnée un hyperplan de la forme produirait la plus faible différence absolue de cardinalités de sommets des deux côtés de la division? Par efficace, je veux dire quelque chose de plus efficace que l'énumération exhaustive des cardinalités des sommets pour toutes ces divisions possibles. $i$ $d_ix_i + d_0 = 0$

Remarque: Après quelques jours de petits progrès, j'ai également posté cette question sur MathOverflow .

ds.algorithms linear-programming linear-algebra Amelio Vazquez-Reina
la source

Ne devrait-on pas être en mesure de prouver qu'il s'agit d'un problème NP-difficile?

Peter Shor, le

Merci @Peter. Une preuve serait formidable. Cela dit, je suppose que le problème est difficile et je pense que je suis plus intéressé par l'heuristique ou les algorithmes d'approximation. La motivation derrière l'idée de restreindre les types de coupes était en partie de voir s'il existe des variantes plus faciles du problème général pour lesquelles nous connaissons déjà une solution ou un algorithme d'approximation.

Amelio Vazquez-Reina

Que diriez-vous de quelque chose dans ce sens (je ne sais pas si cela fonctionne) - Nous savons que compter le nombre de correspondances bipartites maximales est difficile. Nous savons également qu'un programme linéaire pour trouver une correspondance bipartite maximale est totalement unimodulaire et donc tout point d'angle / solution de base réalisable est intégral. Pour un problème de correspondance bipartite maximale, recherchez la valeur de la correspondance. Construisez un programme linéaire avec la contrainte que toute solution doit avoir la valeur optimale. Ensuite, chaque point d'angle est une correspondance. Le fait de pouvoir se diviser à plusieurs reprises de manière égale signifie que vous devriez pouvoir compter le nombre de correspondances.

Opt

Ça ne fait rien. Il faudrait également pouvoir compter le nombre de sommets ajoutés par le plan de coupe.

Opt

Je ne me souviens pas de la façon analytique de le faire!

Mais c'est un problème classique pour la programmation génétique! Si vous le connaissez, vous pouvez utiliser un vecteur normalisé au centre du polyèdre qui décrit le plan de coupe.

Votre population est donc un ensemble de vecteurs normalisés [x, y, z, ...] et comme fonction d'ajustement, vous utilisez la différence entre les 2 volumes divisés!

Donc, si la différence tend vers zéro, plus "d'ajustement" est votre vecteur / avion!

eduardo pons
la source

Désolé, pourriez-vous répéter cela sans utiliser de langage de programmation génétique? Qu'est-ce qu'une "population"? Qu'est-ce qu'une "fonction d'ajustement"?

Jeffε

Trouver un plan de coupe qui divise un polyèdre uniformément

Addendum: restreindre les types de coupes:

Réponses: