I am trying to solve this branch and bound problem but I could not come up with any approximate cost function which is better than the cost.

Let's say $G$ is a graph of $n$ nodes $\{1, 2, 3, \ldots , n\}$. For a permutation $f$ of the nodes of $G$, the weight of each edge $(x,y)$ will be $|f(x)-f(y)|$. The total weight of $G$ will be the sum of the weights of its edges. You can think of $f$ as a relabeling of the nodes of $G$, where $f(x)$ is the new label of node $x$.

I am trying to find a permutation $f$ that results in a minimum total weight of $G$.

Now trying to solve this, all I could come up with is finding the approximate cost that is the sum of weights of each edge completed till now (for each backtracking tree node) and proceed from the minimum cost node. I am wondering if someone can help me with a better approximation formula.

  • 1
    $\begingroup$ Alternative formulation: to arrange the vertices in such way that, in the adjacency matrix, most 1s are near the diagonal. $\endgroup$ Nov 27, 2016 at 9:34
  • 1
    $\begingroup$ Perhaps $7$ years later this problem is of no interest to you, but perhaps other people may be interested in reading this master thesis by Michael Zündorf. $\endgroup$ Feb 19 at 10:20

1 Answer 1


One of the best solution is likely based on a linear programming relaxation or direct integer programming. For the latter, the branching and backtracking will be implicit, and you won't have to manage it yourself.

I have seen it solved in two ways using this technique. We can slightly improve your bounding algorithm as well.

The textbook method

Using binary variables $x_{ij}$ representing $f(i) = j$, you can define continuous variables $f(i) = \sum_{j=1}^n j x_{ij}$

Add constraints $\sum_i x_{ij} = 1$ and $\sum_j x_{ij} = 1$ representing that one position is assigned one and only one node.

For each edge, the cost $c_e$ has two constraints : $c_e \geq f(i) - f(j)$ and $c_e \geq f(j) - f(i)$, and you want to minimize $\sum_e c_e$

You can give this problem to an integer programming solver, which will be happy to do the backtracking for you and more - or you can solve the linear programming relaxation yourself each time (just if you want to learn, the solver optimizes it internally).

Another relaxation

Instead of using the positions as binary variables, you can use $f(i) < f(j)$ i.e. node $i$ goes before node $j$. This is more adapted if you want to do the branching yourself and don't specify those variables explicitly.

With this approach, you can sometimes have a faster problem to solve at each node - here it can be solved as a simpler minimum-cost flow problem as shown by this paper. I wouldn't recomment it unless you are willing to investigate much time and research into your problem.

Other techniques

For branch-and-bound, any lower bound on your cost function will do. For small problems your bounding approach is perfectly fine.

You could make it tighter: for each edge with an unplaced node, pick the best possible free labeling to estimate its cost. Several edges may use the same placement for different nodes, but this will be better than estimating their cost as 0.

There are many possible variations on this scheme: pick the best free label for each unlabeled node (irrespective of overlaps) or consider overlaps only inside small groups of nodes.


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.