Wprowadzenie

Napisz solver do programowania liniowego liczb całkowitych .

Wyzwanie

Twoim zadaniem jest napisanie solvera do programowania liniowego liczb całkowitych (ILP). W ILP podano nierówności liniowe zbioru niewiadomych (z których wszystkie są liczbami całkowitymi), a celem jest znalezienie minimum lub maksimum funkcji liniowej.

Na przykład w przypadku nierówności (przykład wzięty z mieszanego programowania liniowego liczb całkowitych )

 4x+2y-15≤0
  x+2y- 8≤0
  x+ y- 5≤0
- x      ≤0
   - y   ≤0

a funkcja celu 3x+2y, maksimum funkcji celu powinno wynosić 12( x=2,y=3), a minimum powinno być 0( x=y=0).

Dane wejściowe podano w postaci tablicy 2d (lub dowolnego odpowiednika zgodnego ze standardowymi specyfikacjami), każdy wiersz odpowiada jednej nierówności, z wyjątkiem ostatniego wiersza. Liczby w tablicy są współczynnikami, a ≤0część jest zawsze pomijana. Jeśli nw każdym rzędzie są elementy, oznacza to, że są n-1nieznane.

Ostatni wiersz tablicy odpowiada funkcji liniowej. Współczynniki są wymienione.

Na przykład tablica wejściowa dla powyższego problemu to

[[4,2,-15],[1,2,-8],[1,1,-5],[-1,0,0],[0,-1,0],[3,2,0]].

Wydajność powinna być minimalna i maksymalna, podawana w dowolnej rozsądnej formie.

W przypadku następującego problemu (dwa ograniczenia zostały usunięte z powyższego problemu):

[[4,2,-15],[1,2,-8],[1,1,-5],[3,2,0]].

Maksimum jest nadal 12, ale minimum nie istnieje, a funkcja celu może mieć dowolnie duże (w sensie wartości bezwzględnej) wartości ujemne. W takim przypadku program powinien wypisać dane12 wygenerować , zgodnie z wartością falsy, którą decyduje osoba odpowiadająca. Innym przypadkiem jest to, że w ogóle nie ma rozwiązania, na przykład

[[4,2,-15],[-1,-2,7],[-1,0,3],[0,1,0],[3,2,0]].

W takim przypadku należy również wygenerować wartości fałszowania. Byłoby dobrze rozróżnić przypadek, w którym „wartością optymalną” dla funkcji celu jest nieskończoność i przypadek, w którym nie ma żadnych rozwiązań, ale nie jest to konieczne.

Dane wejściowe zawierają tylko współczynniki całkowite zarówno dla nierówności, jak i dla funkcji celu. Wszystko niewiadome są również liczbami całkowitymi. Gwarantowana macierz współczynników nierówności ma pełną rangę.

Przypadki testowe

Kredyt na @KirillL. za znalezienie błędu w oryginalnym pakiecie testowym i pogłębienie mojego zrozumienia problemów z ILP.

Input
Output

[[4,2,-15],[1,2,-8],[1,1,-5],[-1,0,0],[0,-1,0],[3,2,1]]
[1,13]

[[4,2,-15],[1,2,-8],[1,1,-5],[3,2,0]]
[-inf, 12]

[[4,2,-15],[-1,-2,7],[-1,0,3],[0,1,0],[3,2,0]]
[NaN, NaN]

[[-1,-1,-1,-1,-1,8],[1,1,1,1,0,0],[5,5,5,5,6,7]]
[55, inf]

[[-1,-1,-1,-1,-1,8],[1,1,1,1,0,0],[0,0,0,0,0,4]]
[4, 4]

[[4,2,-15],[-1,-2,7],[-1,0,3],[0,1,0],[0,0,4]]
[NaN, NaN]

Okular

• Nie musisz martwić się obsługą wyjątków.

• To jest golf golfowy , najniższa liczba bajtów wygrywa.

• Maksymalna liczba niewiadomych: 9. Maksymalna liczba nierówności: 12.

• Możesz pobierać dane wejściowe i dostarczać dane wyjściowe za pomocą dowolnego standardowego formularza i możesz wybrać format.

• Jak zwykle obowiązują tutaj domyślne luki .

Python 3 , 534 bajty

import itertools as t
import operator as o
I=float("inf")
e=lambda p,A:sum([i[0]*i[1]for i in zip(p,A[:-1])])+A[-1]
def w(x,j):
	d=len(x[0])-1;C=[0]*d;v,w=I,I
	while 1:
		L={(*n,):(sum([0 if e(n,A)<=0 else e(n,A)for A in x[:-1]]),j*e(n,x[-1]))for n in [[sum(a) for a in zip(C,c)]for c in t.product(*[[-1,0,1]]*d)]};C,P=min(L.items(),key=o.itemgetter(1))[0],C;v,w,p,q=L[C][0],L[C][1],v,w
		if(all([e(C,A)<=e(P,A)for A in x[:-1]]))*(j*(e(C,x[-1])-e(P,x[-1]))<0)+(p==v>0):return I
		if(p==v)*(q<=w):return j*q
f=lambda x:(w(x,1),w(x,-1))

Wypróbuj online!

Przegląd

Jest to algorytm iteracyjny, poczynając od oryginału. Zbiera pozycje sąsiadów i przypisuje potencjalną funkcję: x:(a,b)gdzie xjest pozycja, ajest sumą odległości pozycji od półprzestrzeni każdej nierówności liniowej, bjest wartością celu w tej pozycji.

x:(a,b) < y:(c,d)iff a<cluba=c and b<d

Iteracja kończy się, gdy:

• pierwsza współrzędna potencjału nie zmniejszyła się i była dodatnia: system jest nieosiągalny
• odległość od każdej półprzestrzeni zmniejszyła się, podobnie jak cel: system jest nieograniczony.
• żaden z poprzednich i potencjał się nie zmniejszył: jest to wartość optymalna.

Matlab, 226 bajtów

ZASTRZEŻENIE : Nie jest to „oryginalna” implementacja, tylko dla zabawy.

Proste rozwiązanie wykorzystujące intlinprogfunkcję:

function r=f(a);b=-1*a(1:end-1,end);p=a(end,1:end-1);c=a(1:end-1,1:end-1);[~,f,h]=intlinprog(p,1:size(a,2)-1,c,b);[~,g,i]=intlinprog(-p,1:size(a,2)-1,c,b);s=[inf,nan,f];t=[inf,nan,g];r=a(end,end)+[s(4-abs(h)) -t(4-abs(i))];end

Zwraca wartości optymalne lub inf (-inf), jeśli problem jest nieograniczony, lub nan, jeśli jest to niemożliwe.

a = [4 2 -15; 1 2 -8; 1 1 -5; -1 0 0; 0 -1 0; 3 2 1]
b = [4 2 -15; 1 2 -8; 1 1 -5; 3 2 0]
c = [4 2 -15; -1 -2 7; -1 0 3; 0 1 0; 3 2 0]
d = [-1 -1 -1 -1 -1 8;  1 1 1 1 0 0; 0 0 0 0 0 4]
e = [4 2 -15; -1 -2 7; -1 0 3; 0 1 0; 0 0 4]

>> f(a)
ans =

     1    13

>> f(b)
ans =

   Inf    12

>> f(c)
ans =

   NaN   NaN

>> f(d)
ans =

     4     4

>> f(e)
ans =

   NaN   NaN