Non-Convex Quadratic Optimization. Ratio constraints
Answered
Hi all!
My optimization problem has a ratio constraint:
sum(a[i]*x[i]) / sum(b[i]*y[i]) = sum(c[i]*z[i]) / sum(d[i]*t[i]),
where x[i],y[i],z[i],t[i] > 0 - integer variables, a[i],b[i],c[i],d[i] > 0 - coefficients.
It may be formulated into quadratic constraints in two ways.
1) sum(a[i]*x[i]) * sum(d[i]*t[i]) = sum(c[i]*z[i]) * sum(b[i]*y[i])
2) p1, p2 - extra continious variables for three constraints:
- sum(a[i]*x[i]) = p1 * sum(b[i]*y[i]);
- sum(c[i]*z[i]) = p2 * sum(d[i]*t[i]);
- p1 = p2;
Now I think that a second approach is better, because it includes less bilinear constraints. Can it be improved?
Thanks in advance,
Domagoj
-
In (2), the \( p_1 y_i \) and \( p_2 t_i \) terms are all bilinear. You could reduce the number of bilinear terms by creating auxiliary variables for each summation:
$$\begin{align*} \sum_i a_i x_i &= u_1 \\ \sum_ i b_i y_i &= u_2 \\ \sum_i c_i z_i &= u_3 \\ \sum_i d_i t_i &= u_4 \\ u_1 u_4 &= u_2 u_3. \end{align*}$$
This formulation is probably worth a try. Be sure to apply the tightest possible bounds on all variables participating in bilinear terms.
0
Please sign in to leave a comment.
Comments
1 comment