Realizzare come proprietario di un negozio di alta dimensione?

Question

Ho pensato a un problema di recente e mi chiedo se qualcuno può commentare alcune idee per rendere più efficienti soluzioni a questo problema.

---

Diciamo che sono un imprenditore con un set di $ n $ possibili posizioni dei negozi $ L = lbrace x_i in mathbb {r}^m rbrace_ {i = 1}^n $, per $ m> 1 $, dove vorrei costruire alcuni nuovi negozi. Ho stima che ogni posizione $ x_i $ costerà $ c_i $ costruire e dovrebbe realizzare un profitto corrispondente $ p_i $ Dopo l'apertura. Inoltre, ho un budget di $ B $ che non posso superare e tutti i negozi che costruisco devono essere almeno una distanza $ D $ lontano l'uno dall'altro in base alla metrica $ d ( CDOT, CDOT) $. Il mio obiettivo è quello di costruire negozi in modo tale da massimizzare il mio profitto e rimanere entro i vincoli desiderati. Notare che $ (L, d) $ è uno spazio metrico.

Definire $ S = (S_1, S_2, CDOTS, S_N) in lBrace 0, 1 rbrace^n $ tale che $ s_i = 1 $ significa che sto costruendo un negozio in posizione $ i $ e $ s_i = 0 $ significa che non lo sono. È chiaro che questo problema di ottimizzazione può essere posto come:

inizio {align*} & && max_ {s in lbrace 0, 1 rbrace^n} sum_ {i = 1}^n p_i s_i tag*{} & text {soggetto a} && ; end {align*}

---

Ora, quando si guarda a questo problema, è abbastanza semplice risolverlo usando una programmazione dinamica se supponiamo che le posizioni del negozio siano abbastanza lontane da quanto il vincolo di distanza sia automaticamente soddisfatto o che le posizioni sono tutte contenute in un sottospazio affine 1-dimensionale. Al di fuori di questo, le cose sembrano un po 'complicate.

Il mio pensiero è inizialmente costruire un grafico $ G = (v, e) $ tale che $ V (g) = lbrace 1, CDOTS, n rbrace $ e $ E (g) = lbrace ij ; | ; d (x_i, x_j) geq d rbrace $. Da qui, un'idea semplice ma inefficiente è quella di elencare tutte le cricche di $ G $, Risolvili usando una programmazione dinamica e scegli la soluzione, su tutti loro, è la migliore. Questo dovrebbe andare bene perché ogni cricca, per costruzione, è composta da posizioni dei negozi che soddisfano i vincoli di distanza e, a loro volta, dovrebbero consentire individualmente soluzioni efficienti. Questo potrebbe essere formalizzato definendo $ lBrace C_1, C_2, CDOTS, C_P rBrace = text {cliques} (g) $ come l'insieme di cricche di $ G $ e poi risolvere

inizio {align*} & && max_ {s^{(j)} in lbrace 0, 1 rbrace^n} sum_ {i = 1}^n p_i s_i^{(j)} tag* {} & text {soggetto a} && sum_ {i = 1}^n c_i s_i^{(j)} leq b & && s_i^{(j)} = 0 hspace {1cm} i in v (g) setminus v (c_j) end {align*}

per ciascuno $ j^{th} $ cricca $ C_j $. Da qui, quindi scegliamo $ S^* = arg max_ {j in lBrace 1, CDots, p rbrace} sum_ {i = 1}^n p_i s_i^{(j)} $ come soluzione ottimale per il problema generale.

---

Ovviamente la cosa schifosa dell'approccio di cui sopra è che dobbiamo elencare tutte le cricche, che possono essere sia un set di grandi dimensioni che che la computazionalmente richiede da trovare. C'è qualche struttura nel problema che mi manca che potrebbe rendere questo risolvibile senza elencare tutte le cricche in questa formulazione? Forse c'è una prospettiva diversa che potrebbe far luce?