# Combinatorial program

Let $LaTeX: N = \{1, ..., n\}$ and consider a finite collection of subsets, say $LaTeX: {S_1, S_2, ..., S_m}$. For each subset there is an objective function value, $LaTeX: f(S_k)$, and the problem is to optimize $LaTeX: f(S_k)$. Typically, the feasible subsets are represented by inclusion or exclusion of members such that they satisfy certain conditions. This then becomes a special class of integer programs whose decision variables are binary valued: $LaTeX: x_{i,k}=1$ if the i-th element is in $LaTeX: S_k$; otherwise, $LaTeX: x_{i,k}=0$. (IP formulations are not always easy, and often there is more than one formulation, some better than others.)