I am interested in solving a large scale quadratic 0-1 problem with linear constraints. I have found two approaches in the literature and do not understand the relationship between them:
- Linearise the quadratic by introducing new constraints and solve as a MILP problem (with CPLEX for example)
- Use a metaheuristic - VNS seems to be recommended.
These approaches seem very different to me and I don't fully understand the fundamental differences - the first seems to generate many additional constraints which can be bad for large systems?
What are the differences between the approaches and is there a go-to solution for these large scale problems? Or do they both need to be tested and either one can turn out to be faster depending on the problem?
Approach 1 is exact, but approach 2 is only a heuristic (no guarantee of optimality). A third (exact) approach is to call an MIQP solver.