Version 3 (modified by stefan, 7 weeks ago) (diff) |
---|

The feasibility pump heuristic (CbcHeuristicFPump.cpp) is a very clever/simple heuristic. References are -

- Fischetti, L. Bertacco, and A. Lodi. A feasibility pump heuristic for general mixed-integer problems. Technical report, Universita di Bologna - D.E.I.S. - Operations Research, 2005.

and

- Fischetti, F. Glover, and A. Lodi. The feasibility pump. Mathematical Programming, 2005.

The basic idea (much simplified) is that you start with the relaxed continuous solution and then keep changing the objective function to try and minimize the sum of integer infeasibilities. If this goes to zero then you have a solution.

So, how long do you try? If you get a solution, can you get a better one? Even if you fail to get a solution, can you get any benefit? The answer to the second question is yes - by adding a constraint that says the objective must be better than this solution. The answer to the third question is also yes. By continually changing the objective, you are making the solution go all over the place but there will be variables which despite all this remain fixed at a value. maybe if you fix these variables and preprocess the resulting problem you will get a much smaller problem on which it will be worth doing a few nodes of branch and cut.

By default the Feasibility Pump heuristic is run at the start of CBC's branch and cut, but there are several ways to fine tune the heuristic. Before I answer any of those questions, I should mention one or two undocumented features. There are several parameters you can set to terminate the search early. One is "maxNodes". If you do maxN?? in Cbc it will say that the valid range is -1 to 2147483647. If you set maxNodes to 0, cbc will apply all cuts at root node and then terminate, but if you set it to -1, then the cuts will not be computed. This can save some time if all you want to do is find a heuristic solution. Also if "allowableGap" or "ratioGap" is set and a heuristic finds a solution which satisfies the gap criterion, then the code will also terminate before doing the node 0 cut computations. Finally I should mention the "doh" option. The full name of the parameter is doHeuristic. Normally Cbc does preprocessing and then enters branch and cut, where the first thing to be done is the heuristics phase. If a valid value for the objective is known then sometimes the preprocessing can do a better job as it can fix variables on reduced costs. One way of doing this is to run some heuristics, then do preprocessing and go into branch and cut. To do the feasibility pump then do preprocessing and then do feasibility pump inside branch and cut one would do -

cbc ....mps -feas both -doh -solve

Anyway back to tuning the feasibility pump. I should mention here that I will give the full name of the option but you can abbreviate it e.g. passFeasibilityPump is accepted if you enter passF. There are three options which affect the heuristic -

passfeasibilityPump - this says how many passes of feasibility pump to do. If less than 200 and hoptions flag not set then the heuristic will modify this number depending on how things are going.

pumpTune - this is a very complex parameter as more and more was loaded onto it. It is numeric of the form fedddcba where

a is 0,1,2,3. This is only used if the code is going to fix variables and try a mini branch and cut. 0 and 1 have the same meaning and just says - fix all integer variables which have remained at one bound all the time. 2 says - also fix those general integer variables which have stayed at an interior integral value. 3 says do all that and fix all continuous variables which have stayed at a bound. The default is 3.

b is used to fine tune how first solve is done. Even I have no clue what this does!

c - at present the only useful values are 0 and 1. 1 says to add a constraint forcing the objective to be better than some initial value. If the parameter "dextra1" is not set (i.e. is still zero) then this value is 5% more than continuous solution value. If dextra1 is set then this is used.

ddd says how many solutions to try and get. If 0 then the heuristic will exit after the first solution. If n then after n+1 solutions. After the first time a constraint is added forcing a better solution.

e can be 0,1,4,5. If 1 or 5 then the mini branch and cut phase is entered. If 4 or 5 then a different method is used to deal with general integer variables. The default method is to treat general integer variables as if they were continuous. When all 0-1 variables are satisfied then if any general are unsatisfied then all 0-1 variables are fixed and a few nodes of branch and bound are tried to satisfy the general integer variables. If 4/5 is set then the original method of Fischetti and Lodi is used which involves adding one constraint and variable for every general integer variable which is being pushed away from bound.

f if set then a fraction of the original objective is added in. This fraction will decay at each pass. Larger f gives a larger fraction.

Whew! So you think you have finished with options - no way.

hOptions (heuristic options). The first part of this applies to all heuristics, but only if one of the gap parameters are set to say end search early if gap is reached. If the 1 bit is set i.e. hOptions is odd then the heuristic phase is exited immediately the gap is achieved. The default behavior is to do all heuristics and then check. If the 2 bit is set then do exactly the number of passes specified. Normally if number of passes is 30 then the code will do up to 30 passes each major iteration. If the 4 bit is set and an initial cutoff is given then the code will relax this cutoff every 50 passes - so that an optimistic guess can be corrected. If the 8 bit is set then on the second and subsequent major iterations the cutoff will be changed if it does not look as is the code will find a solution.