# Discrete optimisation in 5 variables

I need to solve the following optimisation problem and I can't come up with any solutions. Is there any algorithm to solve this type of problem. I tried to think of a greedy algorithm or brute force, but couldn't solve it.

Input :
$n_1, n_2, n_3, n_4, n_5$ : Positive integers
$a_1, a_2, a_3, a_4, a_5$ : Positive integers
$p_1, p_2, p_3, p_4, p_5$ : Positive integers
$Q$ : Positive integer

Output : $m_1, m_2, m_3, m_4, m_5$ : Non- negative integers

Minimize : $\sum_{i=1}^{5}{m_i a_i p_i}$

Constraints :
$\forall i : m_i \geq n_i$ OR $m_i = 0$
$\sum_{i=1}^{5}{m_i a_i} \geq Q$

• If $m_i = 0$ then $m_i$ is not a positive integer... Jun 28, 2016 at 13:49

First of all, we can enumerate over all 32 possibilities of which of the two alternatives is chosen for each $m_i$ (whether $m_i \geq n_i$ or $m_i = 0$). We will analyze, for simplicity, the case where $m_i \geq n_i$ for all $i$. Let $\mu_i = m_i - n_i$, so that $\mu_i$ is some arbitrary non-negative integer. We now want to minimize the quantity $\sum_i \mu_i a_i p_i$ under the constraint $\sum_i \mu_i a_i \geq P$ (where $P$ is a function of other known parameters).