La programmation 0-1 avec un nombre constant de contraintes est-elle résolvable polynomialement?

11

Il a été montré dans l'article "Programmation entière avec un nombre fixe de variables" que les programmations entières avec un nombre constant de contraintes (ou variables) peuvent être résolues polynomialement.

Cela vaut-il pour la programmation 0-1?

cc.complexity-theory integer-programming Régularité
la source
La programmation 0-1 n'est-elle pas un cas particulier de programmation entière?
Nathann Cohen
3
Je suppose que la partie non triviale est la suivante: si vous avez un algorithme de boîte noire A qui est capable de résoudre des programmes entiers avec un nombre constant de contraintes (mais arbitrairement de nombreuses variables), il n'est pas évident d'utiliser A pour résoudre des programmes 0-1 avec un nombre constant de contraintes. Vous ne pouvez pas simplement ajouter des contraintes de la forme pour chaque variable x i . 0≤Xje≤1Xje
Jukka Suomela
3
Qu'est-ce qu'un "programme 0-1 avec un nombre constant de contraintes"? Les contraintes ne comptent-elles pas? 0≤Xje≤1
Jeffε

Réponses:

20

Je suppose que par "programmation 0-1 avec un nombre constant de contraintes", vous entendez le problème suivant:

Maximisez une fonction linéaire de (x_1, x_2, ..., x_n) sous réserve des contraintes que chaque x_i est dans {0,1} et un nombre constant de contraintes linéaires supplémentaires.

Ce problème est NP-complet même avec 1 contrainte supplémentaire puisque 0-1 sac à dos peut être écrit sous cette forme.

Robin Kothari
la source
1
De plus, le "sac à dos illimité", où vous n'avez que les limites de non-négativité et les contraintes d'intégralité sans les limites supérieures de 1, est toujours NP-difficile.
daveagp
0

Lenstra a montré dans l'article mentionné que le problème de faisabilité du programme linéaire entier

Étant donné la matrice intégrale et b ∈ Z m . Existe-t-il un x ∈ Z n tel que A x ≤ b ?UNEm,nb∈Zm
X∈ZnUNEX≤b

est solvable polynomialement, si n ou m est constant. (Notez l'absence d'une fonction objectif.) Ce résultat est couramment utilisé dans l'analyse des problèmes paramétrés, c'est-à-dire qu'il peut être utilisé pour prouver la tractabilité des paramètres fixes par une réduction.

muede
la source
3
Je ne sais pas pourquoi vous avez posté cela, mais si vous laissez entendre que la différence entre la version de faisabilité et la version d'optimisation est importante, alors non, ce n'est pas important: un algorithme polynomial pour la version de faisabilité peut être utilisé pour résoudre la version d'optimisation également en temps polynomial en la combinant avec la recherche binaire.
Tsuyoshi Ito
-1

La programmation d'entiers 0-1 ou la programmation d'entiers binaires (BIP) est le cas particulier de la programmation d'entiers où les variables doivent être 0 ou 1 (plutôt que des entiers arbitraires). Ce problème est également classé comme NP-hard, et en fait la version de décision est NP-Complete.

Karan Sapra
la source
3
Bien que IP et BIP soient tous deux NP-durs, cela ne dit pas grand-chose si IP et BIP avec un nombre constant de contraintes sont NP-durs. En effet, IP avec un nombre constant de contraintes est en P, alors que BIP avec un nombre constant de contraintes est toujours NP-difficile.
Robin Kothari
-1

k2k

user8477
la source