What is the best way to convert this into a integer linear program and what is the best way to solve such a problem?

Question

I am studying a mixed integer program in the form $$ \textrm{min}: \sum A x$$ constrained by $\sum x_i = N$

where $x$ is a vector containing only 1's and 0's, N is an integer, and $A$ is a square matrix of real numbers.

What may be the best way/algorithm/solver to solve this class of problem?

Another question I have is how to best convert this into the form required for the MATLAB MILP solver $ \textrm{min}: f^T x$, where $f$ is a vector,as I instead have a sum over a square matrix $A$.

Many thanks for anybody's help!

Answer 1

This is similar to a knapsack problem — but made simpler by the fact that each item has the same weight.

You can actually use a greedy algorithm here:

1. Expand $\sum Ax$ onto a linear objective $\sum_{i=1}^{|x|} a_ix_i$ where $a_i=\sum_{j=1}^{|x|} A_{ji}$

2. Sort $a_i$ in increasing order

3. Starting from the smallest $a_i$ set the associated $x_i$ to $1$ until you have set $N$ variables to $1$ (rest are 0).

This will be the optimal solution.