Research On Binary Quadratic Programming Problem With Linear Constraints

Binary quadratic programming problem is one of the most importantproblems in the field of mathematical programming, which comes from thepoint of theoretical researches or practical applications. The problem occursfrom many cases in our daily life, such as distribution center locationproblems, manufacture scheduling problems and capital budgeting problems.By now, most of the researches on binary quadratic programmingproblem are focused on it with no constraints except the binary one. They canbe divided into two parts: optimality conditions research and algorithmsresearch. For the algorithms, many heuristics and deterministic algorithms hadbeen proposed, especially various branch and bound algorithms. A branch andbound algorithm consists of many elements, including bounding, variablesvalue assignment and subproblems pruning.This paper makes a summary of the optimality conditions and algorithmsresearch on binary quadratic programming problem and introduces a kind ofbranch and bound algorithm for it with only binary constraint. Then, weexpand the research of binary quadratic programming problem to that withlinear constraints. Improved forcing rule, linear constraints generating methodunder giving feasible solution and feasibility judgment method of linearconstraints are proposed based on some strategies about researches. Analgorithm for binary quadratic programming problem with linear constraints isthen designed based on the optimization theory and has been implemented inMatlab7.0. Finally, the effectiveness and practical value of the proposedalgorithm is tested and verified by some artificial and practical case.