Ottimizzazione combinatoria, problema di allocazione
Sto cercando di risolvere un problema (in pyspark / python) in cui ho bisogno di trovare due valori distinti da allocare e come allocarli in una rete di negozi.
I due valori distinti possono essere solo valori interi e vincolati entro un limite inferiore e superiore. Per ciascuna coppia di valori così distinti, diciamo 4 e 8, ogni negozio può ottenere 4 o 8 dando un totale di 2 n diversi modi di allocazione se ci sono n negozi ( n è vicino a 1000).
La funzione obiettivo è complessa e utilizza modelli predittivi per fornire l'impatto di una particolare coppia di valori corrispondente alla sua allocazione nella rete.
Speravo di poter creare una funzione di costo del modulo:
Cost = f( variant1, variant2, store_1_variant, store_2_variant, ..., store_n_variant)
dove
variant1 = 4(intero, vincolato entro un valore massimo)variant2 = 8(intero, vincolato entro un valore massimo)store_1_variant, ..., store_n_variantsono binari [0,1] per suggerire se ricevonovariant_1o meno (non riceverevariant1significherebbe riceverevariant2)
Potrei risolvere per gli n + 2 parametri che minimizzano il costo (c'è un altro vincolo che deve tenere sotto controllo l'impatto di una certa allocazione)
Ho esaminato varie tecniche di ottimizzazione combinatoria ma nessuna che sembra consentirmi una funzione definita dall'utente come funzione di costo.
Non ho alcuna esperienza precedente in questo settore, quindi qualsiasi direzione / assistenza è apprezzata.
modificare
Per aggiungere alcune informazioni sulla forma corrente della funzione di costo, continuando con l'esempio di due varianti 4 e 8 con diciamo 5 negozi, f(4, 8, 0, 1, 1, 0, 0)avrà un costo associato del modulo
a * s 11 * (s 12/8 ) b + a * s 21 * (s 22/4 ) b + a * s 31 * (s 32/4 ) b + a * s 41 * (s 42/8 ) b + a * s 51 * (s 52/8 ) b
dove s 11 e s 12 sono metriche a livello di negozio per il negozio 1 e così via.
Parametri a e b sono regrediti coefficienti da dati storici, ma questo è solo un buon punto di partenza e alla fine evolvere in una forma funzionale più complessa (potrebbe essere previsioni di un algoritmo ML)
Vincoli:
variant1 <= k 1
variant2> = k 1 e <= k 2
(s 13 /8) + (s 23 /4) + (s 33 /4) + (s 43 /8) + (s 53 /8) dovrebbe giacciono tra [(0,95 / k 1 ) * (s 13 + s 23 + s 33 + s 43 + s 53 ), (1,05 / k 1 ) * (s 13 + s 23 + s 33 + s 43 + s 53 ) ] (Deviazione del 5%)
dove k 1 , k 2 , variante1 e variante2 sono numeri interi
Risposte
Dato quello che sembra essere un vincolo non lineare (il vincolo di deviazione del 5%) e una funzione obiettivo non lineare (e apparentemente arbitrariamente complessa), non sarei ottimista nel trovare una soluzione dimostrabile ottimale. Se sei disposto ad accontentarti di una "buona" soluzione, ci sono una varietà di metaeuristiche che potrebbero essere applicabili. La raccomandazione di un particolare metaeuristico dipenderebbe dalle specificità dei vincoli e dalle tendenze religiose della persona che fa la raccomandazione.
Addendum: in base ai commenti di seguito, ho provato sia un algoritmo genetico che un'euristica avida. L'euristica avida ha costantemente sovraperformato la GA (risposta migliore in meno tempo). Codificato in R ed esegue un PC con dati costituiti per 1.000 negozi (utilizzando$k_1=6$ e $k_2=12$), l'euristica avida in genere richiedeva meno di 0,2 secondi. L'euristica avida scorre attraverso tutti i possibili valori di variant1 e variant2. Per ogni combinazione, inizialmente assegna il più economico dei due a tutti i negozi, quindi verifica se il vincolo di saldo è soddisfatto. In caso contrario, passa attraverso i negozi in un ordine "più economico", passando dalla variante più economica a quella più costosa, fino a quando il saldo non è (si spera) raggiunto. Ovviamente, valori maggiori di$k_1$ e $k_2$ porterà a più tempo di elaborazione, ma penso che questa sia ancora una strada molto pratica da intraprendere.