# Optimization problem with the Harmonic number

I have an optimization problem:

\begin{align*} \text{ minimize } \sum_{i=1}^n H(x_i) \\ \text{ subject to } Ax \geq b, x\geq 0, x\in \mathbb{Z}^n \end{align*}

where $$H(n)$$ is the $$n$$-th Harmonic number. How can I model this harmonic number in an ILP solver in an efficient way?

Assume $$x_i$$ has upper bound $$u_i$$. Introduce binary variable $$y_{ij}$$ to indicate whether $$x_i=j$$, and minimize $$\sum_{i=1}^n \sum_{j=0}^{u_i} H(j)y_{ij}$$ subject to additional constraints \begin{align} \sum_j y_{ij} &= 1 &&\text{for all i} \\ \sum_j j y_{ij} &= x_i &&\text{for all i} \end{align}
• To get a valid upper bound $u_i$ for each $i$, you can maximize $x_i$ subject to the original constraints. To avoid a large number of binary variables, you can solve the problem in stages. Start with a coarser discretization than $\{0,\dots,u_i\}$ and gradually refine it in the neighborhood of the most recent solution. Dec 4, 2023 at 17:03
• Also, since $H_n$ increases to infinity as $n \to \infty$, any feasible solution gives a (though very large) upper bound of all $x_i$s.