How to linearize below LP problem : \[ \max x_1 + x_2 + \ldots + x_n + y_1 + y_2 + \ldots + y_m\\ \text{s.t.}~ x_i + y_i \leq a_i ~\forall ~i \in N=M\\ x_1 + x_2 +..+ x_n \leq b_1\\ y_1 + y_2 +..+ y_m \leq b_2\\ x_1 + x_2 +..+ x_n + y_1 + y_2 +..+ y_m \leq b_3\\ x_1 * f_1/(x_1 + x_2 +..+ x_n) + .. + x_n * f_n/(x_1 + x_2 +..+ x_n)\\ ~~~~- y_1 * g_1/(y_1 + y_2 +..+ y_m) + .. + y_m * g_m/(y_1 + y_2 +..+ y_m) \leq b_4\\ x_1,\ldots,x_n,y_1,\ldots,y_m \geq 0 \] \(f_1, \ldots, f_n, g_1, \ldots, g_m\) are constants.
asked
Amit Sarkar fbahr ♦ |

First of all, if your sums ( (x_1 + ... + x_n) = 0 ) or ( (y_1 + ... + y_m) = 0 ), you are of course in trouble. So you'll probably want to add constraints so that they are lower bounded by some small positive ( \epsilon ) value(s). The fourth constraint (with right-hand side ( b_4 ) ) can be rewritten in the following fashion. First, introduce two new variables ( v \geq 0 ), with ( v = 1/(x_1 + ... + x_n) ), and ( z \geq 0 ), with ( z = 1/(y_1 + ... + y_m) ). Then the terms in the fourth constraint can be rewritten as ( f_i * x_i * v ) and ( g_i * y_i * z ). Simultaneously, two equations will need enforced: ( v * (x_1 + ... + x_n) = 1 ), and ( z * (y_1 + ... + y_m) = 1 ). There are now bilinear terms involving ( v ) and ( z ). However, as there is only a single ( v ) and a single ( z ), these two variables can be discretized to within any desired accuracy using a technique similar to that in this paper: N. Temiz, A. Trapp, O. Prokopyev, C. J. Camacho, "Optimization of Minimum Set of Protein-DNA Interactions: a Quasi Exact Solution with Minimum Over-fitting," Bioinformatics, Vol. 26 (3), pp. 319-325, 2010. The resulting optimization problem becomes a mixed-integer program as it requires (a logarithmic number of) binary variables, and moreover you will need upper bounds on the ( x ) and ( y ) variables -- your first and second equations provide at least trivial bounds. As long as x and y values are not extremely large or small magnitudes, this technique should work as intended.
answered
AndyT |