0
$\begingroup$

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?

$\endgroup$

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.