4
$\begingroup$

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?

$\endgroup$

1 Answer 1

4
$\begingroup$

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}

$\endgroup$
5
  • $\begingroup$ What if there is no predefined upper bound? Or if the upper bound is very large, so this scheme will lead to a very high number of binary variables? $\endgroup$ Dec 4, 2023 at 16:31
  • 1
    $\begingroup$ 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. $\endgroup$
    – RobPratt
    Dec 4, 2023 at 17:03
  • $\begingroup$ "gradually refine it in the neighborhood of the most recent solution" - it sounds like a kind of a local search. Is it guaranteed to find the global optimum? $\endgroup$ Dec 4, 2023 at 17:12
  • $\begingroup$ You could do the refinement heuristically or exactly. One exact approach is to use sifting (column generation with a precomputed complete pool of columns). The column generation subproblem reduces to explicitly searching the pool for a negative reduced cost column. $\endgroup$
    – RobPratt
    Dec 4, 2023 at 17:43
  • $\begingroup$ 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. $\endgroup$
    – xd y
    Dec 5, 2023 at 1:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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