# Combinatorial program

### From Glossary

Let and consider a finite collection of subsets, say . For each subset there is an objective function value, , and the problem is to optimize . 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: if the i-th element is in ; otherwise, . (IP formulations are not always easy, and often there is more than one formulation, some better than others.)

- Here are some examples:
- assignment
- covering, cutting stock
- knapsack
- matching
- packing, partitioning
- routing
- sequencing, scheduling (jobs), shortest path, spanning tree
- traveling salesman

Also see integer program.