Logs made linear

Logarithm table

Nonlinear model

In [1] a question is asked about a nonlinear model:

How to solve:

Nonlinear model
$$\begin{align} \min & \sum_i \color{DarkRed} x_i\\ & \sum_i \color{DarkBlue} a_i \log \color{DarkRed} x_i \ge \color{DarkBlue} c \\ & \color{DarkRed}x_i \in \{\color{DarkBlue}b_1,\color{DarkBlue}b_2,\dots,\color{DarkBlue}b_m\} \end{align}$$

where we have $n$ variables $x_i$, $i=1,\dots,n$. This model looks nonlinear because of the logarithms.

Linear model

The condition $x_i \in \{b_1,b_2,\dots,b_m \}$ is essentially a table lookup. This can be modeled using binary variables: $$y_{i,j} = \begin{cases} 1 & \text{if $x_i=b_j$}\\ 0 & \text{otherwise}\end{cases}$$ With this definition we can write $$\begin{align} & x_i = \sum_j y_{i,j} b_j \\ & \sum_j y_{i,j}=1 && \forall i\\ & y_{i,j} \in \{0,1\} \end{align}$$

Maybe somewhat surprisingly, we can also calculate $\log x_i$ using these $y_{i,j}$: $$\mathit{logx}_i = \sum_j y_{i,j} \log(b_j)$$ This is very fortunate! We get the logs essentially for free! So our complete model can look like:

Linear model

$$\begin{align} \min & \sum_i \color{DarkRed} x_i\\ & \color{DarkRed} x_i = \sum_j \color{DarkRed} y_{i,j} \color{DarkBlue} b_j \\ & \color{DarkRed}{\mathit{logx}}_i = \sum_j \color{DarkRed} y_{i,j} \log(\color{DarkBlue} b_j) \\ & \sum_j \color{DarkRed} y_{i,j}=1 && \forall i \\ & \sum_i \color{DarkBlue} a_i \color{DarkRed}{\mathit{logx}}_i \ge \color{DarkBlue} c \\ & \color{DarkRed}y_{i,j} \in \{0,1\} \end{align}$$

This model is now completely linear and we can use a standard Mixed Integer Programming (MIP) solver to solve it.

More compact models

If we want we can save a few variables and equations by substituting out the variable $\mathit{logx}_i$.  It would make the model a bit more difficult to read: $$\sum_{i,j}  a_i \log(b_j) y_{i,j} \ge  c$$ may not be completely obvious. Furthermore we can substitute out the variables $x_i$ and just keep the $y_{i,j}$ variables. Of course, you would need to recover, after the solve, the values for $x_i$ from the optimal values $y_{i,j}^*$. That model would be very compact, but would need some explanation, as it is not completely self-explanatory.

Polynomial constraints?

In [1] someone suggested to form the polynomial equations $$(x_i-b_1)(x_i-b_2)\cdots(x_i-b_m)=0$$ and solve as a Nonlinear Programming (NLP) problem. This is surely not a good approach. If this was really a great idea, we would no longer need MIP solvers! Instead of binary variables, we just could form $$x(x-1)=0$$ For an integer variable $x \in \{0,1,\dots,n\}$ we could write $$x(x-1)(x-2)\cdots(x-n)=0$$ The reason why this does not work, is that we create a very difficult non-convex problem. Unless you use a global solver, an NLP solver will just get stuck in a local optimum (or may not find a feasible solution). Don't throw away your MIP solver yet.

Final remarks

Using random data I was able to solve a problem with $n=m=100$ in a few seconds. Of course this depends on the data: other instances may take more time.

This discussion reminds me a little bit of linear regression problems. In many cases, non-linearities appear in the data only, and although the regression model looks non-linear, it can actually be handled by linear regression approaches.

References

1. How to solve the following optimization problem of mathematical programming?, https://math.stackexchange.com/questions/3090493/how-to-solve-the-following-optimization-problem-of-mathematical-programming
2. MIP Modeling: from Sudoku to KenKen via Logarithms, https://yetanothermathprogrammingconsultant.blogspot.com/2016/10/mip-modeling-from-sudoku-to-kenken.html. The model to solve KenKen puzzles uses a similar approach.