# Linearization of a ratio typed objective function

 2 Hi, I am having an objective function of the form: sum(i in iterator) ROI(i)*binary(i)/sum(i in iterator) cost(i)*binary(i) Aforementioned constraint is a non-linear one with binary(i) being the decision variable. I am looking forward for linearising this constraint. Any help will be appreciated. Regards, Abhi asked 05 Sep '12, 14:36 abhiieor 21●1●3 accept rate: 0% fbahr ♦ 4.6k●7●16 Ignoring the binary nature of the dec. var.s, one would apply Charnes-Cooper transformation to yield a non-fractional program. In presence of int. and/or bin. var.s, the situation is a little "trickier"; but googling for "int. (lin.)-", "0/1-", & "bin. fract. progr." gave me some results you might like to look into. PS: The problem here is a somewhat diff. from yours, but ...maybe re-modeling is an option. (05 Sep '12, 15:50) fbahr ♦

 4 If nothing else, you can solve a series of problems by doing binary search on the objective. If the objective is to maximize the value (it is a bit confusing: I would have thought ROI included cost values, but I'll assume you are modeling what you want), then if you want to see if value V is feasible, put in the constraint sum(i in iterator) ROI(i)binary(i) >= sum(i in iterator) Vcost(i)*binary(i) Do binary search on V and take the largest feasible value. answered 05 Sep '12, 15:08 Michael Trick ♦♦ 4.1k●5●16●33 accept rate: 20% Thanks for your input Michael. Though I am not able to understand it completely as I am not getting what do you mean by performing a binary search on V. Does it mean the following: Max V s.t. sum(i in iterator) ROI(i)binary(i) >= V * (sum(i in iterator) cost(i)*binary(i)) other constraints If this is what you mean then it should also work in the desired manner; however the problem will now be quadratrically constrained problem than a problem with non-linear objective function. Does this type of problems are lesser complex than the former one. Regards, Abhi (05 Sep '12, 15:43) abhiieor In essence the linearization objective is still missing. (05 Sep '12, 15:44) abhiieor Fix V at 100. Now the problem is linear. If feasible, try V at 200; if not try V at 50. Keep solving problems until you find the highest possible V. If you have an upper bound U on the objective, and your goal is to get with eps of optimal (say, eps=.0001) then you solve log(U/eps) problems (in this case you would start with U/2). (05 Sep '12, 16:04) Michael Trick ♦♦
 2 You might see here for a paper discussing how to transform fractional binary objective functions into linear ones. answered 05 Sep '12, 16:07 Ehsan ♦ 4.8k●3●11●22 accept rate: 16%
 1 First write as minimize t subject to sum(ROI(i)binary(i)) <= sum(cost(i)binary(i))*t  This is linearized using standard big-M methods. Introduce new variable w(i) to represent binary(i)*t. sum(ROI(i)binary(i)) <= sum(cost(i)w(i)) -(1-binary(i))M<= w(i)-t <= (1-binary(i))M 0 <= w(i) <= M*binary(i)  M is a suffiently large constant for big-M to be correct, for instance sum(cost)/min(ROI) which is an upper bound on optimal t. Maximization follows using similar approach answered 06 Sep '12, 04:21 Johan Löfberg 11●1 accept rate: 0%
 0 Minimize f(x)/g(x)  where both f and g are linear , can be solved by successive LPs You begin with an initial point x0 and mu0=f(x0)/g(x0) then repeat the following : solve minimize f(x)-mu0.g(x) Note x* the optimal solution and mu=f(x*)/g(x*) if mu= mu0 , we then have for all x, f(x)-mu0.g(x) >= f(x*) - mu0.g(x*) >= 0 therefore for all x, f(x)/g(x) >= mu0 which proves that mu0 is the minimal possible ratio answered 07 Sep '12, 17:49 Davidoff 11●1●3 accept rate: 0%
 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: