A new global approach for 0-1 polynomial programs

Given a 0-1 polynomial expression Σ_{k = 1}^{N - 1}Σ_{m = k + 1}^Nx_kx_m, where x_k and x_m are 0-1 variables, the famous Glover and Woolsey method required to use N(N - l) 2 additional continuous variables and 2N(N - 1) linear constraints to transform this expression into a linear form. This paper proposes a method which first reformulates the above expression as a new expression Σ_{k = 1}^Nx_ky_k, y_k = Σ_{m = k + 1}^Nx_m; then to transform the expression into a linear form where x_k and y_k are separated. The proposed transformation method only required to use 2(N - 1) additional continuous variables and 8(N - 1) linear constraints. Based on the new transformation, a 0-1 polynomial program can be more effectively solved to obtain a global optimum.