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?


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.