Lagrangean methods for 0-1 quadratic problems

Three Lagrangean methods for 0-1 quadratic programming are presented. The first one decomposes the initial problem into a continuous nonlinear subproblem and a 0-1 linear subproblem. The second decomposes the initial problem into a 0-1 quadratic problem without constraints and the same 0-1 linear subproblem. The last method is a Lagrangean relaxation which dualizes all the constraints. The authors try to show how a 0-1 quadratic problem may be analysed in order to choose the appropriate method. They also furnish reformulations of the dual problems which make them easier to solve. This is particularly true for the first decomposition for which the authors show that there is no need to solve the continuous nonlinear subproblem. They also give some new primal interpretations for the second decomposition and for the relaxation.