Was ist über Lösungen für ganzzahlige lineare Programmierprobleme bekannt?

Wenn ich eine Reihe von linearen Bedingungen habe, in denen jede Bedingung höchstens (sagen wir) 4 Variablen enthält (alle nichtnegativ und mit {0,1} Koeffizienten, außer einer Variablen, die einen -1-Koeffizienten haben kann), was ist über die Lösung bekannt Platz? Ich befasse mich weniger mit einer effizienten Lösung (obwohl bitte angeben, ob eine bekannt ist) als mit dem Wissen, wie klein das Minimum der Zielfunktion in Abhängigkeit von der Anzahl der Variablen und der Anzahl der Nebenbedingungen und der Anzahl der Variablen pro sein kann Zwang.

Konkret ist das Programm so etwas wie

minimiere t
  vorbehaltlich
für alles i, x_i ist eine positive ganze Zahl
x1 + x2 + x3 - t <0
x1 + x4 + x5 - t <0
...
x3 + x6 - t ≥ 0
x1 + x2 + x7 - t ≥ 0
...

Wenn eine konkrete Frage benötigt wird, ist es dann der Fall, dass die minimale Lösung t <= O (max {Anzahl von Variablen, Anzahl von Nebenbedingungen}) folgt, wobei die Konstante in O () von der Spärlichkeit abhängt? Aber selbst wenn die Antwort nein ist, interessiert es mich mehr, welche Art von Lehrbuch oder Papier ich studieren soll, um über solche Themen zu diskutieren, und ob es einen Studienbereich gibt, der sich dieser Sache widmet, aber ich weiß es einfach nicht die zu suchenden Begriffe. Vielen Dank.

Update: Durch weitere Überlegungen (und das Durchdenken der ziemlich einfachen Reduktion von 3SAT auf ILP, bei der Einschränkungen mit drei Variablen verwendet werden) stelle ich fest, dass die Frage der Koeffizienten kritisch ist (wenn es einen effizienten Algorithmus geben soll). Genauer gesagt haben alle x_i-Variablen 0 oder 1 Koeffizienten (mit höchstens drei 1 Koeffizienten in einer Einschränkung), und alle t-Variablen haben -1 Koeffizienten, und alle Vergleiche haben Variablen links und 0 rechts. Ich habe das obige Beispiel zur Verdeutlichung aktualisiert.

Die Antwort darauf (zumindest auf die konkrete Frage nach der linearen Begrenzung der Lösung) lautet nein. Dies ist Teil des folgenden Papiers: http://arxiv.org/abs/1011.3493 . Satz 5.1 war die Motivation für diese Frage.

Das Gegenbeispiel ist folgendes:

Grundgehäuse:

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

rekursiver Fall:

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

zusammen mit der Forderung, dass sie alle nicht negativ sein müssen.

Sie können durch Induktion beweisen, dass jede echte Lösung a_n ''> = a_n + 2 ^ n erfüllen muss. Wir ändern die "<0" -Einheiten in "≤ -1", weil jede ganzzahlige Lösung genau dann "≤ -1" erfüllt, wenn sie "<0" erfüllt.

Die Moral ist also, dass n Ungleichungen dieser Form die Eigenschaft haben können, dass alle ganzzahligen Lösungen mindestens eine ganze Zahl haben, die in n mindestens exponentiell ist, sicherlich nicht linear begrenzt, wie wir ursprünglich vermutet haben.

Wenn die Koeffizientenmatrix völlig unimodular ist , besteht eine effiziente Lösung durch gewöhnliche lineare Programmierung. Dies gilt für alle ILPs, nicht nur für spärliche, obwohl Sie diese Eigenschaft mit größerer Wahrscheinlichkeit für ein spärliches ILP wie Ihres nutzen können.

Ich vermute, Sie wissen das bereits. Lassen Sie mich versuchen, Ihnen eine bessere Antwort zu geben. Bevor Sie zu tief über die Einzelheiten nachdenken, lautet die Antwort auf Ihre konkrete Frage "Ja", eine Grenze besteht. Der Schnittpunkt von n Ungleichungen in m Variablen definiert ein Polytop. Da die Koeffizienten sich so gut verhalten, können wir mit ein wenig Arithmetik eine Obergrenze für die Dimension der Koordinaten ihrer Scheitelpunkte berechnen. Dies gibt Ihnen eine sehr einfache Obergrenze für die Dimension eines beliebigen Ganzzahlpunkts innerhalb des Polytops und damit für eine Lösung für Ihr Ganzzahlprogramm. Hast du das schon probiert?

Insbesondere Ihr Problem ist ziemlich strukturiert (ich bin gespannt, woher es kommt?), Daher bin ich zuversichtlich, dass wir viel präziser sein können, wenn wir es weiter diskutieren.

Nun zur allgemeineren Frage zum Finden von Informationen zu diesem Thema. Dies ist die Art von Problem, die traditionell in die Theorie der linearen und ganzzahligen Programmierung, einer Teilmenge der mathematischen Programmierung, fällt.

Es ist ein ziemlich aktives Forschungsgebiet, aber ein Großteil der Arbeit findet in Operations Research-Abteilungen unter den Überschriften "Optimierung" und "mathematische Programmierung" statt in der Informatik statt. Es gibt viele Lehrbücher zum Thema. Sie könnten die von Wolsey in Betracht ziehen , die wir in Berkeley verwenden. Hier finden Sie eine unzureichend genutzte Liste von Mythen und Gegenbeispielen von Greenberg, einschließlich ganzzahliger und linearer Programmierung, die Ihnen möglicherweise einen Eindruck davon vermitteln, welche Aspekte bei der Analyse solcher Probleme berücksichtigt werden. Wolsey ist dicht, aber ein guter Ausgangspunkt - es gibt eine Fülle von Techniken, um ILPs zu analysieren und Problemformulierungen bis zur Effizienz zu verbessern.

Lassen Sie mich hinzufügen, dass, wenn Sie den von mir vorgeschlagenen naiven Ansatz verfolgen und die Geometrie des Polytops analysieren, die zu suchenden Begriffe die Begrenzung der Koordinaten der Scheitelpunkte des Polytops betreffen. Diese Begriffe tauchen in der mathematischen Literatur häufiger in Bezug auf Polytope auf.

Sie können dieses Konto von Interesse finden:

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

und insbesondere der Artikel von G. Ziegler:

Vorträge über 0-1 Polytope

im:

Kalai, Gil; Ziegler, Günter M. (2000), Polytope: Kombinatorik und Berechnung, DMV-Seminar, 29, Birkhäuser, ISBN 9783764363512.