Finding the nonnegative integer exponents that minimize a product

I've been trying to solve a problem which seems to be a multiplicative optimization problem:

Given a threshold $T > 0$, and a set of integers $b_1, b_2,\dots, b_n > 0$, find integer exponents $e_1, e_2, \dots, e_n \geq 0$ such that

$$P := \prod b_i^{e_i}$$

is the smallest integer in that form and greater than or equal to $T$.

Another possible optimization criterion is to relax on $P$ but find exponents such that $\sum e_i$ is minimized.

I'd really appreciate some pointers (not necessarily solutions) to help me get started.

• An example of B can be {2, 3, 4, 5, 6, 7, 8, 11, 13, 16} – user204025 Jul 5 '16 at 3:07
• won't it be easier in log domain? – Creator Jul 5 '16 at 3:15
• @Creator Thought about the log domain. Didn't get anywhere :( – user204025 Jul 5 '16 at 3:22
• @RodrigodeAzevedo The bases are positive, and the exponents are nonnegative. – user204025 Jul 5 '16 at 15:06
• @RodrigodeAzevedo There's ~20 $b$'s, and $T$ is bounded by $2^{32}$. – user204025 Jul 5 '16 at 16:58

Note that $$\ln P=\ln(\prod_{i}b_i^{e_i})=\sum_i\ln{b_i^{e_i}}=\sum_ie_i\ln b_i$$ In other words, $\ln P$ is linear with respect to variables $e_i$, which is good news.

Your problem is thus equivalent to $$\min\limits_{e_i\in \mathbb{N}}\;\left\{\sum_{i=1}^n (\ln b_i) e_i\;|\; \sum_{i=1}^n(\ln b_i) e_i\ge \ln{\tau},\; \prod_{i=1}^n b_i^{e_i} \in \mathbb{N}\right\}$$

As pointed out by Rodrigo de Azevedo, you can omit the last constraint ($\prod_{i=1}^n b_i^{e_i} \in \mathbb{N}$) if $b_i$ and $e_i$ are positive integers. Therefore, in this case, your problem is a pure integer linear problem, easy to solve.

So you end up with $$\min\limits_{e_i\in \mathbb{N}}\;\left\{\sum_{i=1}^n (\ln b_i) e_i\;|\; \sum_{i=1}^n(\ln b_i) e_i\ge \ln{\tau}\right\}$$

You can solve this with dynamic programming if $\tau$ is also integer:

Let $$f_j(t)=\min\limits_{e_i\in \mathbb{N}}\;\left\{\sum_{i=1}^j(\ln b_i) e_i\;|\; \sum_{i=1}^j(\ln b_i) e_i\ge \ln{t}\right\}$$ Now, either you set $e_{j+1}$ to $0$, and you have $f_{j+1}(t)=f_j(t)$, either you set $e_{j+1}$ to $\lambda\in \left\{ 1,\cdots, \left\lceil \frac{\ln t}{\ln b_{j+1}} \right \rceil \right\} \subset \mathbb{N}$, and $f_{j+1}(t)$ equals $\lambda \ln b_{j+1}$, plus the optimal solution for the remaining $j$ variables, with a threshold set to $\ln t-\lambda\ln b_{j+1}=\ln\frac{t}{b_{j+1}^{\lambda}}$. Therefore, the following recursive equations hold: $$f_{j+1}(t)=\min\limits_{\lambda\in\left\{ 1,\cdots, \left\lceil \frac{\ln t}{\ln b_{j+1}} \right \rceil \right\}} \left\{ \lambda \ln b_{j+1}+f_j\left(\frac{t}{b_{j+1}^{\lambda}}\right)\right\}$$ with $$f_1(t)= \begin{cases} 1 \quad\; \mbox{if}\quad b_1 \ge t\\ \infty \quad \mbox{if} \quad b_1 < t \end{cases}$$

Compute $f_n(\tau)$ with this recursion and you are done (it will take $\mathcal{O}(n\ln^2\tau)$ operations).

K.G. proposed a quick non-DP implementation to illustrate the idea.

#include <iostream>
#include <vector>
#include <unordered_map>
#include <utility>
#include <cmath>
#include <limits>

using namespace std;

vector<int> base_vec = {2, 3, 4, 5, 6, 8};
const int base_size = base_vec.size();

pair<vector<int>, int> good_size_recursive (int idx, int t)
{
pair<vector<int>, int> res;
res.first = vector<int>(base_size);
vector<int> ret_exp = vector<int>(base_size);

if (0 == idx)
{
int lambda = static_cast<int>(ceil(log(t)/log(base_vec[0])));
ret_exp[0] = lambda;
int best_bound = static_cast<int>(pow(base_vec[0], lambda));
res = make_pair(ret_exp, best_bound);
return res;
}

int best_bound = numeric_limits<int>::max();
//fixed error in lambda calculation
int lambda = static_cast<int>(ceil(log(t)/log(base_vec[idx])));

for (int i = 0; i <= lambda; i++)
{
pair<vector<int>, int> curr_res;
curr_res = good_size_recursive(idx - 1,
static_cast<int>(ceil(
(double)t/pow(base_vec[idx], i)
))
);
int curr_bound = curr_res.second * static_cast<int>(pow(base_vec[idx], i));

if ((curr_bound < best_bound) && (curr_bound >= t))
{
best_bound = curr_bound;
res = curr_res;
res.first[idx] = i;
res.second = curr_res.second * static_cast<int>(pow(base_vec[idx], i));
}
}

return res;
}

int main () {
int t;
cout << "Please enter t: ";
cin >> t;

pair<vector<int>, int> sol = good_size_recursive(base_size - 1, t);
cout << "base sizes:" << endl;
for (auto b : base_vec)
cout << b << '\t';
cout << endl << "exponets:" << endl;
for (auto s : sol.first)
cout << s << '\t';
cout << endl << "Result:" << endl;
cout << sol.second << endl;

return 0;
}

• Thank you for your answer. I'm not very familiar with optimization problems. Can you please elaborate on the formulation of the equivalent problem, especially on the variables $\tau$ and $Z$? – user204025 Jul 5 '16 at 3:35
• I think $\tau$ refers to $T$ in the question? – user204025 Jul 5 '16 at 3:37
• Forget the $Z$. $\tau$ is your threshold. – Kuifje Jul 5 '16 at 3:37
• I'm afraid the last constraint $\exp(t) \in N$ cannot be relaxed. How can it be solved in that case? – user204025 Jul 5 '16 at 3:39
• @RodrigodeAzevedo @ kuifje. The bases are positive, and the exponents are nonnegative. Can you point me to some slides or a book chapter to solve problems of this kind? Thank you. – user204025 Jul 5 '16 at 15:11