Linear program objective function depends on sign of variable

Question

I'm trying to find Q[i] to maximize

Sum[Q[i] F[i] - C[i], {i, 1, n}]

subject to some linear constraints. The problem: C[i] is a function of Q[i] but isn't linear. It's equal to Q[i] * Cp if Q[i] >= 0, and -Q[i] * Cn if Q[i] < 0 (basically a cost term that's different if Q[i] is positive vs negative).

I suspect I need to use some version of integer programming to reformulate this properly but can't see how to get there. Can anyone point me the right way, or maybe just tell me this can't be done? :)

Answer 1

Here is a Mixed Integer formulation with some additional binary variables:

We use variable splitting to have two components of Q (positive and negative). Using a binary variable we make sure only one of those components is nonzero. This will require new continuous variables q+ and q- and new binary variables delta.

The constant M+ and M- are an upper bound on q+, q-. Make them as small as possible (100 or 1000 is better than 1e6 or 1e7).

Now there is something we can exploit. The objective will push down the C term in order to maximize the total objective. This means we can drop the equations with the binary variable, as automatically only one of q-, q+ will be nonzero. I.e. if Q=-10, it will prefer q+ = 0, q- = 10 above q+ = 2, q- = 12. So the final model is actually a straight LP: