Integer Programming & Combinatorial Optimization

• A combinatorial optimization problem is an optimization problem with unknown variables, each of which has a finite domain (taking values from a finite set); thus, the optimal solution is the optimal one among all possible combinations of the variables taking specific values.
• Every combinatorial optimization problem can  be formulated as an integer program, since each possible solution can be coded as a subset of the index sets of the domains of the variables; that is, each possible solution of N variables, is a N-dimensional vector with integer elements.