Pytania otagowane jako integer-programming

3
Ekspresowe operacje logiczne typu boolowskiego w programowaniu liniowym całkowitym zero-jeden (ILP)
Mam całkowity program liniowy (ILP) z niektórymi zmiennymi które mają reprezentować wartości boolowskie. Wartości muszą być liczbami całkowitymi i zawierać 0 lub 1 ( ).xixix_ixixix_i0≤xi≤10≤xi≤10 \le x_i \le 1 Chcę wyrazić operacje boolowskie na tych zmiennych o wartości 0/1, używając ograniczeń liniowych. Jak mogę to zrobić? Mówiąc dokładniej, chcę ustawić …
1
Najszybsza znana złożoność kombinatorycznego algorytmu ILP?
Zastanawiam się, co jest najbardziej znany algorytm, jeśli chodzi o Big- notacji, aby rozwiązać Programowanie Integer Linear?OOO Wiem, że problem jest , więc nie oczekuję niczego wielomianowego. Wiem, że istnieje wiele heurystyk, które są wykorzystywane w praktycznych zastosowaniach, takich jak CPLEX, ale bardziej interesuje mnie formalna, w najgorszym przypadku złożoność …
2
Skrócenie czasu między ILP a SAT?
Tak więc, jak wiadomo, problem decyzyjny ILP 0-1 jest NP-zupełny. Pokazanie tego w NP jest łatwe, a pierwotna redukcja pochodziła z SAT; od tego czasu wykazano, że wiele innych problemów z NP-Complete ma formulacje ILP (które działają jako redukcje tych problemów do ILP), ponieważ ILP jest bardzo przydatna ogólnie. Redukcje …
1
Jak podzielić zestaw na określoną liczbę rozłącznych podzbiorów pod pewnymi warunkami?
Dostaję zestaw , liczbę całkowitą s \ leqslant k i nieujemne liczby całkowite a_ {ij} . Mój problem polega na znalezieniu s podzbiory rozłączne S_j z \ {1, \ ldots, k \} takie, że:A≜{1,…,k}A≜{1,…,k}A\triangleq\{1,\ldots,k\}s⩽ks⩽ks\leqslant kaijaija_{ij}sssSjSjS_j{1,…,k}{1,…,k}\{1,\ldots,k\} ⋃sj=1Sj=A⋃j=1sSj=A\bigcup_{j=1}^s S_j=A ; i |Sj|⩽aij|Sj|⩽aij|S_j|\leqslant a_{ij} dla wszystkich i∈Sji∈Sji\in S_j i j=1,…,sj=1,…,sj=1,\ldots,s . Jak rozwiązać …
5
Czy wszystkie problemy z całkowitym programowaniem liniowym są trudne?
Jak rozumiem, problem przypisania występuje w P, ponieważ węgierski algorytm może go rozwiązać w czasie wielomianowym - O (n 3 ). Rozumiem również, że problem z przypisaniem jest całkowitym problemem programowania liniowego , ale strona Wikipedii stwierdza, że ​​jest to NP-Hard. Dla mnie oznacza to, że problem przypisania jest w …
Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.