0
$\begingroup$

The following a small-scale example meant to illustrate the general problem

Suppose we have $n = 60$ marbles that we want to distribute into 3 bowls, $B = \{bowl_1, bowl_2, bowl_3\}$

The marbles can take the distinct colors $C = \{red, yellow, blue, green\}$ where we have: $n_{red} = 15$, $n_{yellow} = 10$, $n_{blue} = 20$, and $n_{green} = 15$. The bowls have the marble capacities: $c_1 = 15$, $c_2 = 20$, and $c_3 = 25$.

The general distribution of marbles into bowls can be formulated as max flow problem via the flow network below, marble colors are the nodes (R), (Y), (B), and (G), while the bowls are the nodes (1), (2), (3).

Now, we introduce the additional objective that the number of distinct colors in each bowl - summed over all bowls - should be minimized.

This corresponds to minimizing the sum of the in-degrees of nodes (1), (2), and (3) - counting only the incoming edges with non-zero flow.

I attempt to formalize the objective function to minimize, where $1_{f(color,bowl)>0}(f)$ is an indicator function of non-zero flow for a given flow $f$ in the flow network. $Obj(f) = \sum_{bowl \in B} \sum_{color \in C}(1_{f(color,bowl)>0}(f))$

Is there a general approach for solving this kind of problem?

enter image description here

$\endgroup$
4
  • $\begingroup$ The objective is not clear. What if you can't simultaneously minimize the in-degree of all the nodes of interest? Perhaps you interested in minimizing the sum or the maximum of these in-degrees? $\endgroup$
    – Steven
    Sep 27, 2023 at 13:52
  • $\begingroup$ Have you tried to formulate it as an LP? $\endgroup$
    – Pål GD
    Sep 27, 2023 at 14:10
  • $\begingroup$ For multiple commodities with integer flows, the problem is possibly NP-hard. Check out the Multi-commodity circulation problem. $\endgroup$
    – Pål GD
    Sep 27, 2023 at 14:11
  • $\begingroup$ Thanks for the suggestions, I will look into LP and the Multi-commodity circulation problem $\endgroup$
    – silass0
    Sep 29, 2023 at 7:54

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.