An Approximation Algorithm for Quadratic Cost 0-1 Mixed Integer Programming Problems

摘要

In this paper, we focus on the quadratic cost 0-1 mixed integer programming problem. First, we formulate the problem as a two-level programming problem that consists of a lower-level continuous quadratic program- ming problem with 0-1 variables fixed and an upper-level nonlinear 0-1 programming problem. We propose an ap- proximation algorithm for solving the upper-level 0-1 pro- gramming problem. This algorithm approximately solves a subproblem obtained by linearizing the objective function at a current point.