0
$\begingroup$

I'm looking for an algorithm that will let me optimally select items from a set. These items have properties which are involved in defining constraints as well as the objective function.

.e.g Say each item in the set has integer-valued properties A, B, C. I need to select n items (say 2, can pick any item at most once) such that the sum of the property B among all selected items is at least 50 and the sum of all C's is at least 60 (two constraints), and I need to maximize for sum of A.

Where should I start looking? I was pointed towards LP but am unable to formulate it since I'm looking to pick exact items from a set.

$\endgroup$
3
2
$\begingroup$

You can indeed formulate an Integer Linear Program. Let $x_i \in \{0,1\}$ denote whether you select item $i$. For each item $i$ define $f_a(i)$, $f_b(i)$, and $f_c(i)$ as the integer values for the properties $A$, $B$, and $C$.

Then we define the objective function as maximizing $\sum_{i = 1}^{m} f_a(i) \cdot x_i$, given $m$ items in total.

Your constraints are very similar as well, namely $\sum_{i = 1}^{m} f_b(i) \cdot x_i \geq 50$, and $\sum_{i = 1}^{m} f_c(i) \cdot x_i \geq 60$.

Since you can select at most $n$ of those $m$ items, you need to following constraint: $\sum_{i = 1}^{m} x_i \leq n$.

You can then easily recover the solution from your variables. Simply check whether $x_i = 1$, and if so, add item $i$ to your solution.

$\endgroup$
1
  • $\begingroup$ Thank you, this helped $\endgroup$ – Kedar Jan 4 at 15:09

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.