Research On Semidefinite Programming For Slab Stack Shuffling Problem

In iron and steel enterprise, slab-yard acts as a buffer between continuous-casting and hot-rolling production. The management efficiency of slab-yard directly affects the production continuity of continuous-casting and hot-rolling as well as the production cost of integrated production. In this thesis, the typical Slab Stack Shuffling problem (SSS) in hot-rolling slab-yard is studied. The SSS problem is a {0,1} integer quadratic programming which is difficult to find an optimal solution in polynomial time. We provide a lower bound for this problem by using semidefinite programming method. We further construct a heuristic algorithm to solve the problem approximately. In addition, the lower bound is enhanced by another SDP approach. Three parts of work are done in this thesis, as follows:(1) Research on the SDP technique. Firstly the basic theory and algorithm of semidefinite programming are summarized. Then a review of recent search and application of SDP are given in the following three parts:giving some examples of the problems those can be transferred to SDP equally; summarizing three kinds of SDP relaxation technology for the max-cut problem; solving other problems, such as support vector machines, by SDP.(2) Research on the SSS problem. A standard {0,1} quadratic programming is given by redefinition the SSS problem using slab’s matrix properties. In order to get the lower bound, two SDP relaxation models are provided. One is from the relaxation of the {0,1} linear constraints SSS problem, the other is from the relaxation of the {-1,1} quadratic constraints SSS problem. The lower bound and the nearly optimal solution of SSS problem are obtained by solving the SDP using SDPA package combined with a simple heuristic algorithm. The numerical results show that the method can effectively solve the SSS problem, and the average gap between the lower bound and optimal solution is less than20%. (3) Further research on SDP method for the SSS problem. A new model is proposed by replacing rank(Y)=1with two nonlinear constraints. Then a tighter SDP relaxation is achieved. It provides a sharp lower bound in theory, and a numerical example is also given to support the result. Finally, the proofs of the convex of the SDP relaxation and the equivalence relation of all the different SSS models are given in theory.