Quels programmes linéaires entiers sont faciles?

Tout en essayant de résoudre un problème, j'ai fini par en exprimer une partie comme le programme linéaire entier suivant. Ici sont tous des entiers positifs donnés dans le cadre de l'entrée. Un sous-ensemble spécifié des variables est mis à zéro, et le reste peut prendre des valeurs intégrales positives: $\ell,m,n_{1},n_{2},\ldots,n_{\ell},c_{1},c_{2},\ldots,c_{m},w$ $x_{ij}$

Minimiser

$\sum_{j=1}^{m}c_{j}\sum_{i=1}^{\ell}x_{ij}$

Sujet à:

$\sum_{j=1}^{m}x_{ij}=n_{i}\,\,\forall i$

$\sum_{i=1}^{\ell}x_{ij}\ge w\,\,\forall j$

Je voudrais savoir si ce programme entier est résoluble en temps polynomial; mon problème d'origine est résolu s'il l'est, et je dois essayer autrement si ce n'est pas le cas. Ma question est donc:

Comment savoir si un certain programme linéaire entier peut être résolu en temps polynomial? Quels programmes linéaires entiers sont connus pour être faciles? En particulier, le programme ci-dessus peut-il être résolu en temps polynomial? Pourriez-vous m'indiquer quelques références à ce sujet?

reference-request linear-programming polynomial-time integer-programming integrality-gap gphilip
la source

Réponses:

Il s'agit d'un cas particulier du problème de transport (ou du problème de flux à coût minimum), et peut donc être résolu en temps polynomial. La matrice des coefficients est totalement unimodulaire car c'est la matrice d'incidence d'un graphe bipartite.

Les articles suivants de Wikipédia pourraient être utiles.

Yoshio Okamoto
la source

@Yoshio: Merci, cela répond à mon cas de problème particulier (une fois que je l'ai vérifié par moi-même). Connaissez-vous des conditions autres que l'unimodularité totale qui garantissent une solution en temps polynomial?

gphilip

@gphilip: Je résumerais ces questions par le terme "intégrité des polyèdres" et la littérature sur ce sujet est immense. Le livre "Combinatorial Optimization: Packing and Covering" de Gerard Cornuejols (publié en 2001) décrit plusieurs résultats dans ce sens.

Yoshio Okamoto

@Yoshio: Pourriez-vous me dire pourquoi vous pensez que la matrice des coefficients est la matrice d'incidence d'un graphe bipartite? Excusez mon ignorance, mais pour parler d'une matrice de coefficients, ne devons-nous pas d'abord convertir toutes les contraintes sous la forme standard (

)? Une fois que nous faisons cela, la matrice aura -1 entrées, puis elle ne correspond pas à la définition d'une matrice d'incidence (AFAIK). Ou est-ce le cas que l'on puisse parler de la matrice des coefficients sans d' abord convertir les contraintes en forme standard?

A x \leq b

$Ax\le b$

gphilip

@gphilip: Excusez-moi. J'ai fait un raccourci implicite, et je parlais de la matrice des coefficients sans conversion vers la forme standard. J'ai utilisé les raccourcis suivants. (1) Si

est totalement unimodulaire (TU, pour faire court), alors

est également TU, ce qui signifie que nous n'avons pas à nous soucier de la direction des inégalités. (2) Si

est TU, alors

est aussi TU, ce qui signifie que nous n'avons pas à nous soucier des contraintes d'égalité. (3) Chaque sous-matrice d'une matrice TU est TU. L'application de ces règles à la matrice d'incidence d'un graphe bipartite devrait prouver la propriété du formulaire standard.

A

$A$

- A

$-A$

A

$A$

[A ∣ - A]

$[A \mid -A]$

Yoshio Okamoto

Permettez-moi de modifier mes règles de raccourci comme suit. (1) La duplication d'une ligne maintient une unimodularité totale. (2) L'inversion du signe d'une rangée maintient une unimodularité totale. Ils devraient faire le travail.

Yoshio Okamoto

En général, c'est difficile à dire. Mais une condition suffisante est que votre matrice de contraintes soit totalement unimodulaire et que le côté droit soit toujours entier (dans ce cas, le côté droit est entier, mais vous devez toujours vérifier l'unimodularité)

Vous devriez jeter un œil à ceci: http://en.wikipedia.org/wiki/Linear_program#Integer_unknowns

Vinicius dos Santos
la source

Je pensais à votre matrice et elle a l'air totalement unimodulaire.

Vinicius dos Santos

@Vinicius: Pouvez-vous me dire pourquoi la matrice vous semble totalement unimodulaire? Je n'ai pas pu comprendre cela, malgré le commentaire de Yoshio (veuillez voir ma réponse ici).

gphilip

@gphilip: À en.wikipedia.org/wiki/Unimodular_matrix dans la section "Matrices totalement unimodulaires communes", le premier élément énumère 4 conditions suffisantes pour qu'une matrice soit unimodulaire. Je pense que ces conditions, ainsi que les raccourcis commentés par Yoshio, sont suffisantes pour montrer que le problème peut être résolu en temps polynomial.

Vinicius dos Santos

@gphilip: Quelle est la motivation de ce programme linéaire?

Vinicius dos Santos

@Vinicius: Nous essayons de résoudre un problème exprimé en termes de modification d'une matrice d'entrée d'une certaine manière pour obtenir une autre matrice avec de bonnes propriétés. Ce LP est sorti d'un sous-problème pendant le processus.

gphilip

Un programme entier avec seulement des égalités peut être résolu par un programme linéaire.

T ....
la source

cela semblait important pour lui-même.

T ....

Je n'appellerais pas cela un programme entier. C'est un système d'équations linéaires sur les entiers, résoluble efficacement en calculant la forme normale d'Hermite.

Sasho Nikolov

@SashoNikolov un cas dégénéré mais certainement valide.

T ....

pourquoi vote négatif?

T ....