[PYTHON] Kombinationsoptimierung - typisches Problem - Kombinationsauktionsproblem

Typisches Problem und Ausführungsmethode

Kombinationsauktionsproblem

$ n $ Kandidaten (Teilmenge $ S_j (\ subseteq M), j \ in N = \ {1, \ Punkte, n \ der Menge $ M = \ {1, \ Punkte, m \} $ } $) Gibt den Betrag $ c_j $ an. Wählen Sie aus den Kandidaten aus, damit der Gesamtbetrag maximiert wird. Wählen Sie keine doppelten Elemente der Menge $ M $ aus Es kann auch berücksichtigt werden, dass die Zielfunktion maximiert und die Ungleichheit der Einschränkungsbedingung in Assembly Covering Problem umgekehrt wird.

Ausführungsmethode

usage

Signature: combinatorial_auction(n, cand, limit=-1)
Docstring:
Kombinationsauktionsproblem
Maximieren Sie den Verkaufspreis so, dass die maximale Anzahl von Kandidaten für jeden Käufer ohne doppelten Verkauf von Elementen nicht überschritten wird
Eingang
    n:Elementanzahl
    cand: (Geldbetrag,Teilmenge,Käufer-ID)Kandidatenliste. Sie müssen keine Käufer-ID haben
    limit:Maximale Anzahl von Kandidaten für jeden Käufer.-1 ist unbegrenzt. Ein Wörterbuch mit der Käufer-ID als Schlüssel ist möglich
Ausgabe
Nummernliste der ausgewählten Kandidatenliste

python

#Stichprobe
from ortoolpy import combinatorial_auction
cand = [
    ( 15, (0,2), 0),
    ( 10, (0,), 1),
    (  8, (1,), 1),
    ( 14, (1,2), 2),
]
combinatorial_auction(3, cand)

Ergebnis

[1, 3]

python

# pandas.DataFrame
from ortoolpy.optimization import CombinatorialAuction
CombinatorialAuction('data/auction.csv')

python

# pandas.DataFrame
from ortoolpy.optimization import CombinatorialAuction
CombinatorialAuction('data/auction.csv',limit=1)

Daten

• data/auction.csv

Ergänzung

• Durch Hinzufügen einer kleinen Zufallszahl zum Geldbetrag fungiert es auch als Lotterie.