Algorithm to distribute group of connected nodes in a graph

Question

Given something similar to this.

Where you have blocks (the squares) and entries (the circles). Each block has a rating (the number inside the blocks) and is connected to other blocks. This topology is always fixed and cannot change, the ratings neither.

An entry can ask for a given rating. The algorithm then should try to assign N connected blocks to that entry so the rating provided is above or as close as possible to what the entry requires. It needs to be considered that the block to which the entry is 'conected' will always be asigned to him. An example:

We have two entries requiring a limit (green and blue entry). Green requires 300, and he receives 300 (3 blocks of 100 assigned to him), while blue asks for 275 and receives 250 (125+75+25). This solution is the optimal one; deviations are of all entries are minimized. Green has |1-(300/300)|=0 and blue |1-(250/275)|=0.09.

Mind that the third entry is not active, so his 'entry block' can be used by another entry group of asigned blocks. If we activate the third entry and require 200 as follows.

Note that the optimum solution changes. Green cannot use the 'entry block' from orange (as orange is connected).

The algorithm should assign to each entry the best possible connected path, taking into account the other paths too. And the best path is the one with a value (sum of blocks) equal, above or closest to the entry desired value.

The algorithm should output the solution that minimizes the deviation |1-(recived/required)| in each entry. In other words, the blocks assigned to each entry such that the rating received per entry is the closest to the desired value (for all the entries combined).

minimize: |1-(recived_1/required_1)| + |1-(recived_2/required_2)| + ...

• What could be an algorithm to solve such a problem. I am quite sure it involves linear/constraint programming. But I cannot see a clear way of doing it.

Edit: Context of question: Circles are EV charge stations, the squares are energy blocks connect between each other. When a car is connected to a station, the car requires some energy to charge (in the diagram, they ask for 300kW, 250kW and 200kW), and the blocks have ratings of 125kW, 100kW, 100kW, ... The algorithm has to say which group of power blocks go to which station. Aiming at satisfing as much as possible every car (i.e. kW provided by the sum of blocks is closest to how much kW the car wants, i.e the value in the circles in the diagram).

In real life, each edge has a contactor, it is either opened or closed to drive the energy of the blocks to the stations (but this can be ignored, knowing which blocks go to which station is enough). The doted line is the acces connection of the station to the networks of blocks. If the station has a car charging, the block to which the station is conected (doted line) will always be closed (i.e. that block assigned to him). This way every station when active has at least one block asigned so the car can charge.

Answer 1

I think the problem might be $\mathsf{NP}$-difficult. Consider the decision version:

Input: an undirected graph $G = (V, E)$, a value function $f:V\to \mathbb{N}$, a subset $E = \{e_1, …, e_m\} \subseteq V$ of entries, vertices of degree $1$ and a rational $q$.

Question: does there exists $m$ disjoint paths $p_1,…,p_m$, each $p_i$ starting in $e_i$, such that $\sum\limits_{i=1}^n\left|1-\frac{f(e_i)}{f(p_i-e_i)}\right|\leqslant q$, where $f(p_i-e_i) = \sum\limits_{\substack{v\in p_i\\v\neq e_i}}f(v)$?

Here is a reduction from $\texttt{Hamiltonian Undirected Path}$. Consider an undirected graph $G = (V, E)$. Construct a graph $G' = (V', E')$ where:

• $V' = V\cup \{e, b\}$ (add one block and one entry);
• $E' = E \cup \{\{e, b\}\} \cup \{\{b, v\}\mid v\in V\}$ (add one edge between the block and each other vertex, entry included).

Define $f$ such that $f(v) = 1$ if $v\in V$, $f(b) = 0$ and $f(e) = |V|$. Define $E = \{e\}$ and $q = 0$.

Then there exists a Hamiltonian path in $G$ if and only if $(G', f, E, q)$ is a positive instance of the problem. The idea is that to create a path of sum $f(e)$, there needs to exist a path crossing each vertex once.

For this reason, your problem is difficult to solve (though I do not know about approximations).