Studies On Convex Reformulation Methods For Integer Programming Problems Based On SDP Relaxations

Integer programming is an important class of optimization problems with numerous applications in economy, management, engineering, transportation and communications areas. It has attracted much attention from both academic and industrial fields. Various algorithms based on branch-and-bound and many-relaxation methods have been developed. On the other hand, the development of conic optimization provides a new concept and method for solving NP-hard problems, for instance,0-1quadratic programming and polynomial programming.In this thesis, we consider three classes of0-1integer programming prob-lems:Quadratic knapsack problem (QKP), chance-constrained quadratic knap-sack problem (CQKP) and unconstrained0-1polynomial programming (0-1UPP). Quadratic knapsack problem is a classical and challenging problem with applica-tions in project planning, production planning and financial planning. It is also the subproblem of many integer programming problems. Chance-constrained quadratic knapsack problem is a stochastic version of QKP with random coef-ficients in the capacity constraint. It has become an active research topic in recent years. Yet it also brings great challenges due to its inherent nonconvexity and combinatorial nature. Unconstrained0-1polynomial optimization is also an important class of integer programming problem which has attracted much attention in recent years. The development of conic optimization provides new methodologies to establish exact and approximation methods for unconstrained0-1polynomial optimization problems.We focus in this thesis on the theory and methodologies for the above three classes of integer programming problems using semidefinite programming (SDP) methods. We establish new convexification and reformulation methods for0-1quadratic knapsack problem and chance-constrained quadratic knapsack prob-lem. We show that the new reformulations have tighter continuous relaxations and thus could be more efficient when branch-and-bound methods are applied. We give a new way of constructing SDP relaxation for unconstrained0-1poly- nomial problem and compare it with the classical linear and SDP relaxations. Our method provides a basis for designing efficient approximation methods for unconstrained0-1polynomial optimization.In Chapter1, we briefly introduce the problem background, our research motivation and main contributions of this thesis. A survey of the relevant theory and results for the three classes of integer programming problems is given in Chapter2. Our main results and methodologies are described in Chapters3-5. We conclude the thesis in Chapter6with some concluding remarks and future research perspectives.In Chapter3, we present a new convex0-1QP reformulation for quadratic knapsack problems (QKP). This new reformulation improves the existing refor-mulation based on diagonal perturbation in the sense that the continuous re-laxation of the new reformulation is tighter than or at least as tight as that of the existing reformulation. The improved reformulation is derived from matrix decomposition of the objective function and piecewise linearization of quadratic terms on{0,1}n. We show that the optimal parameters in the reformulation can be obtained by solving an SDP problem. Extension to k-item quadratic knapsack problems is also discussed. Computational results are reported to demonstrate the effectiveness of the improved reformulation.In Chapter4, we consider a chance-constrained quadratic knapsack prob-lem (CQKP) where each item has a random size that is finitely distributed. We present a new improved convex0-1quadratic program reformulation for CQKP using the same method as mentioned in chapter three. Extension to k-item prob-abilistic quadratic knapsack problems is also discussed. Preliminary comparison results are reported to demonstrate the effectiveness of the improved reformula-tion.In Chapter5, we present new semidefinite programming (SDP) relaxation schemes for0-1unconstrained polynomial programming (0-1UPP) problems. We first construct an SDP relaxation based on matrix cone decomposition and (piece-wise) linear approximation for (0-1UPP). It is shown that this SDP bound is tighter than the standard linear form (SLF). We then use Lagrangian dual and sum of squares (SOS) relaxation to obtain SDP relaxations which are equivalent to Lasserre’s SDP relaxations for (0-1UPP). This provides a new way to derive Lasserre’s hierarchy of SDP relaxations for (0-1UPP).