What are the known(polynomial) approximation algorithms to get MIP(Mixed-Integer Programming) solutions from LP relaxation?

user_16345105 0
Viewed 66

I want to control these approximation algorithms in time and solution quality with my own approximation algorithm for a problem of mine and the MIP solution itself.

So what are the known approximation algorithms that will be created from the LP relaxation of the problem?

Note: If you wanna explain it I will appreciate it but if you don't names of those algorithms are more than enough.

Thank you all in advance.

mixed-integer-programming approximation linear-programming
1 Answers

MIP solvers are very good in finding good solutions quickly. So, Stop on time limit, essentially makes it a polynomial approximation algorithm. It gives you a constant time complexity, and in many cases a good solution. An alternative is to stop on the gap (no good complexity bound). The idea is that MIP solvers show most improvements at the beginning of the search. These stopping conditions exploit that.

user_56255340
Related