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