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.

  • 1
    $\begingroup$ Have your tried Branch & Bound ? $\endgroup$ – callculus Apr 15 '16 at 23:13
  • $\begingroup$ @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 ! $\endgroup$ – Alireza Apr 15 '16 at 23:19
  • 1
    $\begingroup$ 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. $\endgroup$ – user164550 Apr 15 '16 at 23:21
  • $\begingroup$ Good luck for your calculation. $\endgroup$ – callculus Apr 15 '16 at 23:27

Your Answer

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

Browse other questions tagged or ask your own question.