Suppose the constraints of our integer programming model consist of two parts:
- the polynomial-size formulations, that have a size (number of variables and constraints) which is polynomial w.r.t. the size of the graph G
- exponential-size formulations, that have an exponential number of subtour elimination constraints.
The material I'm reading explains the procedure to solve such integer programming:
The whole model cannot be built (except for tiny instances). Nevertheless, it is possible to generate the subtour elimination constraints dynamically, in a phase called separation. In practice, this means starting with no subtour elimination constraints. Then, during the branch-and-bound search, every time we find a solution x, we check whether it violates any of the constraints we left out of the model. If this is the case, we add those constraints, and continue.
I could roughly understand it but I have one confusion: what if the number of violated constraints in some iteration is too large to be added? Do we just add part of it?