Piecewise nonlinear functions

In [1] a question is posed how we can model the piecewise nonlinear function depicted below:

Model the dashed line h(x)

We want to model that the costs are represented by the function \(h(x)\) (the dashed curve in the picture). Let's make a few assumptions:

• The function \(f(x)\) is a quadratic function while \(g(x)\) is linear.
• \(f(x)\) is convex
• We are minimizing cost (or maximizing profit)
• Update: I also assume this is part of a larger problem, with multiple items. If this was the only curve, we just can use \(\min f(x) = \min x\) due to monotonicity (see comments below). If we want to minimize \(\displaystyle \sum_i \mathit{Cost}_i\) this is no longer applicable.

Choose cheapest

One way is to observe that for any \(x\) we choose the cheapest curve. I.e. we have \(\mathit{Cost}=\min(f(x),g(x))\). This can be modeled as:
\[\begin{align}\min \> & \mathit{Cost}\\ & \mathit{Cost}\ge f(x)-M\delta\\ &\mathit{Cost}\ge g(x)-M(1-\delta)\\&x \in [0,x_{max}]\\ & \delta \in \{0,1\}\end{align}\] The proper value for \(M\) would be \(M=f(x_{max})-g(x_{max})\). Basically this MIQCP (Mixed-Integer Quadratically Constrained Programming) formulation says: just choose one of the curves and ignore the other one. The objective will make sure the most expensive curve is ignored and the cheapest curve is retained. We did not have to use \(x_0\) at all in this formulation.

The big-M value can become large in case \(x_{max}\) is large. Sometimes a SOS1 formulation is proposed. For this case this means:\[\begin{align}\min \> & \mathit{Cost}\\ & \mathit{Cost}\ge f(x)-s_1\\ &\mathit{Cost}\ge g(x)-s_2\\&x \in [0,x_{max}]\\ & s_1,s_2 \ge 0\\& \{s_1,s_2\} \in SOS1\end{align}\]

If the solver allows indicator constraints we can write: \[\begin{align}\min \> & \mathit{Cost}\\ & \delta=0\Rightarrow \mathit{Cost}\ge f(x)\\ &\delta=1 \Rightarrow \mathit{Cost}\ge g(x)\\&x \in [0,x_{max}]\\& \delta \in \{0,1\}\end{align}\]

Use Intervals

A more standard approach would be to try to formulate: \[\mathit{Cost}=\begin{cases} f(x) & \text{if $x \le x_0$} \\ g(x) &\text{if $x\gt x_0$}\end{cases}\] Instead of letting the solver decide the best value of \(\delta\), now we use the current value of \(x\) to determine \(\delta\). The rule \[\delta = \begin{cases} 0 & \text{if $x \in [0,x_0]$} \\ 1 & \text{if $x \in [x_0,x_{max}]$}\end{cases}\] can be rewritten as:\[\begin{align} & \delta = 0 \Rightarrow x \in [0,x_0]\\ & \delta = 1 \Rightarrow  x \in [x_0,x_{max}]\end{align}\] (Note that we added some ambiguity for \(x=x0\). In practice that is no problem. Int can be argued this is good thing [2].) This expression in turn can be formulated as two inequalities: \[x_0 \delta \le x \le x_0 + (x_{max}-x_0) \delta\] We can add this to any of the earlier formulations, e.g.: \[\begin{align}\min \> & \mathit{Cost}\\ & \mathit{Cost}\ge f(x)-M\delta\\ &\mathit{Cost}\ge g(x)-M(1-\delta)\\ &x_0 \delta \le x \le x_0 + (x_{max}-x_0) \delta \\&x \in [0,x_{max}]\\ & \delta \in \{0,1\}\end{align}\]

References

1. Piecewise non-linear cost function in Cplex, https://stackoverflow.com/questions/49992813/piecewise-non-linear-cost-function-in-cplex
2. Strict inequalities in optimization models, http://yetanothermathprogrammingconsultant.blogspot.com/2017/03/strict-inequalities-in-optimization.html