Résoudre efficacement un système d'inégalités linéaires strictes avec tous les coefficients égaux à 1 sans utiliser un solveur LP général?

Par le titre, outre l'utilisation d'un solveur LP à usage général, existe-t-il une approche pour résoudre les systèmes d'inégalités sur les variables où les inégalités ont la forme ? Qu'en est-il du cas particulier des inégalités qui forment un ordre total sur les sommes des membres de l'ensemble de puissance de ? $x_i, \ldots, x_k$ $\sum_{i \in I} x_i < \sum_{j \in J} x_j$ $\{x_i, \ldots, x_k\}$

ds.algorithms linear-algebra linear-programming jonderry
la source

@Ankur: peu importe qu'il s'agisse d'entiers ou de réels. S'il s'agit d'inégalités strictes, vous pouvez les arrondir à des rationnels, puis les multiplier par le dénominateur le moins commun pour obtenir une solution entière.

Peter Shor

Je n'ai aucune idée de ce que vous pouvez coder en 30 minutes (dans quelle langue?). Si tel est le critère du «simple», est-ce vraiment une question d'informatique théorique?

Tsuyoshi Ito

Bon point Peter Shor. jonderry, je reprends ma déclaration. Je pensais que le problème combinatoire de la satisfaction de ces inégalités strictes et le problème analytique convexe de la recherche d'un point intérieur d'un cône sont qualitativement distincts. J'avais tort.

Ankur

@Tsuyoshi: Cela n'a pas besoin d'être trivial, mais je suis curieux de savoir si cela peut être fait à partir des premiers principes sans utiliser toute la puissance supplémentaire d'un solveur LP complet, en particulier pour le cas spécial dans lequel nous avons une commande de tous les sous-ensembles (notez dans ce cas que le temps polynomial est exponentiel dans le nombre de variables).

jonderry

Ensuite, je pense que "ce problème peut-il être résolu efficacement sans utiliser d'algorithmes généraux pour la programmation linéaire?" est un bon moyen de mieux formuler votre question.

Tsuyoshi Ito

Réponses:

Pour votre première question, sans l'ordre total, la réponse à votre question est qu'elle est essentiellement aussi difficile que la programmation linéaire. Voici un aperçu d'une preuve.

D'abord, établissons une variable , que nous appelons . Maintenant, choisissons une autre variable , que nous appellerons . Nous voulons nous assurer que Pour ce faire, considérez les inégalités etc. Avec une chaîne suffisamment longue, cela nous dira que , ou , pour un très grand ( est un nombre de Fibonacci, et croît donc de façon exponentielle en ). $x_1>0$ $\epsilon$ $x_i$ $1$

ϵ ≪ 1 .

$\epsilon \ll 1\, .$

x_{1} < x_{2},

$x_1 < x_2,$

x_{1} + x_{2} < x_{3},

$x_1 + x_2 < x_3,$

x_{2} + x_{3} < x_{4},

$x_2+x_3 < x_4,$

N x_{1} < x_{i}

$Nx_1 < x_i$

ϵ < 1 / N

$\epsilon < 1/N$

N

$N$

N

$N$

i

$i$

Nous pouvons maintenant fabriquer un programme linéaire avec des coefficients entiers. Si nous voulons un coefficient de 3 sur , nous ajoutons les inégalités et laissons reposer pour 3 . Si vous voulez des coefficients plus grands, vous pouvez les obtenir en exprimant les coefficients en notation binaire et en créant des inégalités qui garantissent que , , etc. Pour obtenir le côté droit, nous faisons de même avec la variable $x_t$

x_{t} < x_{t^{'}} < x_{t^{″}} < x_{t} + ϵ

$x_t < x_{t'} < x_{t''} < x_t + \epsilon$

x_{t} + x_{t^{'}} + x_{t^{″}}

$x_t + x_{t'} + x_{t''}$

x_{t}

$x_t$

x_{u} \approx 2 x_{t}

$x_u \approx 2x_t$

x_{v} \approx 2 x_{u}

$x_v \approx 2x_u$

x_{i} = 1

$x_i = 1$ . Cette technique nous permettra d'utiliser des programmes linéaires de la forme de l'OP pour vérifier approximativement la faisabilité de programmes linéaires arbitraires avec des coefficients entiers, une tâche qui est essentiellement aussi difficile que la programmation linéaire.

Je ne sais pas comment analyser la deuxième question, poser des questions sur le cas où il y a un ordre total sur tous les sous-ensembles.

Peter Shor
la source