0
$\begingroup$

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$

$\endgroup$
  • $\begingroup$ If $m_i = 0$ then $m_i$ is not a positive integer... $\endgroup$ – Yuval Filmus Jun 28 '16 at 13:49
3
$\begingroup$

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).

You can now reduce your problem to KNAPSACK as described in a question on cstheory.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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