0
$\begingroup$

The situation is :

There are n bulbs and m power sources. The j-th power source has a failure probability of $P_j$. Each bulb is connected to 3 power sources, and only $\frac{3n}{m}$ bulbs can be connected to one power source. When all the power sources connected to the bulb fail, the bulb fails. How to connect to minimize the expectation of the failure bulb.

Let $x_{ij}$ indicts whether bulbs i connects to power source j. This problem can be modeled as 0-1 integer programming easily:

the constraint is $\sum_{j}x_{ij}=3$ for any i and $\sum_{i}x_{ij}=\frac{3n}{m}$ for and m. Minimize the function $E=\sum_i(1-\prod_j(1-P_j)^{x_{xj}})$

But as the parameters can be pretty large, such as n=1000000 ,m=1000，it may take a lot of time to solve it.

Now suppose $P_i$ has only a few cases, such as $P_i\in\{0.2,0.5,0.7\}$. Considering all variables now having high substitutability, can we simply the model?

$\endgroup$
5
  • $\begingroup$ Is $3n/m$ assumed to be integer? So power sources are connected to the same number of bulbs. What model did you came up with? $\endgroup$ Commented Sep 28, 2024 at 8:15
  • $\begingroup$ @ caduk yes. the constraint is :$\sum_{j}x_{ij}=3$ for any i and $\sum_{i}x_{ij}=\frac{3n}{m}$ for any j. Minimize the function $E=\frac{\sum_{i}(1-\prod_{j}(1-P_j)^{x_{ij}})}{n}$ $\endgroup$ Commented Sep 28, 2024 at 20:51
  • $\begingroup$ Your expectation seems to have reversed $i$ and $j$, and why divide by $n$? $\endgroup$ Commented Sep 28, 2024 at 20:57
  • $\begingroup$ @RobPratt sorry my fault., I'm discussing with my roommate in a similar situation while writing it . i and j should be reversed and have to remove n. $\endgroup$ Commented Sep 30, 2024 at 6:50
  • $\begingroup$ Please add the constraints and corrected objective from your comments into your question. $\endgroup$ Commented Sep 30, 2024 at 12:48

0

Reset to default

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.