I have this question:

Suppose you are given a set of positive integers $A = \{a_1, a_2, \dots, a_n\}$ and a positive integer $B$. A subset $S \subseteq A$ is called feasible if the sum of the numbers does not exceed $B$. You would like to select a feasible subset $S$ of $A$ whose total sum is as large as possible. Design an integer Linear program for finding $S$

My work so far:

Let $x_i = 1$ if $a_i \in S$ and $x_i = 0$ otherwise


$\sum\limits_{a_i \in S} x_ia_i$ for $a_i \in A$

$0 \leq x_i \leq 1$

With constraints:

$\sum\limits_{a_i \in S} x_ia_i \leq B$

$x_i \in {0,1}$

My question is, in properly designing this ILP am I correct in having the sum be $\sum\limits_{a_i \in S} x_ia_i$ ? or should it be summing the values of $A$ and just using $x_i$ to assign it weight. Like this $\sum\limits_{a_i \in A} x_ia_i$?

  • $\begingroup$ Why did you heavily edit your question to remove most of it, specifically what you had done? (rolled back) $\endgroup$ – Clement C. Nov 15 '17 at 4:30

You want $\sum_{a_i \in A} x_i a_i$. You need to sum over all elements of $A$. Notice that the goal is to determine $S$, so you cannot use it in your objective function: you don't know what $S$ is!

The same goes for your constraint: you want $\sum_{a_i \in A} x_i a_i \le B$.

  • $\begingroup$ Also, the $0\leq x_i\leq 1$ is redundant, since the OP also has $x_i\in\{0,1\}$. $\endgroup$ – Clement C. Nov 15 '17 at 3:42

Your Answer

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