Ganzzahlige lineare Programmierung

21

Einführung

Schreiben Sie einen Löser für die ganzzahlige lineare Programmierung .

Herausforderung

Ihre Aufgabe ist es, einen Löser für die ganzzahlige lineare Programmierung (ILP) zu schreiben. In ILP werden lineare Ungleichungen einer Menge von Unbekannten (von denen alle ganze Zahlen sind) angegeben, und das Ziel besteht darin, das Minimum oder Maximum einer linearen Funktion zu finden.

Zum Beispiel für die Ungleichungen (Beispiel aus Mixed Integer Linear Programming )

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

und die Zielfunktion 3x+2ysollte das Maximum der Zielfunktion 12( x=2,y=3) sein, während das Minimum 0( x=y=0) sein sollte.

Die Eingabe wird als 2d-Array (oder ein beliebiges Äquivalent gemäß den Standardspezifikationen) angegeben. Jede Zeile entspricht einer Ungleichung, mit Ausnahme der letzten Zeile. Die Zahlen im Array sind die Koeffizienten, und der ≤0Teil wird immer weggelassen. Wenn sich nin jeder Zeile Elemente befinden , bedeutet dies, dass n-1Unbekanntes vorhanden ist.

Die letzte Zeile des Arrays entspricht der linearen Funktion. Die Koeffizienten werden aufgelistet.

Beispielsweise ist das Eingabearray für das obige Problem

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

Die Ausgabe sollte das Minimum und das Maximum sein, die in einer angemessenen Form angegeben werden.

Für das folgende Problem (zwei der Einschränkungen werden aus dem obigen Problem entfernt):

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

Das Maximum ist noch 12, aber das Minimum existiert nicht und die Zielfunktion kann beliebig große (im Sinne des Absolutwertes) negative Werte haben. In diesem Fall sollte das Programm 12einen falschen Wert ausgeben , der vom Antwortenden festgelegt wird. Ein anderer Fall ist, dass es überhaupt keine Lösung gibt, zum Beispiel

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

In diesem Fall sollten auch falsche Werte ausgegeben werden. Es wäre schön, den Fall zu unterscheiden, in dem der "optimale Wert" für die Zielfunktion unendlich ist, und den Fall, in dem es überhaupt keine Lösungen gibt, dies jedoch nicht erforderlich ist.

Die Eingabe enthält nur ganzzahlige Koeffizienten sowohl für die Ungleichungen als auch für die Zielfunktion. Alle Unbekannten sind auch ganze Zahlen. Die Koeffizientenmatrix der Ungleichungen hat garantiert den vollen Rang.

Testfälle

Dank an @KirillL. um einen Fehler in der ursprünglichen Testsuite zu finden und mein Verständnis für ILP-Probleme zu vertiefen.

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]

Technische Daten

  • Sie müssen sich keine Sorgen um die Ausnahmebehandlung machen.

  • Dies ist , die niedrigste Anzahl von Bytes gewinnt.

  • Maximale Anzahl der Unbekannten: 9. Die maximale Anzahl von Ungleichheiten: 12.

  • Sie können Eingaben und Ausgaben über jedes Standardformular vornehmen und das Format frei wählen.

  • Wie üblich gelten hier Standardlücken .

Weijun Zhou
quelle
Generalises codegolf.stackexchange.com/q/155460/194
Peter Taylor
Sie haben es in der Aufgabenbeschreibung nicht explizit erwähnt, aber ich vermute, Sie suchen nach Originalimplementierungen des Algorithmus und nicht nach langweiligem Code, der vorhandene Bibliotheken nutzt? Trotzdem habe ich mit Ihren Testfällen in R gespielt und konnte die Ergebnisse nicht exakt reproduzieren.Eg, [55, inf] case funktioniert nur, wenn die Variablen zwangsläufig nicht negativ sind. Dann liefert der Fall [-inf, 12] aber auch normale Ergebnisse [0, 12]. Wenn die Untergrenze hingegen -inf ist, kann der Fall [55, inf] sowohl in Min- als auch in Max-Szenarien nicht gelöst werden.
Kirill L.
Ja, ich suche nach originellen Implementierungen.
Weijun Zhou
@KirillL. Können Sie einen Vektor angeben, bei dem die Funktion im Testfall [55, inf] einen Wert kleiner als 55 ergibt? Ich habe es gerade mit einem Online-Löser verglichen und der Fall scheint in Ordnung zu sein. Ich habe die folgenden Überlegungen, wenn ich diesen Testfall mache: Die erste Einschränkung erfordert, dass die Summe aller freien Variablen geq 8 ist, aber die zweite erfordert, dass die Summe aller außer der letzten leq 0 ist. Wenn wir jemals versuchen, die zu verringern Wenn Sie eine der ersten 4 freien Var reduzieren, muss die endgültige Var um den gleichen Betrag erhöht werden, was zu einem höheren Wert für das Ziel führt.
Weijun Zhou
Hier ist mein Snippet , obwohl es auf TIO aufgrund fehlender Bibliothek nicht funktioniert. Dies ergibt 55, wird jedoch mit "model is unbounded" beendet, wenn ich die Zeile set.bounds auskommentiere. Möglicherweise liegt der Fehler aber auf meiner Seite. Könnten Sie auch einen Link zum Online-Löser geben?
Kirill L.

Antworten:

2

Python 3 , 534 Bytes

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))

Probieren Sie es online!

Überblick

Es ist ein iterativer Algorithmus, der vom Origo ausgeht. Es sammelt die Nachbarpositionen und weist eine mögliche Funktion zu: x:(a,b)Wo xist die Position, aist die Summe der Abstände der Position von den Halbräumen jeder linearen Ungleichung, bist der Wert des Ziels an dieser Position.

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

Die Iteration stoppt, wenn:

  • Die erste Koordinate des Potentials hat sich nicht verringert und ist positiv: Das System ist nicht realisierbar
  • Die Entfernung von jedem halben Raum hat sich ebenso verringert wie das Ziel: Das System ist unbegrenzt.
  • Keine der vorherigen und das Potenzial hat nicht abgenommen: Es ist der optimale Wert.
mmuntag
quelle
1

Matlab, 226 Bytes

HAFTUNGSAUSSCHLUSS : Keine "originelle" Implementierung, nur zum Spaß.

Einfache Lösung unter Ausnutzung der intlinprogFunktion:

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

Es gibt die optimalen Werte zurück oder inf (-inf), wenn das Problem unbegrenzt ist, oder nan, wenn es nicht durchführbar ist.

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
PieCot
quelle