0-1 Programmation linéaire: calcul de la formulation optimale

Considérons l' espace à $n$ dimensions $\{0,1\}^n$ , et soit $c$ une contrainte linéaire de la forme $a_1x_1 + a_2x_2 + a_3x_3 +\ ...\ + a_{n-1}x_{n-1} + a_nx_n \geq k$ , où $a_i \in \mathbb{R}$ , et k ∈ R .$x_i \in \{0,1\}$$k \in \mathbb{R}$

Clairement, a pour effet de diviser { 0 , 1 } n en deux sous-ensembles S c et S ¬ c . S c contient tous et seulement les points satisfaisant c , tandis que S ¬ c contient tous et seulement les points falsifiant c .$c$$\{0,1\}^n$$S_c$$S_{\lnot c}$$S_c$$c$$S_{\lnot c}$$c$

Supposons que . Maintenant, soit O un sous-ensemble de S c tel que les trois énoncés suivants soient valables:$|S_c| \geq n$$O$$S_c$

1. contient exactement n points.$O$$n$
2. Ces points sont linéairement indépendants.$n$
3. Ces points sont ceux à distance minimale de l'hyperplan représenté par c . Plus précisément, soit d ( x , c ) la distance d'un point x ∈ { 0 , 1 } n à l'hyperplan c . Alors, ∀ B ⊆ S c tel que B vérifie 1 et 2 c'est le cas que ∑ x ∈ B d ( x , c ) ≥ ∑ x ∈ O$n$$c$$d( x, c )$$x \in \{0,1\}^n$$c$$\forall B \subseteq S_c$$B$ . Autrement dit O est, parmi tous les sous-ensembles de S c satisfaisant à la fois aux conditions 1 et 2, celui qui minimise la somme des distances de ses points à l'hyperplan c .$\sum_{x \in B} d(x, c) \geq \sum_{x \in O} d(x, c)$$O$$S_c$$c$

Des questions

1. Étant donné , est-il possible de calculer O efficacement? $c$$O$
2. Quel est l'algorithme le plus connu pour le calculer?

$\ $

Exemple avec $n = 3$

, O = { ( 0 , 0 , 1 ) , ( 1 , 1 , 1 ) , ( 1 , 0 , 0 ) } .$S_{\lnot c} = \{ ( 1, 0, 1 ) \}$$O = \{ ( 0, 0, 1 ), ( 1, 1, 1 ), ( 1, 0, 0 ) \}$

$\ $

Mise à jour 05/12/2012

Motivation

La motivation est que l' utilisation de , il devrait être possible de déterminer la contrainte optimale c * , comme cela devrait être le hyperplan défini par les n points dans O . $O$$c^*$$n$$O$

La contrainte optimale est celle qui conduit au polytope optimal P ∗ .$c^*$$P^*$

Le polytope optimal est celui dont les sommets sont tous et seulement les sommets entiers du polytope P initial (un sommet entier est un sommet dont les coordonnées sont toutes entières).$P^*$$P$

Le processus peut être itéré pour chaque contrainte d'une instance I de 0-1 L P , en remplaçant à chaque fois c par sa contrainte optimale correspondante c ∗ . A la fin, cela conduira à polytope optimale P * de I . Puis, comme les sommets de P ∗ sont tous et uniquement les sommets entiers du polytope initial P de I , tout algorithme pour L P peut être utilisé pour calculer la solution entière optimale. Je sais que pouvoir calculer P ∗ efficacement impliquerait $c$$LP$$I$$c$$c^*$$P^*$$I$$P^*$$P$$I$$LP$$P^*$ , mais la question supplémentaire suivante demeure:$P = NP$

Question supplémentaire

Y a-t-il des travaux antérieurs dans ce sens? Quelqu'un at - il déjà étudié la tâche de calcul, étant donné un polytope , son polytope optimale correspondant P * ? Quel est l'algorithme le plus connu pour le faire?$P$$P^*$

Cela semble être NP-difficile à faire exactement, par réduction de la somme du sous-ensemble. Supposons que nous ayons une procédure efficace pour calculer . Etant donné les entiers positifs v 1 , … , v n codés en binaire, nous souhaitons tester s'il existe un sous-ensemble sommant s . Prétraitez en jetant tous les entiers supérieurs à s .$O$$v_1,\dots,v_n$$s$$s$

Appelez la procédure pour obtenir un petit ensemble de points satisfaisant v 1 x 1 + ⋯ + v 1 x n ≤ s , satisfaisant vos conditions de minimalité (le prétraitement assure | S c | ≥ n ). Cet ensemble contiendra certainement un point sur l'hyperplan v 1 x 1 + ⋯ + v 1 x n = s s'il y en a un.$O$$v_1x_1+\dots+v_1x_n\leq s$$|S_c|\geq n$$v_1x_1+\dots+v_1x_n= s$

It seems to me you are trying to get to the convex hull of the IP - in essence this is what cut algorithms try to achieve. Although thereotically appealing these methods fare poorly in practice.

There is all theory on the generation of valid inequalities. A good starting point would be shrijver's book theory of integer programming.