# Linear integer programming

I am trying to find the optimal solution for the following linear integer programming:

\begin{eqnarray} &&\underset{x_i, \forall i} {\text{maximize}} ~ \sum_{i=1}^N x_i a_i \\ && \text{s.t.} \sum_{i=1}^N i ~x_i \leq B, ~~~x_i \in \mathbb N_{0}, ~\forall i. \nonumber \end{eqnarray}

where $a_i$'s are known positive coefficients.

• Have your tried Branch & Bound ? – callculus Apr 15 '16 at 23:13
• @callculus not really, I was thinking of a relaxed solution of linear programming which would be sub-optimal, I'll try Branch and bound but it must be tedious for this problem ! – Alireza Apr 15 '16 at 23:19
• It seems like a knapsack problem (where the value is $a_i$ and the cost is $b_i = i$) for which some efficient algorithms can be used. – user164550 Apr 15 '16 at 23:21
• Good luck for your calculation. – callculus Apr 15 '16 at 23:27