Ottimizzazione delle richieste cartesiane con costi affini

https://stackoverflow.com/questions/1403933

05-07-2019
|

Domanda

Ho una richiesta di ottimizzazione dei costi che non so come fare se c'è della letteratura. È un po 'difficile da spiegare, quindi mi scuso in anticipo per la lunghezza della domanda.

Esiste un server a cui accedo che funziona in questo modo:

viene fatta una richiesta su record (r1, ... rn) e campi (f1, ... fp)
puoi richiedere solo il prodotto cartesiano (r1, ..., rp) x (f1, ... fp)
Il costo (tempo e denaro) associato a tale richiesta è affine alla dimensione della richiesta:

T((r1, ..., rn)x(f1, ..., fp) = a + b * n * p

Senza perdita di generalità (solo normalizzando), possiamo supporre che b=1 quindi il costo è:

T((r1, ...,rn)x(f1,...fp)) = a + n * p

Ho solo bisogno di richiedere un sottoinsieme di coppie (r1, f(r1)), ... (rk, f(rk)), una richiesta che proviene dagli utenti. Il mio programma funge da intermediario tra l'utente e il server (che è esterno). Ho molte richieste come questa (decine di migliaia al giorno).

Graficamente, possiamo immaginarlo come una matrice sparsa n x p, per la quale voglio coprire i valori diversi da zero con una matrice secondaria:

   r1 r2 r3 ... rp
   ------      ___
f1 |x  x|      |x|
f2 |x   |      ---
   ------
f3
..    ______
fn    |x  x|
      ------

Avere:

il numero di sottoatrici mantenuto ragionevole a causa del costo costante
tutte le 'x' devono trovarsi all'interno di una sottotrix
l'area totale coperta non deve essere troppo grande a causa del costo lineare

Definirò g il coefficiente di sparseness del mio problema (numero di coppie necessarie su coppie possibili totali, g = k / (n * p). Conosco il coefficiente a.

Ci sono alcune ovvie osservazioni:

se a è piccolo, la soluzione migliore è richiedere ciascuna coppia (record, campo) in modo indipendente e il costo totale è: k * (a + 1) = g * n * p * (a + 1)
se a è grande, la soluzione migliore è richiedere l'intero prodotto cartesiano e il costo totale è: a + n * p
la seconda soluzione è migliore non appena g > g_min = 1/ (a+1) * (1 + 1 / (n * p))
ovviamente gli ordini nei prodotti cartesiani non sono importanti, quindi posso trasporre le righe e le colonne della mia matrice per renderla più facilmente ricopribile, ad esempio:

   f1 f2 f3
r1  x    x
r2     x 
r3  x    x

può essere riordinato come

   f1 f3 f2
r1  x  x
r3  x  x
r2       x

E c'è una soluzione ottimale che è quella di richiedere (f1,f3) x (r1,r3) + (f2) x (r2)

Cercare tutte le soluzioni e cercare il costo più basso non è un'opzione, perché la combinatoria esplode:

for each permutation on rows: (n!)
   for each permutation on columns: (p!)
       for each possible covering of the n x p matrix: (time unknown, but large...)
           compute cost of the covering

quindi sto cercando una soluzione approssimativa. Ho già una sorta di algoritmo avido che trova una copertura data una matrice (inizia con celle unitarie, quindi le unisce se la percentuale di celle vuote nell'unione è al di sotto di una soglia).

Per mettere in mente alcuni numeri, il mio n è da qualche parte tra 1 e 1000, e il mio p da qualche parte tra 1 e 200. Il modello di copertura è davvero "bloccato", perché i record arrivano in classi per cui i campi richiesti sono simili . Purtroppo non riesco ad accedere alla classe di un record ...

Domanda 1 : qualcuno ha un'idea, un'intelligente semplificazione o un riferimento per un documento che potrebbe essere utile? Dato che ho molte richieste, un algoritmo che funziona bene in media è quello che sto cercando (ma non posso permettermi di lavorare molto male su alcuni casi estremi, ad esempio richiedere l'intero matrice quando n e p sono grandi e la richiesta è effettivamente piuttosto scarsa).

Domanda 2 : In effetti, il problema è ancora più complicato: il costo è in effetti più simile al modulo: a + n * (p^b) + c * n' * p', dove b è una costante < 1 (una volta che viene richiesto un record per un campo, non è troppo costoso chiedere altri campi) e n' * p' = n * p * (1 - g) è il numero di celle che non voglio richiedere (perché non sono valide e vi è un costo aggiuntivo nel richiedere cose non valide). Non riesco nemmeno a sognare una soluzione rapida a questo problema, ma comunque ... un'idea chiunque?

Soluzione

La selezione delle sottomatrici per coprire i valori richiesti è una forma del set che copre il problema e quindi NP completo. Il tuo problema aggiunge a questo già difficile problema che i costi degli insiemi differiscono.

Il fatto che tu permetta di permutare le righe e le colonne non è un problema così grande, perché puoi semplicemente considerare le matrici disconnesse. La riga uno, le colonne da quattro a sette e la riga cinque, le colonne quattro due sette sono un set valido perché è possibile scambiare solo la riga due e la riga cinque e ottenere la riga uno connessa sottomatrix, la colonna quattro alla riga due, colonna sette. Naturalmente questo aggiungerà alcuni vincoli - non tutti i set sono validi sotto tutte le permutazioni - ma non credo che questo sia il problema più grande.

L'articolo di Wikipedia fornisce i risultati di inapprossimabilità che il problema non può essere risolto in un tempo polinomiale meglio di un fattore 0.5 * log2(n) dove n è il numero di insiemi. Nel tuo caso 2^(n * p) è un limite superiore (abbastanza pessimistico) per il numero di set e rendimenti che puoi trovare una soluzione fino a un fattore 0.5 * n * p nel tempo polinomiale (oltre a N = NP e ignorando i costi variabili) .

Un limite inferiore ottimistico per il numero di insiemi che ignora le permutazioni di righe e colonne sta 0.5 * n^2 * p^2 producendo un fattore molto migliore di log2(n) + log2(p) - 0.5. Di conseguenza, ci si può aspettare di trovare una soluzione nel caso peggiore di n = 1000 e p = 200 fino a un fattore di circa 17 nel caso ottimistico e fino a un fattore di circa 100.000 nel caso pessimistico ( ignorando ancora i costi variabili).

Quindi il meglio che puoi fare è usare un algoritmo euristico (l'articolo di Wikipedia menziona un algoritmo avido quasi ottimale) e accettare che ci sarà un caso in cui l'algoritmo funziona (molto) male. Oppure vai dall'altra parte e usi un algoritmo di ottimizzazione e cerchi di trovare una buona soluzione usando più tempo. In questo caso, suggerirei di provare a utilizzare A * search .

Altri suggerimenti

Sono sicuro che ci sia un ottimo algoritmo per questo là fuori da qualche parte, ma ecco le mie idee intuitive:

Approccio Toss-some-rectangles:
- Determina un " approssimativamente ottimale " dimensione del rettangolo basata su a .
- Posiziona questi rettangoli (forse in modo casuale) sui punti richiesti, fino a quando tutti i punti sono coperti.
- Ora prendi ogni rettangolo e riduci il più possibile senza " perdendo " eventuali punti dati.
- Trova i rettangoli vicini l'uno all'altro e decidi se combinarli sarebbe più economico che tenerli separati.
Grow
- Inizia con ogni punto nel suo rettangolo 1x1.
- Individua tutti i rettangoli all'interno di n righe / colonne (dove n può essere basato su a ); vedi se riesci a combinarli in un rettangolo senza alcun costo (o costo negativo: D).
- Ripeti.
Shrink
- Inizia con un grande rettangolo, che copre TUTTI i punti.
- Cerca un rettangolo secondario che condivida una coppia di lati con quello grande, ma contenga pochissimi punti.
- Ritaglialo da quello grande, producendo due rettangoli più piccoli.
- Ripeti.
Quad
- Dividi il piano in 4 rettangoli. Per ognuno di questi, vedi se ottieni un costo migliore ricorrendo ulteriormente o semplicemente includendo l'intero rettangolo.
- Ora prendi i tuoi rettangoli e vedi se riesci a unirli con pochi / nessun costo. \

Inoltre: tieni a mente che a volte sarà meglio avere due rettangoli sovrapposti rispetto a un rettangolo grande che ne sostituisce uno. Per esempio. il caso in cui due rettangoli si sovrappongono in un angolo.

Ok, la mia comprensione della domanda è cambiata. Nuove idee:

Memorizza ogni riga come una lunga stringa di bit. AND coppie di stringhe di bit insieme, cercando di trovare coppie che massimizzino il numero di 1 bit. Fai crescere queste coppie in gruppi più grandi (ordina e cerca di abbinare tra loro quelle davvero grandi). Quindi costruisci una richiesta che colpirà il gruppo più grande e poi dimenticherai di tutti quei bit. Ripeti fino a quando tutto è fatto. Forse passare da righe a colonne a volte.
Cerca tutte le righe / colonne con zero o pochi punti in esse. & Quot; quot Elimina &; loro temporaneamente. Ora stai esaminando ciò che verrebbe coperto da una richiesta che li esclude. Ora forse applica una delle altre tecniche e in seguito gestisci le righe / i punti ignorati. Un altro modo di pensare a questo è: affrontare prima i punti più densi, quindi passare a quelli più sparsi.

Dato che i tuoi valori sono scarsi, è possibile che molti utenti chiedano valori simili? La memorizzazione nella cache all'interno dell'applicazione è un'opzione? Le richieste potrebbero essere indicizzate da un hash che è una funzione della posizione (x, y), in modo da poter identificare facilmente i set memorizzati nella cache che rientrano nell'area corretta della griglia. La memorizzazione dei set memorizzati nella cache in un albero, ad esempio, consentirebbe di trovare rapidamente sottoinsiemi minimi che coprono l'intervallo di richieste. È quindi possibile effettuare una ricerca lineare sul sottoinsieme, che è piccolo.

Considererei i n record (righe) e i campi p (cols) menzionati nella richiesta dell'utente impostati come n punti nello spazio p-dimensionale ({0,1} ^ p) con la sua coordinata pari a 1 iff esso ha una X e identifica una gerarchia di cluster , con il cluster più grossolano alla radice incluso tutto la X. Per ciascun nodo nella gerarchia del cluster, considerare il prodotto che copre tutte le colonne necessarie (si tratta di righe (qualsiasi nodo secondario) x cols (qualsiasi nodo secondario)). Quindi, dal basso verso l'alto decidere se unire le coperture secondarie (pagando per l'intera copertura) o conservarle come richieste separate. (i rivestimenti non sono di colonne contigue, ma esattamente quelle necessarie; cioè pensa a un po 'di vettore)

Concordo con Artelius sul fatto che la sovrapposizione di richieste di prodotti potrebbe essere più economica; il mio approccio gerarchico avrebbe bisogno di miglioramenti per incorporarlo.

Ci ho lavorato un po 'su, ed ecco un ovvio, avido, algoritmo avido di rottura di simmetria (record e campi sono trattati separatamente) in pseudo-codice simile a python.

L'idea è banale: iniziamo provando una richiesta per record e facciamo l'unione più degna fino a quando non rimane più nulla di degno da unire. Questo algoritmo ha l'ovvio svantaggio di non consentire richieste sovrapposte, ma mi aspetto che funzioni abbastanza bene nel caso della vita reale (con la funzione a + n * (p^b) + c * n * p * (1 - g) costo):

# given are
# a function cost request -> positive real
# a merge function that takes two pairs of sets (f1, r1) and (f2, r2) 
# and returns ((f1 U f2), (r1 U r2))

# initialize with a request per record

requests = [({record},{field if (record, field) is needed}) for all needed records]
costs = [cost(request) for request in requests]

finished = False

while not finished: # there might be something to gain
    maximum_gain = 0
    finished = True
    this_step_merge = empty

    # loop onto all pairs of request
    for all (request1, request2) in (requests x request) such as request1 != request2:
        merged_request = merge(request1, request2)
        gain = cost(request1) + cost(request2) - cost(merged_request)

        if gain > maximum_gain:
            maximum_gain = gain
            this_step_merge = (request1, request2, merged_request)

    # if we found at least something to merge, we should continue
    if maximum_gain > 0:
        # so update the list of requests...
        request1, request2, merged_request = this_step_merge
        delete request1 from requests
        delete request2 from requests
        # ... and we are not done yet
        insert merged_request into requests
        finished = False

output requests

Questo è O (n3 * p) perché:

dopo l'inizializzazione iniziamo con n richieste
il ciclo while rimuove esattamente una richiesta dal pool ad ogni iterazione.
il ciclo interno for scorre le coppie distinte di richieste (ni^2 - ni) / 2, con ni che va da n a una nel peggiore dei casi (quando uniamo tutto in un'unica grande richiesta).
1. Qualcuno può aiutarmi a indicare i casi molto negativi dell'algoritmo. Sembra ragionevole usarlo?
2. È O (n ^ 3) che è troppo costoso per input di grandi dimensioni. Qualche idea per ottimizzarlo?

Grazie in anticipo!

Autorizzato sotto: CC-BY-SA insieme a attribuzione

Non affiliato a StackOverflow