Minimize a linear cost function subject to a cubic equality constraint

Question

In the framework of a simple load balancing problem, I am facing an optimization problem, but I am not sure if I am handling it in the right way.

Let's say I have a 3D grid of P distinct ressources, arranged over a 3D mesh of size $p_1 p_2 p_3$, and I want to process a 3D workload of size $mnk$, where all quantities are positive, non zero integer : $p_1, p_2, p_3, m, n, k \in \mathbb{N}^*$

The cost of processing all these workload is \begin{align} (p_3-1)mn + (p_2-1)mk + (p_1-1)nk \end{align}

Here, we have $m,n$ and $k$ three constants of the problem, and $p_1, p_2$ $p_3$ variables constrained by $p_1 p_2 p_3 = P$. Finding the best possible grid configuration is then equivalent to solve a constrained optimization problem of the form:

\begin{equation} \underset{p_1*p_2*p_3=P, p_1,p_2,p_3 \in \mathbb{N}^*}{argmin} \alpha_1 p_1+ \alpha_2 p_2+\alpha_3p_3 \end{equation} with $\alpha_1=mn$, $\alpha_2=mk$ and $\alpha_3=nk$

My first idea was to transform the integer variables into real positive constraints. so that I get at least an approximate solution for the integer case, and tranform the product into a sum using a log. Then I should be able to use the method of lagrangian multiplier ?

\begin{equation} \underset{log(p_1)+log(p_2)+log(p_3)=log(P), p_1,p_2,p_3 \in \mathbb{R}^{+*}}{argmin} \alpha_1 p_1+ \alpha_2 p_2+\alpha_3p_3 \end{equation}

Another possibility would be to put $p_1, p_2$ and $p_3$ in a diagonal matrix, and solve a linear optimization problem with an equality constraint on the matrix determinant, but this does not look easier.

In one of the paper I am reading, the author use a slightly different approach, he claims that load balancing is effective only if every ressource has the same amount of work to do, hence a change of variable of the form: $n_1=\frac{m}{p_1}, n_2=\frac{n}{p_2}$ and $n_3=\frac{k}{p_3}$, and the constraint $n_1 n_2 n_3 = \frac{mnk}{P}$, we can setup:

\begin{align} &\underset{n_1 n_2 n_3 = \frac{mnk}{P} \in \mathbb{N}}{argmin} \frac{m}{n_1}nk+ \frac{n}{n_2}mk+ \frac{k}{n_3}mn\\ \Leftrightarrow &\underset{n_1 n_2 n_3 = \frac{mnk}{P} \in \mathbb{N}}{argmin} (mnk) \left( \frac{1}{n_1}+\frac{1}{n_2}+\frac{1}{n_3}\right)\\ \Leftrightarrow &\underset{n_1 n_2 n_3 = \frac{mnk}{P} \in \mathbb{N}}{argmin} (mnk) \left( \frac{n_2 n_3+n_1 n_3+n_1 n_2}{n_1 n_2 n_3}\right)\\ \Leftrightarrow &\underset{n_1 n_2 n_3 = \frac{mnk}{P} \in \mathbb{N}}{argmin} (mnk) \frac{P}{mnk} (n_2 n_3+n_1 n_3+n_1 n_2)\\ \Leftrightarrow &\underset{n_1 n_2 n_3 = \frac{mnk}{P} \in \mathbb{N}}{argmin} (n_2 n_3+n_1 n_3+n_1 n_2) \end{align}

This problem is exactly equivalent to the minimum surface cuboid, with a given volume, whose solution in the continuous case is that each ressource should handle a subcube of the total work, then assuming $n_1=n_2=n_3$, which simplifies the problem even further: \begin{align} n_1 &= \sqrt[3]{\frac{mnk}{P}}\\ p_1 &= \frac{m}{n_1}\\ p_2 &= \frac{n}{n_1}\\ p_3 &= \frac{k}{n_1} \end{align}

(Edit) How can I now solve this problem in the integral case

Thank you in advance

Answer 1

Given $b, c_1, c_2, c_3 \in \mathbb N^+$,

$$\begin{array}{ll} \text{minimize} & c_1 x_1 + c_2 x_2 + c_3 x_3\\ \text{subject to} & x_1 x_2 x_3 = b\\ & x_1, x_2, x_3 \in \mathbb N^+\end{array}$$

Let the prime factorization of $b$ be

$$b = p_1^{m_1} \cdot p_2^{m_2} \cdots p_n^{m_n}$$

where $p_1, p_2, \dots, p_n$ are the $n$ prime factors and $m_1, m_2, \dots, m_n$ are their multiplicities. From the prime factorization, one can generate all (finitely many) triples $(x_1, x_2, x_3)$ that satisfy the cubic equality constraint. Evaluating the objective function at each triple, one can find the minimum.

---

Example #1

Let $b := 12$. Note that $12 = 2^2 \cdot 3$. Brute-forcing in Haskell:

Prelude> triples = [ (x1,x2,x3) | x1 <- [1..12], x2 <- [1..12], x3 <- [1..12] ]
Prelude> triples' = filter (\(x1,x2,x3)->x1*x2*x3==12) triples
Prelude> triples'
[(1,1,12),(1,2,6),(1,3,4),(1,4,3),(1,6,2),(1,12,1),(2,1,6),(2,2,3),(2,3,2),(2,6,1),(3,1,4),(3,2,2),(3,4,1),(4,1,3),(4,3,1),(6,1,2),(6,2,1),(12,1,1)]
Prelude> length triples'
18

Hence, one only has to evaluate the objective function at $18$ triples. One can arrive at the number of solutions without using brute force, however. Let each solution be of the form

$$(2^{\kappa_1} \cdot 3^{\ell_1}, 2^{\kappa_2} \cdot 3^{\ell_2}, 2^{\kappa_3} \cdot 3^{\ell_3})$$

Since the product must be $12 = 2^2 \cdot 3$,

$$2^{\kappa_1 + \kappa_2 + \kappa_3} \cdot 3^{\ell_1 + \ell_2 + \ell_3} = 2^2 \cdot 3$$

and, thus, one obtains two linear equations over the nonnegative integers

$$\kappa_1 + \kappa_2 + \kappa_3 = 2 \qquad \qquad \qquad \ell_1 + \ell_2 + \ell_3 = 1$$

The number of nonnegative integer solutions of the equation $z_1 + z_2 + z_3 = k$ is the coefficient of $t^k$ in the following generating function

$$\dfrac{1}{(1-t)^3}$$

Using SymPy:

>>> from sympy import *
>>> t = Symbol('t')
>>> f = 1 / (1-t)**3
>>> f.series(t,0,3)
1 + 3*t + 6*t**2 + O(t**3)

Thus,

• $\kappa_1 + \kappa_2 + \kappa_3 = 2$ has $6$ nonnegative integer solutions

• $\ell_1 + \ell_2 + \ell_3 = 1$ has $3$ nonnegative integer solutions

Hence, the total number of solutions is $6 \cdot 3 = 18$. Finding all positive integer solutions of the cubic equation $x_1 x_2 x_3 = 12$ thus boils down to finding all nonnegative integer solutions of $n = 2$ linear Diophantine equations, i.e., finding all integer points inside a polytope.

---

Example #2

Let $b := 5000 = 2^3 \cdot 5^4$. Using SymPy:

>>> from sympy import *
>>> t = Symbol('t') 
>>> f = 1 / (1-t)**3
>>> f.series(t,0,5)
1 + 3*t + 6*t**2 + 10*t**3 + 15*t**4 + O(t**5)

Hence, the total number of solutions is $10 \cdot 15 = 150$.

---

Example #3

Let $b := 5040 = 2 \cdot 3 \cdot 4 \cdot 5 \cdot 6 \cdot 7$. Since $z_1 + z_2 + z_3 = 1$ has $3$ nonnegative integer solutions, the total number of solutions is $3^6 = 729$.