3
$\begingroup$

Let's say I have 3 type of sensors: A, B, C. These sensors can be connected to multiple devices at the same time: let's call them dA, dB and dC. Now, device dA can only accept connections of sensor of type A. Device dB can only accept connections of sensor of type A and B. Device dC can only accept connections of sensors of type C. One sensor can be connected to multiple devices. Every device must have one sensor (and no more) connected to it. The number of sensors can be smaller than the number of devices.

What's the best way to find a general solution in polynomial time (if possible!) for a problem like this? Please tell me if I have explained the problem in a clear manner.

$\endgroup$
  • $\begingroup$ Do you need an optimal solution in polynomial time, or just a feasible solution of good quality? $\endgroup$ – dhasson Sep 14 at 20:03
  • $\begingroup$ What are you trying to optimize? An example objective is that you prefer to connect not more than a certain number of devices to the same sensor. $\endgroup$ – batwing Sep 14 at 21:45
  • $\begingroup$ Paragraphs would make this monolithic question much easier to understand. $\endgroup$ – Ray Butterworth Sep 15 at 0:32
  • $\begingroup$ @dhasson A solution in polynomial time would be perfect, as this is a real life problem but also a learning experience for me. $\endgroup$ – Marco Sep 15 at 18:21
3
$\begingroup$

@prubin assumed that the sensors are not "setup" yet, and that setting them up yields a fixed cost, for each sensor.

If the sensors are already in place (this is not clear in the question), then you just want to assign devices to sensors, which you can model as a min cost flow problem. Just add a Source node and link it to all the sensors, a Sink node which is linked to all devices. And add an edge with infinite capacity from nodes of type $A$ ($B,C$) to all devices of type $dA$ ($dB,dC)$. And then impose that the flow from the devices to the Sink must equal $1$ exactly.

Since the graph is bipartite, it can be solved in polynomial time.

| improve this answer | |
$\endgroup$
  • $\begingroup$ This seems to be the most promising solution for sure. Thanks a lot. $\endgroup$ – Marco Sep 15 at 18:31
2
$\begingroup$

I'm going to assume that (a) you want to minimize the number of sensors used and (b) there is no limit to the number of devices to which one sensor can be connected. (The second assumption seems shaky to me, but you did not mention a limit.) Under those assumptions, your problem can be reduced to an uncapacitated facility location problem (UFLP), in which each sensor type is a "facility", each device is a "customer", customers (devices) can only be assigned to compatible facilities (sensor types), and the objective is to minimize the number of facilities (sensor types). Given a solution, you just install one sensor of each selected type and hook it to the devices specified by the solution. This can be easily modified to minimize the cost of the selected sensors, if different types have different costs.

I'm pretty sure the UFLP is NP-hard, and since your problem is equivalent to it, that should mean no polynomial time exact solution is possible.

If you have a limit on how many devices one sensor can support, you can tweak the model to make it a capacitated FLP by allowing a predefined number of sensors of each type (for instance five type A sensors, assuming that five would be enough to handle every type A-compatible device). You might want to throw in some antisymmetry constraints to improve model solution time.

Polynomial time heuristics can of course be cobbled together, with no guarantee of optimality.

| improve this answer | |
$\endgroup$
  • $\begingroup$ Both assumptions are valid. There's no real "cost" to connecting the sensor. Thanks a lot for the input. $\endgroup$ – Marco Sep 15 at 18:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.