Global optimization of state assignments in a directed graph with a tree-based distance cost

Question

I am exploring a general optimization framework to solve problems characterized by the following structure. Any literature references, search terms, or algorithmic strategies would be greatly appreciated. I aim to unify several algorithms I devised into a more general formulation to gain more control over the optimization criteria.

Given Data

For any optimization instance, the inputs are:

• A set of state numbers, $State$, commonly ranging in size from 2 to 35.
• A tree parentage relationship $Tree \subseteq State \times State$, which forms a rooted tree where every state, except the root, has a single parent. States can have any number of children.
• A directed graph $G = (V,E)$, specifically a control flow graph derived from source code. This graph is not always fully connected. Let $preds(v) = \{ p \mid (p,v) \in E \}$ denote the predecessors of a vertex $v$. The number of vertices $|V|$ is typically a few hundred.
• A partial assignment $Asg_{partial} \subseteq V \hookrightarrow State$, indicating that certain vertices are mandatorily assigned to specific states.

Derived Functions

From $Tree$, we derive:

• $transit_2(s_1, s_2) : State \times State \rightarrow \mathscr{P}(State)$, a symmetric function that returns the set of all states on the tree path from $s_1$ to $s_2$. It is equivalent to $transit_2(s_1, anc) \cup transit_2(s_2, anc)$, where $anc$ is the lowest common ancestor of $s_1$ and $s_2$.
• $transit_{\mathscr{P}}(S) : \mathscr{P}(State) \rightarrow \mathscr{P}(State)$, which extends $transit_2$ to a set of states. It represents the union of all tree nodes on all paths to their mutual common ancestor for the given set of states.

Optimization Goal

The goal is to extend $Asg_{partial}$ to a total function $Asg$, assigning states to all vertices while respecting the constraints set by $Asg_{partial}$. For any vertex $v$ pre-specified by $Asg_{partial}$, it must hold that $Asg(v) = Asg_{partial}(v)$. For all other vertices, $Asg$ should be chosen to minimize:

$TotalScore(Asg) = \sum_{v \in V} score_{Asg}(v)$

where

$score_{Asg}(v) = |transit_{\mathscr{P}}(Asg(v) \cup \bigcup_{p \in preds(v)} Asg(p))|$

This score represents the number of tree states that must be transited by all predecessors of $v$, in combination, en route to $v$.

Important Notes

This is distinct from minimizing the sum of the individual edge scores $\sum_{p \in preds(v)} |transit_2(Asg(p), Asg(v))|$ because the score function for a vertex depends on all its predecessors collectively. For example, if $Asg$ assigns $v$ to the same state $s$ as both its predecessors $p_1$ and $p_2$, then:

$score_{Asg}(v) = |\{s\}| = 1$

while treating the edges independently would yield:

$|\{s\}| + |\{s\}| = 2$

Alternative Conception

You could also think of the problem as embedding $G$ into $Tree$: that is, associating a set $V_{State} \subseteq V$ with each $State$. Then the score for each vertex $v$ would be the total cardinality of all $Tree$ nodes traversed by the predecessor edges incident to $v$, which we want to minimize globally by placing vertices and their predecessors as close as possible.

Additional Context

In my actual instances, vertices are numbered, and sequentially adjacent numbers frequently share the same state. My algorithms exploit this to consider states of groups of vertices at a time rather than every vertex independently. This detail is omitted above for simplicity, and because I was interested in more generalized approaches to the problem.

Per the first answer given below, it makes sense to clarify that the algorithm needs to be deterministic, and if possible, run in polynomial time. (The latter might be difficult without making use of the extra structure mentioned in the previous paragraph. This extra structure also gives an initial $Asg$: each vertex is assigned to the state of the next lower-numbered vertex whose state is dictated by $Asg_{partial}$.)

Requests

I welcome all algorithmic strategies, literature recommendations, and insights. Thank you for your time and assistance!

Answer 1

One approach is to use the big guns, i.e., a SAT solver or ILP (integer linear programming) solver. You could implement both and see if either is satisfactory for problems of the size you are dealing with. I don't know whether there is a more efficient algorithm.

Reducing to SAT

For instance, you can express this in SAT as follows. Introduce the following boolean variables. Let $x_{v,s}$ be true if $Asg(v)=s$. Let $\alpha_{v,s}$ be true if $s$ is in the subtree of states rooted at the lowest common ancestor of $Asg(v) \cup \bigcup_{p \in preds(v)} Asg(p)$. Let $\beta_{v,p,s}$ be true if $s$ is an ancestor of $Asg(p)$ (we treat each state as an ancestor of itself), for $p \in preds(v) \cup \{v\}$, and let $\gamma_{v,s}=\beta_{v,v,s} \lor \bigvee_{p \in preds(v)} \beta_{v,p,s}$. Let $y_{v,s}$ be true if $s \in transit_{\mathscr{P}}(Asg(v) \cup \bigcup_{p \in preds(v)} Asg(p))$.

Then we can enforce the variables to have the aforementioned relationships by introducing a bunch of constraints (clauses):

• "$Asg$ is a function": for each $v$, exactly one of $x_{v,s}$ is true.

• "$Asg$ is consistent with the partial assignment": for each $v$ that is assigned a value under $Asg_{partial}$, we enforce $x_{v,Asg_{partial}(v)}$ is true.

• "$\alpha_{v,s}$ represents a subtree": for every $v,s,s'$ such that $s$ is a parent of $s'$, $\alpha_{v,s} \implies \alpha_{v,s'}$.

• "$\alpha_{v,s}$ is a common ancestor": $x_{v,s} \implies \alpha_{v,s}$ and for each $p \in preds(v)$, $x_{p,s} \implies \alpha_{v,s}$.

• "$\beta_{v,p,s}$ includes all ancestors of $Asg(p)$": $x_{p,s} \implies \beta_{v,p,s}$ and $\beta_{v,p,s'} \implies \beta_{v,p,s}$ for all $p \in preds(v) \cup\{v\}$ and all children $s'$ of $s$.

• "$\gamma_{v,s}$ includes all relevant states": $\beta_{v,p,s} \implies \gamma_{v,s}$ for all $p \in preds(v) \cup \{v\}$.

• "$y_{v,s}$ includes all the relevant states": $(\alpha_{v,s} \land \gamma_{v,s}) \implies y_{v,s}$.

Notice that all of these can be expressed as CNF clauses, so the boolean formula can be obtained as a conjunction of all of these clauses.

Finally, the goal is to find an assignment that satisfies this formula and minimizes the number of $y$-variables set to true. One way to do this is to pick an integer $k$, add the constraint that at most $k$ of the $y'$ are true, and test whether the resulting formula is satisfiable. Then, use binary search on $k$ to find the smallest $k$ such that this formula is satisfiable.

This requires you to be able to express "exactly 1-out-of-$n$" and "at most $k$-out-of-$n$" constraints in SAT (the former for the $x$'s, the latter for the $y$'s). This can be done using the methods in Encoding 1-out-of-n constraint for SAT solvers, Reduce hitting set to SAT, and cardinality constraints, Can a propositional threshold connective be expressed by standard connectives?. Or, better yet, some SAT/SMT solvers provide a built-in way to express these constraints. Typically these are called "pseudo-boolean constraints". See, e.g., https://stackoverflow.com/q/43081929/781723.

Therefore, one plausible approach to your problem would be to reduce it to SAT, use the Z3 SMT solver (together with its built-in support for pseudo-boolean constraints), and have it search for the best solution.

Reducing to ILP

Another plausible approach is to use an ILP solver. Each variable is either 0 or 1, instead of being either false or true. ILP solvers provide built-in-support for pseudo-boolean constraints (each one is just a single linear equality or linear inequality, which is natively supported). Each implication is also trivial to express as ILP; $x \implies y$ is translated to $x \le y$, and $(x \land y) \implies z$ is translated to $x+y-1 \le z$. Your goal to minimize the (linear) objective function $\sum_{v,s} y_{v,s}$, which ILP solvers support natively.

This should be enough to express your problem as an instance of ILP, and then apply an off-the-shelf ILP solver.

Simplified ILP formulation

After further thought, I can suggest a simpler formulation as an ILP problem:

• "$Asg$ is a function": for each $v$, exactly one of $x_{v,s}$ is 1, i.e., $\sum_s x_{v,s}=1$.

• "$Asg$ is consistent with the partial assignment": for each $v$ that is assigned a value under $Asg_{partial}$, we enforce $x_{v,Asg_{partial}(v)}=1$.

• "$y$ has the correct shape": for each triple $s,t,u$ of states such that $s \le u \le lca(s,t)$ and $t \le u \le lca(s,t)$, we enforce $(y_{v,s} \land y_{v,u})\implies y_{v,t}$, i.e., $y_{v,s}+y_{v,u}-1 \le y_{v,t}$. Here I write $lca(s,t)$ for the lowest common ancestor of $s,t$, and $s \le u$ if $u$ is an ancestor of $s$ (this includes the possibility that $s=u$).

• "$y$ is consistent with $x$": for each $v,s$ and $p \in preds(v)$, we have $x_{v,s} \le y_{v,s}$ and $x_{p,s} \le y_{v,s}$.

Finally, we minimize $\sum_{v,s} y_{v,s}$. This is an ILP instance with approximately $|State| \times |V|$ zero-or-one variables and about $|State|^2 \times |V|$ inequalities.

(Of course this can also be expressed as SAT/SMT and solved using MAX-SAT or binary search with pseudo-boolean constraints. I expressed it as ILP because it is particularly simple and clean to express in ILP.)

Warm starts

You mentioned that you have a greedy heuristic that often gives you an optimal solution. Some ILP solvers allow a way to provide a warm start, i.e., to suggest an initial assignment that is feasible, and ask the ILP solver to try to improve on it. This might be called a "warm start" or "MIP start". Also, you might be able to specify a timeout, and ask the solver to give you the best solution found so far when it reaches the timeout. I don't know whether this will help.

For more about starting values, see, e.g., https://or.stackexchange.com/q/7361/2415, https://www.gurobi.com/documentation/current/refman/start.html, https://yalmip.github.io/warmstart, https://coin-or.github.io/pulp/guides/how_to_mip_start.html.

Determinism

Some solvers might have built-in support for deterministic solving. See, e.g., https://support.gurobi.com/hc/en-us/articles/360031636051-Is-Gurobi-deterministic, https://www.ibm.com/docs/en/icos/12.9.0?topic=interface-determinism-timing, https://stackoverflow.com/q/71188150/781723.

Answer 2

You should look into some quantum optimization methods that can be derived through matrice representation.