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, 03:18

Amit%20Sarkar's gravatar image

Amit Sarkar
134
accept rate: 0%

edited 01 Mar, 13:39

fbahr's gravatar image

fbahr ♦
4.6k716


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.

link

answered 27 Feb, 09:42

AndyT's gravatar image

AndyT
6588
accept rate: 7%

Your answer
toggle preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "Title")
  • 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:

×228
×190
×4

Asked: 22 Feb, 03:18

Seen: 134 times

Last updated: 01 Mar, 13:39

OR-Exchange! Your site for questions, answers, and announcements about operations research.