This thesis investigates the NP-hard binary quadratic optimization (BQO) problem, i.e. the problem of maximizing a quadratic function in binary variables. BQO can represent numerous important problems from a variety of domains and serve as a unified model for many combinatorial optimization problems pertaining to graphs. This thesis is devoted to developing effective metaheuristic algorithms for solving BQO and its applications. First, we propose backbone guided tabu search algorithms on the basis of variable fixation technique and a backbone multilevel memetic algorithm following the general multilevel framework, both of which are based on the idea of decreasing the problem scale so as to carry out extensive exploitation in a small search area. Then we focus on advanced methods of generating preferable initial solutions and develop GRASP combined with tabu search algorithms and path relinking algorithms. In addition, we undertake to tackle problems including maximum cut, maximum clique, maximum vertex weight clique and minimum sum coloring either by directly applying or with a trivial adaptation of our developed algorithms for BQO, with the premise that these problems are recast into the form of BQO. Finally, we present a memetic algorithm based on tabu search that effectively tackles the cardinality constrained BQO.
