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.


asked 05 Sep '12, 14:36

abhiieor's gravatar image

accept rate: 0%

edited 05 Sep '12, 14:46

fbahr's gravatar image

fbahr ♦

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 ♦

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%20Trick's gravatar image

Michael Trick ♦♦
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 ♦♦

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's gravatar image

Ehsan ♦
accept rate: 16%

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%20L%C3%B6fberg's gravatar image

Johan Löfberg
accept rate: 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 :

  1. solve minimize f(x)-mu0.g(x) Note x* the optimal solution and mu=f(x*)/g(x*)

  2. if mu<mu0 then set mu0 to mu and repeat the step 1, else return mu0

You can see that while mu<mu0 we find strictly decreasing ratios f(x*)/g(x*). Now when we exit with mu=f(x*)/g(x*) >= 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's gravatar image

accept rate: 0%

Your answer
toggle preview

Follow this question

By Email:

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



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



Asked: 05 Sep '12, 14:36

Seen: 8,445 times

Last updated: 07 Sep '12, 17:49

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