Que sait-on des solutions aux problèmes de programmation linéaire à nombres entiers clairsemés?

Si j'ai un ensemble de contraintes linéaires dans lesquelles chaque contrainte a au plus (disons) 4 variables (toutes non négatives et avec {0,1} coefficients à l'exception d'une variable qui peut avoir un coefficient -1), que sait-on de la solution espace? Je suis moins préoccupé par une solution efficace (bien que s'il vous plaît indiquer si on est connu) que de savoir à quel point le minimum de la fonction objectif peut être petit, en fonction du nombre de variables et du nombre de contraintes, et du nombre de variables par contrainte.

Plus concrètement, le programme est quelque chose comme

minimiser t
  soumis à
pour tout i, x_i est un entier positif
x1 + x2 + x3 - t <0
x1 + x4 + x5 - t <0
...
x3 + x6 - t ≥ 0
x1 + x2 + x7 - t ≥ 0
...

Si une question concrète est nécessaire, est-il vrai que la solution minimale obéit à t <= O (max {# de variables, # de contraintes}), la constante dans O () dépendant de la rareté? Mais même si la réponse est non, je suis plus intéressé à savoir quel type de manuel ou de papier étudier pour une discussion sur de telles questions, et s'il y a un domaine d'étude consacré à ce genre de chose mais je ne sais pas les termes à rechercher. Merci.

Mise à jour: Avec une réflexion plus approfondie (et en réfléchissant à la réduction assez simple de 3SAT en ILP, qui utilise des contraintes à trois variables), je me rends compte que la question des coefficients est critique (s'il va y avoir un algorithme efficace). Plus précisément, toutes les variables x_i ont 0 ou 1 coefficients (avec au plus trois coefficients 1 dans une contrainte), et toutes les variables t ont -1 coefficients, et toutes les comparaisons ont des variables à gauche et 0 à droite. J'ai mis à jour l'exemple ci-dessus pour clarifier.

La réponse à cette question (du moins à la question concrète de la limitation linéaire de la solution) est non. Cela fait partie du document suivant: http://arxiv.org/abs/1011.3493 . Le théorème 5.1 était la motivation de cette question.

Le contre-exemple est le suivant:

cas de base:

a_1 '+ b_1' - t ≥ 0
a_1 '' + b_1 '' - t ≥ 0
a_1 + b_1 '- t ≤ -1
a_1 '+ b_1' '- t ≤ -1

cas récursif:

a_n '+ b_n' + a_ {n-1} - t ≥ 0
a_n '' + b_n '' + a_ {n-1} - t ≥ 0
a_n + b_n '+ a_ {n-1}' '- t ≤ -1
a_n '+ b_n' + a_ {n-1} '' - t ≤ -1

tout en exigeant qu'ils soient tous non négatifs.

Vous pouvez prouver par induction que toute solution réelle doit satisfaire a_n ''> = a_n + 2 ^ n. Nous changeons les inégalités "<0" en "≤ -1" car toute solution entière satisfait "≤ -1" si et seulement si elle satisfait "<0".

Donc, la morale est que n inégalités de cette forme peuvent avoir la propriété que toutes les solutions entières ont au moins un entier au moins exponentiel dans n, certainement pas linéairement limité comme nous le pensions à l'origine.

Si la matrice de coefficients est totalement unimodulaire , alors une solution efficace existe via une programmation linéaire ordinaire. Cela vaut pour n'importe quel ILP, pas seulement pour ceux qui sont clairsemés - bien que vous soyez plus susceptible d'exploiter cette propriété pour un ILP clairsemé comme le vôtre.

Je suppose que vous le savez peut-être déjà, alors laissez-moi essayer de vous donner une meilleure réponse. Avant de réfléchir trop profondément aux détails, la réponse à votre question concrète est «oui», une limite existe. L'intersection de n inégalités dans m variables définit un polytope. Parce que les coefficients sont si bien comportés, nous pouvons établir une limite supérieure sur la dimension des coordonnées de ses sommets avec un peu d'arithmétique. Cela vous donne une limite supérieure très facile sur la dimension de tout point entier dans le polytope, et donc sur une solution à votre programme entier. Avez-vous déjà essayé cela?

Votre problème en particulier a un peu de structure (je suis curieux, d'où vient-il?), Donc je suis convaincu que nous pouvons être beaucoup plus précis que cela si nous en discutons plus avant.

Maintenant, pour la question plus générale sur la recherche d'informations sur ce sujet. C'est le genre de problème qui tombe traditionnellement dans la théorie de la programmation linéaire et entière, un sous-ensemble de la programmation mathématique.

C'est un domaine de recherche assez actif, mais une grande partie du travail se déroule dans des départements de recherche opérationnelle sous les rubriques «optimisation» et «programmation mathématique» au lieu de l'informatique. Il existe de nombreux manuels sur le sujet. Vous pourriez envisager celui de Wolsey , que nous utilisons à Berkeley. Voici une liste sous-utilisée des mythes et contre-exemples de Greenberg, y compris la programmation entière et linéaire, qui peut vous donner une idée de ce que les gens considèrent lors de l'analyse de tels problèmes. Wolsey est dense, mais c'est un bon point de départ - il existe une multitude de techniques pour analyser les ILP et améliorer la formulation des problèmes au point de l'efficacité.

Permettez-moi d'ajouter que si vous poursuivez l'approche naïve que je suggère, en analysant la géométrie du polytope, les termes à rechercher concerneraient la délimitation de la taille des coordonnées des sommets du polytope. Ces termes reviennent plus souvent dans la littérature mathématique sur les polytopes.

Vous pouvez trouver ce compte d'intérêt:

http://en.wikipedia.org/wiki/Polyhedral_combinatorics

et en particulier l'article de G. Ziegler:

Conférences sur 0-1 polytopes

dans:

Kalai, Gil; Ziegler, Günter M. (2000), Polytopes: Combinatorics and Computation, DMV Seminar, 29, Birkhäuser, ISBN 9783764363512.