revelation alrady explained the idea pretty well, so I will give a different explanation that outlines some subtile points that are rarely mentioned in the literature (IMHO):
In discrete optimization one often has the job of minimizing a linear function over some set of 0/1 vectors V (this could for now be also an arbitrary set of points in R^d). The good news is: This is equivalent to optimizing over the convex hull of V and thus optimizing over some polytope P. The bad news is: This polyhedron is often very complicated to describe in terms of inequalities (which exist by Minkowski's theorem). So give up the dream? No - we just approach a little bit differently.
Let A, b be a rational (!) matrix/vector. Then a theorem by Meyer says that
conv {x \in Z^m x R^n: A x <= b}
again forms a rational polyhedron. Indeed lots of problems (for example TSP) can be written in this form (subtour elimination polytope for TSP). Again the problem is finding the inequalities that describe it in a reasonable time. One way to handle this problem is adding inequalities iteratively until we get to the (mixed-)integer hull. Indeed one can show that if n=0 (ILP - integer linear programming) or the integral variables are 0/1-valued such algorithms exist and can in principle be implemented (though they are rather slow; for the pure integer case something to google for is "Gomory's cutting plane algorithm"). Note that in the general MILP setting finding such an algorithm is (at least for practical purposes (yes, I know about the famous Del-Pia,Weismantel paper (A. Del Pia, R. Weismantel, On convergence in mixed integer programming), I know about t-branch split disjunctions (Dash,Dobbs,Günlük ,Nowicki,Swirszc - Lattice-free sets, multi-branch split disjunctions,
and mixed-integer programming), I know about how Cook-Kannan-Schrijver circumvented this problem (W. Cook, R. Kannan, A. Schrijver - Chvátal closures for mixed integer programming problems); so you don't have to correct me ;-) )) still an unsolved problem (the theoretical side here is different, see paper references - but I don't want to go into these very subtile details). This idea to iteratively add inequalities as necessary is called "cutting plane algorithm".
For the subtour elimination polytope we have the property that the number of inequalities is exponential in the number of vertices. Nevertheless by LP duality and Carathéodory's theorem we just need at most the number of variables of inequalities to certify the optimality of a solution. So we "theoretically" just have to be clever and add the right inequalities ( ;-) ). For a given point, finding a violated inequality (or assure that none is violated) is called the "separation problem". This problem can be solved for the subtour elimination polytope. The good news is: When it can be solved for an arbitrary point (not only a vertex) we can already optimize in polynomial time over the polyhedron (just apply ellipsoid algorithm). The bad news is: The ellipsoid algorithm is painfully slow. So we have to be more clever (but here my knowledge ends - let's say: From here practise begins ;-) ).
I remark that a modern approach to avoid an exponential number of inequalities is to use so-called "extended formulations" (the basic idea is to formulate the polyhedron as a projection of a more simple polyhedron). This can be applied for the subtour elimination polytope (the best reference I can give is the PhD thesis of Kanstantin Pashkovich (full disclosure: I know him personally): http://edoc2.bibliothek.uni-halle.de/hs/urn/urn:nbn:de:gbv:m...). But in general this approach has strong limitations. For example one can show that finding a maximum matching is possible in polynomial time (Edmond's matching algorithm), but there exists no extended formulation of the matching polytope of polynomial size (http://arxiv.org/abs/1311.2369). If you are interested in the theory of extended formulations, besides the PhD thesis of Kanstantin Pashkovich I can recommend the famous Yannakakis paper that laid out the whole theory (Yannakakis - Expressing combinatorial optimization problems by Linear Programs http://www.sciencedirect.com/science/article/pii/00220000919...) and the survery paper by Conforti, Cornuéjols, Zambelli (Conforti, Cornuéjols, Zambelli - Extended formulations in combinatorial optimization).
In discrete optimization one often has the job of minimizing a linear function over some set of 0/1 vectors V (this could for now be also an arbitrary set of points in R^d). The good news is: This is equivalent to optimizing over the convex hull of V and thus optimizing over some polytope P. The bad news is: This polyhedron is often very complicated to describe in terms of inequalities (which exist by Minkowski's theorem). So give up the dream? No - we just approach a little bit differently.
Let A, b be a rational (!) matrix/vector. Then a theorem by Meyer says that
conv {x \in Z^m x R^n: A x <= b}
again forms a rational polyhedron. Indeed lots of problems (for example TSP) can be written in this form (subtour elimination polytope for TSP). Again the problem is finding the inequalities that describe it in a reasonable time. One way to handle this problem is adding inequalities iteratively until we get to the (mixed-)integer hull. Indeed one can show that if n=0 (ILP - integer linear programming) or the integral variables are 0/1-valued such algorithms exist and can in principle be implemented (though they are rather slow; for the pure integer case something to google for is "Gomory's cutting plane algorithm"). Note that in the general MILP setting finding such an algorithm is (at least for practical purposes (yes, I know about the famous Del-Pia,Weismantel paper (A. Del Pia, R. Weismantel, On convergence in mixed integer programming), I know about t-branch split disjunctions (Dash,Dobbs,Günlük ,Nowicki,Swirszc - Lattice-free sets, multi-branch split disjunctions, and mixed-integer programming), I know about how Cook-Kannan-Schrijver circumvented this problem (W. Cook, R. Kannan, A. Schrijver - Chvátal closures for mixed integer programming problems); so you don't have to correct me ;-) )) still an unsolved problem (the theoretical side here is different, see paper references - but I don't want to go into these very subtile details). This idea to iteratively add inequalities as necessary is called "cutting plane algorithm".
For the subtour elimination polytope we have the property that the number of inequalities is exponential in the number of vertices. Nevertheless by LP duality and Carathéodory's theorem we just need at most the number of variables of inequalities to certify the optimality of a solution. So we "theoretically" just have to be clever and add the right inequalities ( ;-) ). For a given point, finding a violated inequality (or assure that none is violated) is called the "separation problem". This problem can be solved for the subtour elimination polytope. The good news is: When it can be solved for an arbitrary point (not only a vertex) we can already optimize in polynomial time over the polyhedron (just apply ellipsoid algorithm). The bad news is: The ellipsoid algorithm is painfully slow. So we have to be more clever (but here my knowledge ends - let's say: From here practise begins ;-) ).
I remark that a modern approach to avoid an exponential number of inequalities is to use so-called "extended formulations" (the basic idea is to formulate the polyhedron as a projection of a more simple polyhedron). This can be applied for the subtour elimination polytope (the best reference I can give is the PhD thesis of Kanstantin Pashkovich (full disclosure: I know him personally): http://edoc2.bibliothek.uni-halle.de/hs/urn/urn:nbn:de:gbv:m...). But in general this approach has strong limitations. For example one can show that finding a maximum matching is possible in polynomial time (Edmond's matching algorithm), but there exists no extended formulation of the matching polytope of polynomial size (http://arxiv.org/abs/1311.2369). If you are interested in the theory of extended formulations, besides the PhD thesis of Kanstantin Pashkovich I can recommend the famous Yannakakis paper that laid out the whole theory (Yannakakis - Expressing combinatorial optimization problems by Linear Programs http://www.sciencedirect.com/science/article/pii/00220000919...) and the survery paper by Conforti, Cornuéjols, Zambelli (Conforti, Cornuéjols, Zambelli - Extended formulations in combinatorial optimization).