Encontrar los exponentes enteros no negativos que minimizan un producto

Question

He estado tratando de resolver un problema que parece ser un problema de optimización multiplicativa:

Dado un umbral $T > 0$ y un conjunto de enteros $b_1, b_2,\dots, b_n > 0$ , encontrar exponentes enteros $e_1, e_2, \dots, e_n \geq 0$ tal que

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

es el menor número entero en esa forma y mayor o igual que $T$ .

Otro posible criterio de optimización es relajarse en $P$ pero encontrar exponentes tales que $\sum e_i$ se minimiza.

Agradecería algunos consejos (no necesariamente soluciones) para ayudarme a empezar.

Gracias de antemano.

Answer 1

Tenga en cuenta que $$ \ln P=\ln(\prod_{i}b_i^{e_i})=\sum_i\ln{b_i^{e_i}}=\sum_ie_i\ln b_i $$ En otras palabras, $\ln P$ es lineal con respecto a las variables $e_i$ Lo cual es una buena noticia.

Su problema es, por tanto, equivalente a $$ \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\} $$

Como señala Rodrigo de Azevedo, se puede omitir la última restricción ( $\prod_{i=1}^n b_i^{e_i} \in \mathbb{N}$ ) si $b_i$ y $e_i$ son positivo enteros. Por lo tanto, en este caso, su problema es un problema lineal entero puro, fácil de resolver.

Así que terminas con $$ \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\} $$

Esto se puede resolver con programación dinámica si $\tau$ también es un número entero:

Dejemos que $$ 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\} $$ Ahora, o bien se pone $e_{j+1}$ a $0$ y tienes $f_{j+1}(t)=f_j(t)$ o bien se establece $e_{j+1}$ a $\lambda\in \left\{ 1,\cdots, \left\lceil \frac{\ln t}{\ln b_{j+1}} \right \rceil \right\} \subset \mathbb{N} $ y $f_{j+1}(t)$ es igual a $\lambda \ln b_{j+1}$ más la solución óptima para el resto de $j$ variables, con un umbral fijado en $\ln t-\lambda\ln b_{j+1}=\ln\frac{t}{b_{j+1}^{\lambda}}$ . Por lo tanto, las siguientes ecuaciones recursivas se mantienen: $$ 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\} $$ con $$ f_1(t)= \begin{cases} 1 \quad\; \mbox{if}\quad b_1 \ge t\\ \infty \quad \mbox{if} \quad b_1 < t \end{cases} $$

Calcula $f_n(\tau)$ con esta recursividad y ya está (tardará $\mathcal{O}(n\ln^2\tau)$ operaciones).

---

K.G. propuso una implementación rápida no-DP para ilustrar la 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;
}