Pytania otagowane jako integer-programming

Jeśli mam zestaw ograniczeń liniowych, w których każde ograniczenie ma co najwyżej (powiedzmy) 4 zmienne (wszystkie nieujemne i o współczynnikach {0,1}, z wyjątkiem jednej zmiennej, która może mieć współczynnik -1), co wiadomo o rozwiązaniu przestrzeń? Nie interesuje mnie wydajne rozwiązanie (choć proszę wskazać, czy jedno jest znane) niż wiedza o …

23 co.combinatorics  integer-programming 

(Jest to kontynuacja tego pytania i odpowiedzi ). Mam następujący całkowicie nieimodularny (TU) całkowity program liniowy (ILP). Tutaj są dodatnimi liczbami całkowitymi podanymi jako część danych wejściowych. Określony podzbiór zmiennych x i j jest ustawiony na zero, a reszta może przyjmować dodatnie wartości całkowite:ℓ , m , n1, n2), …

21 ds.algorithms  reference-request  linear-programming  integer-programming  polynomial-time 

Próbując rozwiązać problem, ostatecznie wyraziłem jego część jako następujący program liczbowy całkowity. Tutaj są dodatnimi liczbami całkowitymi podanymi jako część danych wejściowych. Określony podzbiór zmiennych jest ustawiony na zero, a reszta może przyjmować dodatnie wartości całki:ℓ,m,n1,n2,…,nℓ,c1,c2,…,cm,wℓ,m,n1,n2,…,nℓ,c1,c2,…,cm,w\ell,m,n_{1},n_{2},\ldots,n_{\ell},c_{1},c_{2},\ldots,c_{m},wxijxijx_{ij} Zminimalizować ∑mj=1cj∑ℓi=1xij∑j=1mcj∑i=1ℓxij\sum_{j=1}^{m}c_{j}\sum_{i=1}^{\ell}x_{ij} Z zastrzeżeniem: ∑mj=1xij=ni∀i∑j=1mxij=ni∀i\sum_{j=1}^{m}x_{ij}=n_{i}\,\,\forall i ∑ℓi=1xij≥w∀j∑i=1ℓxij≥w∀j\sum_{i=1}^{\ell}x_{ij}\ge w\,\,\forall j Chciałbym wiedzieć, czy ten program …

13 reference-request  linear-programming  polynomial-time  integer-programming  integrality-gap 

Słynny artykuł H. Lenstry Integer Programowanie z ustaloną liczbą zmiennych z 1983 r. Stwierdza, że ​​programy liczb całkowitych o ustalonej liczbie zmiennych można rozwiązać wielomianem czasowym długości danych. Interpretuję to w następujący sposób. Programowanie liczb całkowitych ogólnie jest nadal NP-kompletne, ale jeśli mój typowy rozmiar problemu (powiedzmy około 10.000 zmiennych, …

12 co.combinatorics  linear-programming  integer-programming 

W artykule „Programowanie liczb całkowitych ze stałą liczbą zmiennych” wykazano, że programowanie liczb całkowitych o stałej liczbie ograniczeń (lub zmiennych) można rozwiązać wielomianowo. Czy to dotyczy programowania 0-1?

11 cc.complexity-theory  integer-programming 

Czy są znane algorytmy dla następującego problemu, które pokonały naiwny algorytm? Dane wejściowe: system o nierówności liniowych.A x ≤ bZAx≤bAx \le bmmm Wynik: wykonalne rozwiązanie jeśli takie istnieje.x∗∈ { 0 , 1 }nx∗∈{0,1}nx^*\in \{0,1 \}^n Załóżmy, że i mają wpisy liczb całkowitych. Interesują mnie granice najgorszego przypadku.ZAZAAbbb

10 np-hardness  integer-programming  exp-time-algorithms 

Czy są znane algorytmy dla następującego problemu, które pokonały naiwny algorytm? Dane wejściowe: matryca AAA i wektory b,cb,cb,c, gdzie wszystkie wpisy z pozycji A,b,cA,b,cA,b,c są liczbami całkowitymi nieujemnymi. Wyjście: optymalne rozwiązanie x∗x∗x^* do max{cTx:Ax≤b,x∈{0,1}n}max{cTx:Ax≤b,x∈{0,1}n}\max \{ c^T x : Ax \le b, x \in \{ 0,1\}^n \}. To pytanie jest udoskonaloną …

9 np-hardness  integer-programming  exp-time-algorithms