4
$\begingroup$

I have a problem which is mainly linear but it has a non-linear component. The objective function is

obj = Linear_term + $c*f(x,y)$ where,

$f(x,y) = (G_1 x_1 + G_2 x_2)/(x_1 + x_2)$.

The decision variables and parameters are as follows.

$0 < b_1 <1$ :: decision variable

$0 <b_2 <1$ :: decision variable

$c>1$ :: integer decision variable

$Q_1$ :: constant

$Q_2$ :: constant

$G_1$ :: constant

$G_2$ :: constant

$x_1 = Q_1 * b_1$

$x_2 = Q_2 * b_2$

My questions are:

How I can model $cf(x,y)$ in MIP? Please note it is also probable that more than two decision variables of $b$ appear in the last equation.

How do I break this fraction and model it in linear form?

$\endgroup$
1
  • $\begingroup$ Do you have any upper bound on $c$? $\endgroup$ – RobPratt Oct 29 '20 at 23:45
6
$\begingroup$

Without the $c$ variable, you could do a Charnes-Cooper transformation, followed by a linearization of a product of a continuous and binary variable, as shown in my answer https://math.stackexchange.com/questions/3500493/doing-a-charnes-cooper-transformation-with-matrices-and-an-zero-one-constraint/3500608#3500608

If $c$ has a small enough upper bound, you can solve a separate problem for each value of $c$ and take the best.

Alternatively, you can introduce a variable $z$ to replace $c\cdot f(x,y)$ in the objective function and impose constraint $(x_1+x_2)z=c(G_1 x_1+G_2 x_2)$, which you can linearize by linearizing the resulting products of continuous and binary variables.

$\endgroup$
1
  • $\begingroup$ Thank you so much Rob for your prompt and comprehensive reply. Your guide also led me to another reference that could be helpful for others to deal with these tricks. I will put the link below. AIMMS Modeling Guide - Linear Programming Tricks download.aimms.com/aimms/download/manuals/… $\endgroup$ – Hirad A Oct 30 '20 at 2:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.