Combinatorial program

From Glossary

Jump to: navigation, search

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.)

Also see integer program.

Personal tools