# Linearize fractional constraints

 0 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 22 Feb '18, 03:18 Amit Sarkar 13●5 accept rate: 0% fbahr ♦ 4.6k●7●16

 0 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 27 Feb '18, 09:42 AndyT 678●8 accept rate: 7%
 toggle preview community wiki

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "Title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported

Tags: