Archive | Heuristics RSS feed for this section

The Feasibility Pump

8 Jul

The Feasibility Pump is an heuristic used in Mixed Integer Programs (MIP). Its aim is to solve the satisfaction problem, i.e. find a feasible solution to the MIP. We want to find this initial solution as we can then start cutting on the branch and bound tree and apply other heuristics such as RINS,  which uses local search to find a better solution. Ideally we would like to not take very long in finding this solution, but at the same time we would like a solution with a reasonable objective value.

This heuristic divides the MIP into two spaces: the LP polyhedron and the space of integer (or binary) points. It first finds the LP point, which  becomes the fractional solution $x$. We then find the closest integer point by simply rounding each variable to the nearest integer. We now project back onto the feasible space by solving the LP $\sum_{j} |x_j – x_j^*|$ with the same constraints as the original MIP. We now have an integer point $x^*$ and we know its distance from the LP polyhedron. If the distance is 0, this means that out integer point IS the fractional solution, which means we have found an feasible point. Most of the time, this isn’t the case, so we need to project back (by rounding) to the integer space.  And we repeat this practice until there is a solution.

Well not quite. FP suffers from cycling. This is where it alternates between the same integer for fractional solutions. To combat this FP has perturbations and restarts. A perturbation is simple just shifting a few of the variables slightly in order to kick it out of the cycle. After a few perturbations, if cycling is still detected, a restart is performed which causes all the variables to be essentially randomised. To detect cycling FP says the distance calculated from the integer to fractional calculation must always be decreasing.

As far as I can work out, the idea behind the FP was “lets try this crazy idea out, hey look, it actually works!”. In this first paper, there wasn’t much theory why it actually works. As it turns out, pure mathematicians, have been looking at projection algorithms for a while, and have a few results proved about them. Mostly in convex spaces and/or Hilbert spaces. There is now research going on using these different projection algorithms. But still mostly it is a bit of black magic and we don’t know how far we can push these algorithms.

This is my current lot of research: looking at different projection algorithms and the feasibility pump.