A Class Of Inverse Optimal Value Problems On Minimum Spanning Tree

The minimum spanning tree problem is an important research direction in combinatorial optimization,which is widely used in transportation,communication and other networks.We mainly consider the inverse optimal value problem on minimum spanning tree(IOVMST),which can be described as follows.Given a weighted connected undirected network G=(V,E,ω,c0)and a spanning tree T0,we aim to modify the weights of the edges from ω to ωsuch that T0 is not only the minimum spanning tree under the new weight ω but also the weight w(T0)of T0 is equal to a given value K(K<ω(T0)),the objective is to minimize the weighted modification cost c0‖ω-ω‖ under a certain norm.We mainly focus on the inverse optimal value problems under the weighted bottleneck Hamming distance(IOVMSTBH)and weighted l∞ norm(IOVMST∞ω),whose objective functions are(?)c0iH(ωi,ωi)and(?)ci0|ωi-ωi|,respectively.Under the weighted bottleneck Hamming distance,l,u are the lower bound vector and upper bound vector on the modification of weights,respectively.Suppose l=-∞,u=+∞in the unbounded problem(IOVMSTBH),l>-∞,u=+∞ in the lower bounded problem(LIOVMSTBH)and l>-∞,u<+∞ in the capacitated problem(CIOVMSTBH).In this paper,we present three mathematical models of these three inverse problems,analyze their properties and design corresponding algorithms.The vector c is obtained by deleting the same elements from c0 and sorting them in an ascending order.For the unbounded problem(IOVMSTBH),given a ck,we firstly define the subproblem(IOVMSTBH(ck))of(IOVMSTBH),whose objective value is no more than ck.If the subproblem(IOVMSTBH(ck))has no feasible solution,which indicates the optimal value is greater than ck;Otherwise,we give a feasible solution to the subproblem(IOVMSTBH(ck)).For the lower bounded problem(LIOVMSTBH),the sufficient and necessary condition for a feasible solution is that l(T0)≤K.An optimal solution of the problem(LIOVMSTBH)is given when l(T0)=K,and we define the subproblem(LIOVMSTBH(ck))of(LIOVMSTBH)when l(T0)<K,which is to verify whether ck is a feasible objective value.For each ej(?)T0,the path Pj connecting the two endpoints of ej in T0 is called the fundamental path.For each ei∈T0,we define Ωi={ej(?)T0|ei∈Pj} as the set of non-tree edges ej such that ei is in the fundamental path Pj.Let Ω0={ej∈T0|Ωi=(?)} be the set of isolated edges in T0,denote Ψ={(ei,ej)|ei∈T0\Ω0,ej∈Ωi,li>uj}.Define#12 For the capacitated problem(CIOVMSTBH),the sufficient and necessary condition for a feasible solution is that Ψ=(?) and l(T0)≤K ≤U(T0).When Ψ=(?),l(T0)=K or U(T0)=K,some optimal solutions of the problem are given,respectively.When Ψ=(?) and l(T0)<K<U(T0),the subproblem(CIOVMSTBH(ck))of(CIOVMSTBH)is defined to verify whether ck is a feasible objective value.For the problems(IOVMSTBH),(LIOVMSTBH),(CIOVMSTBH),we develop three strongly polynomial time algorithms with the same time complexities O(|V‖E|log|E|)based on a binary search method.Finally,we do some numerical experiments to show the effectiveness of the algorithms.In addition,we present a mathematical model of the unbounded problem under weighted l∞norm(IOVMST∞ω).When the spanning tree T0 satisfies the circle optimality condition,we give an optimal solution of(IOVMST∞ω).When T0 does not satisfy the circle optimality condition,we analyze the properties of the problem(IOVMST∞ω):reduce the weights of the tree edges and augment the weights of the non-tree edges that does not meet the circle optimality condition.Firstly,we construct a new weight vector ω based on the lower bound C of the optimal value.Secondly,we consider three cases ω(T0)=K,ω(T0)<K,ω(T0)>K.Thirdly,for the most difficult case ω(T0)<K,we design a weight vector ω" based on the circle optimality condition and the lower bound C of the optimal objective value.Fourthly,we calculate the intersections of multiple lines and use binary search method to find the interval that the optimal value lies in whenω"(T0)<K.Finally,we propose an algorithm with time complexity O(|E|2 log |E|)to solve the problem(IOVMST∞ω)and give some examples to verify the effectiveness of the algorithm.