Inverse Optimization Problems Under Hamming Distance And Multicommodity Production And Distribution Problems

This dissertation studies two kinds of problems, namely, the inverse optimization problems under Hamming distance and multicommodity production and distribution problems.For a given (combinatorial) optimization problem, the inverse optimization problem is to find a minimal adjustment of the parameters (costs, capacities, etc.) of the problem such that the given solutions become optimum. Due to their theoretical importance and wide range of applications, the inverse optimization problems have attracted much attention. There are many papers discussing inverse optimization problems under l₁, l_∞ and l₂ norm. But little is known about inverse optimization problems under Hamming distance. We may find applications of the inverse optimization problems under Hamming distance in real world. In this dissertation, we study inverse optimization problems under Hamming distance.Due to its theoretical and practical importance, multicommodity production and distribution problem has attracted a vast amount of attention of academic researchers. The problem can be described as follows: There are several products produced at several plants. There is a determinate demand for each product at each customer location. The customer demand is satisfied by transiting products via some of distribution centers (DCs). The problem is how to arrange production and distribution so as to minimize the total costs. In this dissertation, we also consider the problems.In Chapter 2, we consider the following weighted inverse minimum spanning tree problem under the sum-type Hamming distance: We are given a connected undirected network G, each edge has a modification cost and a nonnegative weight. Let T° be a spanning tree of G. We are asked to modify the edge weights such that T^° is the minimum weight spanning tree and the total modification cost of modified edges is minimized under the Hamming distance. Three models are considered: Unbounded case, unbounded case with forbidden edges and bounded case. In terms of the method for minimum-weight node cover problem on bipartite graph and the algorithm of solving...