Faire un profit en tant que propriétaire de magasin de grande dimension?

Question

J'ai pensé à un problème récemment et je me demande si quelqu'un peut commenter certaines idées pour rendre les solutions à ce problème plus efficaces.

---

Disons que je suis un propriétaire d'entreprise avec un ensemble de $ n $ Emplacements de magasin possibles $ L = lbrace x_i in mathbb {r} ^ m rbrace_ {i = 1} ^ n $, pour $ m> 1 $, où j'aimerais construire de nouveaux magasins. J'ai des estimations que chaque emplacement $ x_i $ coûtera $ c_i $ construire et devrait réaliser un bénéfice correspondant $ p_i $ Après ouverture. De plus, j'ai un budget de $ B $ que je ne peux pas dépasser et que tous les magasins que je construisent doivent être au moins une distance $ D $ loin les uns des autres en fonction de la métrique $ d ( cdot, cdot) $. Mon objectif est de construire des magasins de telle sorte que je maximise mon profit et que je reste dans les contraintes souhaitées. Notez que $ (L, d) $ est un espace métrique.

Définir $ S = (s_1, s_2, cdots, s_n) in lbrace 0, 1 rbrace ^ n $ tel que $ s_i = 1 $ signifie que je construis un magasin à l'emplacement $ i $ et $ s_i = 0 $ signifie que je ne le suis pas. Il est clair que ce problème d'optimisation peut être présenté:

begin {aligner *} & && max_ {s in lbrace 0, 1 rbrace ^ n} sum_ {i = 1} ^ n p_i s_i tag * {} & text {soumis à} && sum_ {i = 1} ^ n c_i s_i leq b & && d (x_j, x_i) geq d hspace {1cm} forall j> i geq 1 text {where} s_i = s_j = 1 end {align *}

---

Maintenant, lorsque vous regardez ce problème, il est assez simple de le résoudre en utilisant la programmation dynamique si nous supposons que les emplacements des magasins sont suffisamment éloignés pour que la contrainte de distance soit automatiquement satisfaite ou si les emplacements sont tous contenus dans un sous-espace affine à 1 dimension. En dehors de cela, les choses semblent un peu compliquées.

Ma pensée est de construire initialement un graphique $ G = (v, e) $ tel que $ V (g) = lbrace 1, cdots, n rbrace $ et $ E (g) = lbrace ij ; | ; d (x_i, x_j) geq d rbrace $. De là, une idée simple mais inefficace est d'énumérer toutes les cliques de $ G $, résolvez-les en utilisant la programmation dynamique et choisissez la solution, à travers toutes, c'est la meilleure. Cela devrait être bien car chaque clique, par construction, est composée d'emplacements de magasin qui satisfont les contraintes de distance et devraient à leur tour permettre individuellement des solutions efficaces. Cela pourrait être formalisé en définissant $ lbrace c_1, c_2, cdots, c_p rbrace = text {cliques} (g) $ comme l'ensemble des cliques de $ G $ puis résoudre

begin {aligner *} & && max_ {s ^ {(j)} in lbrace 0, 1 rbrace ^ n} sum_ {i = 1} ^ n p_i s_i ^ {(j)} tag * {} & text {soumis à} && 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 *}

pour chaque $ j ^ {th} $ clique $ C_j $. De là, nous choisissons ensuite $ S ^ * = arg max_ {j in lbrace 1, cdots, p rbrace} sum_ {i = 1} ^ n p_i s_i ^ {(j)} $ comme solution optimale pour le problème global.

---

De toute évidence, la chose merdique à propos de l'approche ci-dessus est que nous devons énumérer toutes les cliques, ce qui peut être à la fois un grand ensemble et une exigeant de calcul. Y a-t-il une structure au problème qui me manque qui pourrait rendre cette résolution sans énumer toutes les cliques de cette formulation? Peut-être y a-t-il une perspective différente qui pourrait faire la lumière?