含乘积项非线性转线性规划

假设有如下规划问题，其中变量有(mu , w_i, x_{ij})，含了两变量乘积项，属于非线性规划。

egin{align} &min mu\ ext{Such that: }& w_0U_{ij}+w_jZ_i+w_iZ_jleq mu Bx_{ij}, ext{ for any }i,j=1,2,...,N \ &sum_{i=0}^N w_i=1 \ & w_igeq 0, i=0, 1, 2,...,N \ & sum_{j=1}^N x_{ij}leq R_i, sum_{i=1}^N x_{ij}leq R_j,\ & x_{ij} ext{ are non-negative integers and }x_{ii}=0 end{align}

直接解，会报错类似：gurobipy.GurobiError: Q matrix is not positive semi-definite (PSD)

可以令 (alpha = frac{1}{mu}) 后，转换为线性规划。此时有新变量 (y_{i} = alpha w_{i})。

egin{eqnarray} &max alpha\ ext{Such that: }& y_0U_{ij}+y_jZ_i+y_iZ_jleq Bx_{ij}, ext{ for any }i,j=1,2,...,N \ &sum_{i=0}^N y_i=alpha \ & y_igeq 0, i=0, 1, 2,...,N \ & sum_{j=1}^N x_{ij}leq R_i, sum_{i=1}^N x_{ij}leq R_j,\ & x_{ij} ext{ are non-negative integers and }x_{ii}=0 end{eqnarray}