0
$\begingroup$

Given something similar to this.

enter image description here

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:

enter image description here

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.

enter image description here

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.

$\endgroup$
8
  • $\begingroup$ @Nathaniel I state: "And the best path is the one with a value (sum of blocks) equal, above or closest to the entry desired value." I'll edit to clarify it. $\endgroup$
    – ikerdc
    Nov 29, 2022 at 10:30
  • $\begingroup$ @Nathaniel yes you are correct. I would like to minimize the maximum deviation of ALL the entries. I have made and edit with a formula that reflects this. $\endgroup$
    – ikerdc
    Nov 29, 2022 at 10:45
  • $\begingroup$ @Nathaniel my bad, the comment is not correct. It should minimize the sum of deviations. $\endgroup$
    – ikerdc
    Nov 29, 2022 at 10:54
  • $\begingroup$ 1. I don't understand how you define how much an entry receives, given a set of edges. 2. What is N? Is it an input? 3. What are the dashed/dotted edges? Are they provided as part of the input? 4. Can one input be assigned to two or more entries? 5. What do you mean by path? I don't see how paths are relevant, only the assignment between blocks and entries. $\endgroup$
    – D.W.
    Nov 29, 2022 at 16:30
  • $\begingroup$ 6. It seems like you have multiple objectives you are simultaneously trying to minimize. In general, that is not possible. How do you want to combine all of those deviations for each entry into a single objective function to minimize? 7. Can you describe the context in which you encountered this task, or the motivation, in the question? $\endgroup$
    – D.W.
    Nov 29, 2022 at 16:30

1 Answer 1

0
$\begingroup$

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).

$\endgroup$
2
  • $\begingroup$ Hmm I see.. Thanks for the answer! (I would upvote it, but I don't have enough reputation yet.) $\endgroup$
    – ikerdc
    Nov 29, 2022 at 13:02
  • $\begingroup$ @ikerdc you can still accept it if it satisfies you! $\endgroup$
    – Nathaniel
    Nov 29, 2022 at 14:07

Your Answer

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

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