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 nonline ar subproblem and a 0-1 linear subproblem. The second decomposes the i nitial problem into a 0-1 quadratic problem without constraints and th e same 0-1 linear subproblem. The last method is a Lagrangean relaxati on which dualizes all the constraints. We try to show how a 0-1 quadra tic problem may be analysed in order to choose the appropriate method. We also furnish reformulations of the dual problems which make them e asier to solve. This is particularly true for the first decomposition for which we show that there is no need to solve the continuous nonlin ear subproblem. We also give some new primal interpretations for the s econd decomposition and for the relaxation.