Continuous Approaches To 0-1 Programming Problems With Applications

New continuous approaches for the discrete optimization are proposed and investigated. Our focus is mainly on the 0-1 optimization problems, the results of which can be extended to the more general discrete optimization problems. This thesis is organized as follows:In chapter 1, the background of the research is demonstrated first, followed by a literature of the 0-1 programming problems. To conclude this section, a list of the main contents is presented.In chapter 2, a Lagrangian relaxation-based continuation approach is proposed for the linear 0-1 programming problem. Keeping the linearity of the objective and constraint functions in mind, this method take full advantage of Lagrangian relaxation and the 0-1 variable and succeeds in obtaining a simple dual problem, with explicit dual objective function and simple constraints. Moreover, the dimension of the dual variable is decreased in general, compared with the original variable. Then the threshold accepting criterion and the continuation scheme are incorporated to help generate better feasible primal solution according to the primal-dual relationship.In chapter 3, a new continuous formulation for the 0-1 programming problem is proposed from the point of view of the complementarity. The zero-one programming problem is first formulated as an equivalent mathematical program with complementary constraints, then as a smooth ordinary nonlinear programming problem with the help of the Fischer-Burmeister function. After that the augmented Lagrangian method is introduced to solve the resulting continuous problem, with optimality conditions for the non-smooth augmented Lagrangian problem derived on the basis of the aggregate function, and with convergence properties established. In chapter 4 a continuous formulation for zero-one programs is proposed based on the binary entropy function in information theory which is employed to depict the discrete zero-one variables elegantly. Then a convergent algorithm is performed on the resulting continuous problem with stable performance. Numerical experiments and comparisons of the results indicate the efficiency of the proposed method.In chapter 5, the continuous approaches in the previous section are extended to more general discrete optimization problems. As a special case, the well-known binary quadratic problem is investigated first for its simple structure. To our benefit, new properties are obtained that under suitable conditions the corresponding augmented Lagrangian function is convex in sufficiently large continuous domains. Then, the discrete optimization problem is reformulated as continuous models and solved, with application to problems in engineering. Moreover, the process showing how the continuous solution of the continuous problem iterate to the discrete 0-1 feasible solution is exhibited in detail.The last chapter summarizes the thesis and proposes some future research aspects.This thesis is supported by the National Natural Science Foundation of China under Grant 10590354,10572031.