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

14

Considérons l' espace à n dimensions {0,1}n , et soit c une contrainte linéaire de la forme a1x1+a2x2+a3x3+ ... +an1xn1+anxnk , où aiR , et k R .xi{0,1}kR

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}nScS¬cSccS¬cc

Supposons que . Maintenant, soit O un sous-ensemble de S c tel que les trois énoncés suivants soient valables:|Sc|nOSc

  1. contient exactement n points.On
  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 dncd(x,c)x{0,1}ncBScB . 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 .xBd(x,c)xOd(x,c)OScc

Des questions

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

 

Exemple avec n=3

Exemple avec n = 3

, O = { ( 0 , 0 , 1 ) , ( 1 , 1 , 1 ) , ( 1 , 0 , 0 ) } .S¬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 . OcnO

La contrainte optimale est celle qui conduit au polytope optimal P .cP

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).PP

Formulation optimale

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 PcLPIccPIPPILPP , 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?PP

Giorgio Camerani
la source
Cela semble être NP-difficile à faire exactement, par réduction de la somme du sous-ensemble. Étant donné des entiers binaires , pour tester s'il existe un sous-ensemble sommant s , nous pouvons tester s'il y a un point sur l'hyperplan v 1 x 1 + + v 1 x n = s . Êtes-vous intéressé par les approximations? v1,,vnsv1x1++v1xn=s
Colin McQuillan
@ColinMcQuillan: La question était destinée à une solution exacte, mais je suis certainement aussi intéressé par les approximations. Pourquoi ne transformez-vous pas votre commentaire en réponse?
Giorgio Camerani
@ColinMcQuillan: En outre, votre hyperplan est défini en utilisant une égalité, tandis que le mien est défini en utilisant une inégalité. Êtes-vous sûr que cela ne fait aucune différence en termes de dureté? Je n'ai pas encore vérifié cela, donc je demande juste.
Giorgio Camerani
Je suis un peu confus au sujet de toutes les restrictions sur . Si vous recherchez des informations sur la coque convexe de S c, il existe de nombreux résultats dans la littérature de recherche opérationnelle sur le polytope à dos 0-1. En termes de formulations approximatives, voir ceci . OSc
Austin Buchanan,

Réponses:

6

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 .Ov1,,vnss

Appelez la procédure pour obtenir un petit ensemble de points satisfaisant v 1 x 1 + + v 1 x ns , 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.Ov1x1++v1xns|Sc|nv1x1++v1xn=s

Colin McQuillan
la source
v1,...,vn belong to R. Maybe you mean encoded in binary? Or maybe you wanted to say positive? 2) Why throwing out all the integers larger than s? They may contribute to the solution. For example: v1=3,v2=7,v3=5,s=2 if you throw away v2 you lose the only solution {v2,v3}.
Giorgio Camerani
2
I think what Colin means is that if the constraint coefficients ai are rational numbers, in their usual binary representation, then your problem appears to NP-hard. (Mixing real numbers and NP-hardness is always tricky.)
Jeffε
1
@GiorgioCamerani: I did need to say positive - I've updated my answer.
Colin McQuillan
1

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.

AJ Student
la source