Label the nodes in a tree with their depth as a linear or quadratic problem.

I have a tree made by selecting a few edges out of a graph, in a quadratic programming problem (actually conic).

I would like to assign a variable representing the distance from the root to each node for the given selection of edges.

This has to be done inside the programming problem to minimise an objective, so it must be some set of constraints.

My idea for now is something like this:

Let $a_{ij}$ represent the selection of the link between i and j for the tree as a binary variable, and $d_i$ be the depth of the node i.

$a_{ij}*(d_j-d_i)=1$ would imply that if I select the link ij then the depth of j is 1 more than the depth of i.

The problem is that the graph is undirected, so I don't know if i was actually the node closer to the root, and hence it could be that the depth of i is more than the depth of j.

$a_{ij}*(d_j-d_i)^2=1$ Is no longer quadratic and it also doesn't solve the problem.

What can I do? I was also thinking about some flux based formulation, but no luck for now.

If inequality constraints are allowed, we can “encode” that if the link $ij$ is selected then depths $d_i$ and $d_j$ differs by $1$ by the following inequalities:

$(d_i-d_j)^2\ge a_{ij}$,

$a_{ij}(d_i-d_j)\le 1$,

$a_{ij}(d_j-d_i)\le 1$.

Indeed, if $a_{ij}=0$ then all inequalities hold for arbitrary $d_i$ and $d_j$. But if $a_{ij}=1$ then the first inequality implies $|d_i-d_j|\ge 1$, whereas the other inequalities imply $|d_i-d_j|\le 1$, so $|d_i-d_j|=1$.

• this is a nice idea, but I fear it will not work. let's say that i is the root (depth 0) and j has depth 1 since aij=1. with this set of constraints dj could be either 1 or -1, since it only implies that the difference between the depths is 1. am I wrong? thanks for the answer May 26, 2017 at 10:48
• I just got this idea: using your constraints I could add to my objective function the maximization of the sum of the di. if I pick a really low value for its weight in the multi objective I think it implies that (if I set the root as d=0) the depth will be increasing after each hop (but it also implies the desire to maximise the overall depth of the three, hence the very low weight). what do you think about this approach? it's not really elegant, but if it's the only way.... May 26, 2017 at 10:53
• @user3149593 I’ll think, how we can overcome this obstacle. Indeed, the constraints $|d_i-d_j|=1$ are not sufficient to determine all $d_i$’s. We can also add the constraints that all $d_i$’s are non-negative. Also, because any node of a tree can be selected as its root, I have a question, how we determine the root of the tree? It is some fixed node $i_0$? May 27, 2017 at 14:05
• the root is something I select out of the nodes before running the optimization and set as a constraint for the problem. basically I pick a root and tell my program ''find me a tree with this root compliant with the other constraints''. For now thanks again! May 28, 2017 at 14:28
• you were really clear, now I understood how things work. thanks! my only concern is that $a_ij(d_i−d_j)≤1$ and the other link won't work in gurobi or cplex (I get the error ''Q is not positive definite'') so I'll need to look for another solver. Thanks again for all your help! May 29, 2017 at 21:40