Algorithmes à temps exponentiel exact pour la programmation 0-1

10

Existe-t-il des algorithmes connus pour le problème suivant qui ont battu l'algorithme naïf?

Entrée: Un système de inégalités linéaires. $Ax \le b$ $m$

Résultat: une solution réalisable s'il en existe une. $x^*\in \{0,1 \}^n$

Supposons que et ont des entrées entières. Je m'intéresse au pire des cas. $A$ $b$

np-hardness integer-programming exp-time-algorithms Austin Buchanan
la source

14

Si est superlinéaire, un tel algorithme réfuterait l'hypothèse de temps exponentiel fort, car les formules sous forme normale conjonctive sont un cas particulier de programmation 0-1 et le lemme de sparsification nous permet de réduire -SAT en CNF-SAT sur de nombreuses clauses linéairement . $m$ $k$

Cependant, il existe un algorithme dû à Impagliazzo, Paturi et moi - même qui peut résoudre un tel système d'inégalités si le nombre de fils, c'est-à-dire le nombre de coefficients non nuls dans est linéaire. En particulier, si le nombre de fils est , l'algorithme s'exécute dans le temps , où $A$ $cn$ $2^{(1-s)n}$ . $s=\frac1{c^{O(c^2)}}$

Stefan Schneider
la source

1

Si est suffisamment petit, vous pouvez faire mieux que l'algorithme naïf, c'est-à-dire mieux que fois. Ici, «assez petit» signifie que est plus petit que quelque chose comme . Le temps d'exécution sera toujours exponentiel - par exemple, il pourrait être fois - mais il sera plus rapide que l'algorithme naïf. $m$ $2^n$ $m$ $n/\lg n$ $2^{n/2}$

Soit dit en passant, il semble que cela nous permette de résoudre le problème en un temps inférieur à dans certains cas où la matrice a un nombre d'entrées super-linéaire. Je ne sais pas comment concilier cela avec l'autre réponse fournie ici. Par conséquent, vous devriez vérifier attentivement ma réponse: cela pourrait indiquer que j'ai commis une grave erreur quelque part. $2^n$ $A$

L'approche de base: écrire , où contient les premiers composants de et contient les derniers composants; et de même , où a les colonnes gauche de et le droit $x=(x_0,x_1)$ $x_0$ $n/2$ $x$ $x_1$ $n/2$ $A=(A_0,A_1)$ $A_0$ $n/2$ $A$ $A_1$ colonnes. Maintenant, peut être réécrit sous la forme $n/2$ $Ax \le b$

A_{0} x_{0} + A_{1} x_{1} \leq b,

$A_0 x_0 + A_1 x_1 \le b,$

ou équivalent,

A_{0} x_{0} \leq b - A_{1} x_{1} .

$A_0 x_0 \le b - A_1 x_1.$

Énumérer toutes les possibilités pour et laisser désigner l'ensemble des valeurs possibles, c'est-à-dire $2^{n/2}$ $A_0 x_0$ $S$

S = {A_{0} x_{0} : x_{0} \in {0, 1}^{n / 2}} .

$S=\{A_0 x_0 : x_0 \in \{0,1\}^{n/2}\}.$

$T$ $2^{n/2}$ $b - A_1 x_1$

T = {b - A_{1} x_{1} : x_{1} \in {0, 1}^{n / 2}} .

$T = \{b - A_1 x_1 : x_1 \in \{0,1\}^{n/2}\}.$

Maintenant, le problème devient

$S,T \subseteq \mathbb{Z}^{m}$ $2^{n/2}$ $s\in S$ $t \in T$ $s\le t$

$\le$ $s_i \le t_i$ $i$

$O(2^{n/2} (n/2)^{m-1})$ $m$ $n/\lg n$ $2^n$

$m=1$ $m=1$ $x_i=1$ $A_{1,i}\le 0$ $x_i=0$ $x$

DW
la source

1

L'algorithme de ma réponse se réduit également au problème de vecteur décrit dans votre réponse en utilisant la même méthode, c'est-à-dire diviser les variables et lister toutes leurs affectations.

Stefan Schneider

2

2^{O (m)}

$2^{O(m)}$

Algorithmes à temps exponentiel exact pour la programmation 0-1

Réponses: