Inverse max+sum spanning tree problem under weighted $$l_1$$ norm by modifying the sum-cost vector

The inverse max+sum spanning tree problem is considered by modifying the sum-cost vector under weighted \(l_1\) norm. On an undirected network G(V, E, c, w), a cost c(e) and a weight w(e) are prescribed for each edge \(e\in E\). The max+sum spanning tree (MSST) problem is to find a spanning tree \(T^*\) which makes the combined weight \(\max _{e\in T}w(e)+\sum _{e\in T}c(e)\) as small as possible. It can be solved in \(O(m\log n)\) time, where \(m=|E|\) and \(n=|V|\). Whereas, in an inverse MSST problem, \(T_0\) is a given spanning tree of G, which is not an optimal MSST. The sum-cost vector c is to be modified to \(\bar{c}\) so that \(T_0\) becomes an optimal MSST of the new network \(G(V,E,\bar{c},w)\). The goal is to minimize the modification cost \(\Vert \bar{c}-c\Vert _1\) incurred by adjusting the sum-cost vector under weighted \(l_1\) norm. The inverse MSST problem under weighted \(l_1\) norm can be formulated as a linear programming problem with exponential number of constraints. Then a column generation algorithm is proposed to solve its dual problem. It is extremely interesting that in each iteration the choice of entering variable can be determined by solving an MSST problem with new sum-cost \(\tilde{c}\). Computational experiments show that the column generation algorithm can find the optimal solutions of the inverse problem although the number of iterations as well as the running time grow fast with the increase in the size of the instance.