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

The inverse max+sum spanning tree problem is considered by modifying the sum-cost vector under weighted l1<inline-graphic></inline-graphic> 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∈E<inline-graphic></inline-graphic>. The max+sum spanning tree (MSST) problem is to find a spanning tree T∗<inline-graphic></inline-graphic> which makes the combined weight maxe∈Tw(e)+∑e∈Tc(e)<inline-graphic></inline-graphic> as small as possible. It can be solved in O(mlogn)<inline-graphic></inline-graphic> time, where m=|E|<inline-graphic></inline-graphic> and n=|V|<inline-graphic></inline-graphic>. Whereas, in an inverse MSST problem, T0<inline-graphic></inline-graphic> is a given spanning tree of G, which is not an optimal MSST. The sum-cost vector c is to be modified to c¯<inline-graphic></inline-graphic> so that T0<inline-graphic></inline-graphic> becomes an optimal MSST of the new network G(V,E,c¯,w)<inline-graphic></inline-graphic>. The goal is to minimize the modification cost ‖c¯-c‖1<inline-graphic></inline-graphic> incurred by adjusting the sum-cost vector under weighted l1<inline-graphic></inline-graphic> norm. The inverse MSST problem under weighted l1<inline-graphic></inline-graphic> 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 c~<inline-graphic></inline-graphic>. 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. [ABSTRACT FROM AUTHOR]