Algorithmes à temps exponentiel exact pour les programmes 0-1 avec des données non négatives

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

Entrée: matrice et vecteurs , où toutes les entrées de sont des entiers non négatifs.b , c A , b , $A$$b,c$$A,b,c$

Sortie: une solution optimale à . max { c T x : A x ≤ b , x ∈ { 0 , 1 } n$x^*$$\max \{ c^T x : Ax \le b, x \in \{ 0,1\}^n \}$

Cette question est une version raffinée de ma question précédente Algorithmes à temps exponentiel exact pour la programmation 0-1 .

si le nombre de coefficients non nuls dans $A$ est linéaire dans $n$ , il existe un algorithme qui résout ce problème en moins de $2^n$ temps.

Voici comment ça fonctionne. Nous utilisons la connexion standard entre un problème d'optimisation et son problème de décision correspondant. Pour tester s'il existe une solution où et , on va former un problème de décision: on va attacher la contrainte à la matrice , et tester s'il existe un tel que et . En particulier, nous formerons une nouvelle matrice en prenant et en ajoutant une ligne supplémentaire contenant , et nous formerons en prenantA x ≤ b c T x ≥ α c T x ≥ α A x A x ≤ b - c T x ≤ - α A ′ A - c T b ′ b - α x ∈ { 0 , 1 } n A ′ x ≤ b ′ α 2 n A ′ n A $x$$Ax\le b$$c^T x \ge \alpha$$c^T x\ge \alpha$$A$$x$$Ax \le b$$-c^T x \le -\alpha$$A'$$A$$-c^T$$b'$$b$et à côté d'une ligne supplémentaire avec . On obtient un problème de décision: existe-t-il tel que ? La réponse à ce problème de décision nous indique s'il existe une solution au problème d'optimisation d'origine de valeur ou supérieure. De plus, comme expliqué dans la réponse à votre question précédente , ce problème de décision peut être résolu en moins de temps, si le nombre de coefficients non nuls dans est linéaire dans (et donc si le nombre de non les coefficients nuls dans sont linéaires dans ). Maintenant, nous pouvons utiliser la recherche binaire sur$-\alpha$$x \in \{0,1\}^n$$A' x \le b'$$\alpha$$2^n$$A'$$n$$A$$n$2 $\alpha$pour résoudre votre problème d'optimisation en moins de temps.$2^n$

Mes remerciements à AustinBuchanan et Stefan Schneider pour avoir aidé à déboguer une version antérieure de cette réponse.

Si nous considérons le problème de minimisation , alors la réduction suivante montre qu'un algorithme fonctionnant dans le temps pour réfuterait le SETH. Une reformulation prouve le même résultat pour le problème visé (la version de maximisation).O ( 2 δ n / 2 ) δ < $\min_y \{c^T y : Ay \ge b, y \in \{ 0,1\}^n \}$$O(2^{\delta n/2})$$\delta <1$

Étant donné une instance de CNF-SAT avec des variables , une IP 0-1 avec deux variables pour chaque variable dans l'instance SAT. Comme d'habitude, la clause serait représentée comme . Ensuite, pour chaque variable dans l'instance SAT, ajoutez une contrainte . L'objectif est de minimiser . L'objectif de la IP sera ssi l'instance SAT est satisfaisable. { x j } n j = 1 y j , ¯ y j x j ( x 1 ∨ ¯ x 2 ∨ x 3 ) y 1 + ¯ y 2 + $\Phi = \wedge_{i=1}^m C_i$$\{x_j \}_{j=1}^n$$y_j, \overline{y}_j$$x_j$$(x_1 \vee \overline{x}_2 \vee x_3)$x j y j + ¯ y j ≥ 1 ∑ n j $y_1 + \overline{y}_2 + y_3 \ge 1$$x_j$$y_j + \overline{y}_j \ge 1$$\sum_{j=1}^n (y_j + \overline{y}_j)$$n$

Merci à Stefan Schneider pour la correction.

Mise à jour: dans On Problems as Hard as CNF-Sat, les auteurs supposent que SET COVER ne peut pas être résolu dans le temps , , où fait référence au nombre d'ensembles. Si vrai, cela montrerait que mon problème ne peut pas être résolu dans le temps également.δ < 1 n O ( 2 δ n$O(2^{\delta n})$$\delta <1$$n$$O(2^{\delta n})$

Mise à jour 2. Pour autant que je sache, en supposant que SETH, mon problème ne peut pas être résolu dans le temps , car il a été démontré que Hitting Set (avec un ensemble de base de taille ) ne peut pas être résolu. résolu dans le temps .n O ( 2 δ n$O(2^{\delta n})$$n$$O(2^{\delta n})$