I have this minimization problem
$\min \sum_{i=1}^k\alpha_i {X_i\choose r}$
s.t. $\sum_{i=1}^kX_i=m$
and $0<X_i<N$, $\alpha_i>0$, $1<k<N$, $m=(k-1)N$, and $1<r<N$
where $N$, $m$, $r$, and $\alpha_i$ are constants. ($N$ is the number of nodes in the problem)
But I have no idea how to approach it. Any ideas will help greatly.
Combinatorics in integer programming, pretty cool...
You are facing a typical case of integer programming with a non-linear cost function. What you can do (like always in those cases), is to define
$ \forall i \in [1,k], \forall n \in [0,m], Y_{i,m} $ the binary variable equal to $1$ iff $X_i = n$.
Your problem then becomes
$\min \sum_{i \in [1,k]} \sum_{n \in [0,m]} \alpha_i \binom{n}{r} Y_{i,n} $
s.t. $ \sum_{i \in [1,k]} \sum_{n \in [0,m]} n \cdot Y_{i,n} = m $
$\forall i \in [1,k], \sum_{n \in [0,m]} Y_{i,n} = 1$
Which is linear
I hope for you that this trick doesn't make an unsolvable MIP (I don't know the size of your problem). This kind of linearization trick is usually expensive computation-wise.
I sincerely wish you find a trick requiring less variables (for instance, if you are lucky enough so that $\binom{X_i}{r}$ is always convex, you don't need all of this). Good luck
