linear-programming - Linear form of function (a/b) for ampl/cplex

Question

I am trying to solve a minimisation problem and I want to minimise an expression

a/b

Where both a & b are variables. Hence this is not a linear problem... How can I transform this function into an other one (being a linear one).

Answer 1

There are several ways to do this, but the simplest to explain requires that you solve a series of linear programs. First, remove the objective and add a constraint

a <= c * b

Where c is a known upper bound on the solution. Then do a binary search on c you can a range where c_l, c_u where the problem is infeasible for

a <= c_l * b

but feasible for

a <= c_u * b

Answer 2

There is a detailed section on how to handle ratios in Linear Programming on the lpsolve site. It should be general enough to apply to AMPL and CPLEX as well.

Answer 3

The general form of the obj should be a linear fractional function, something like f_{0}(x)=(c^Tx+d)/(e^Tx+f). For your case, X=(a,b),c=(1,0),(e=0,1),d=f=0. To solve this kind of opt, something called linear fractional programming can be used. it's like linear constrainted version of linear fractional function and Charnes-Cooper transformation is applied to transform into a LP. You can find the main idea from wiki. Many OR books talk more about this such as pp53, pp165 in the Boyd's "convex optimization" (free to download).