Originally posted by: Zak86

Hi Guys,

I have to solve a binary LP with the Feasibility Pump Heuristic. Before that, i solve it without forcing any heuristic and i see that CPLEX ,by default, uses the branch and bound/cut algorithm. The output logs are something like that:

..............

Cover cuts applied:  1

Implied bound cuts applied:  45

Flow cuts applied:  2

Mixed integer rounding cuts applied:  28

Zero-half cuts applied:  25

Lift and project cuts applied:  1

Gomory fractional cuts applied:  1

Root node processing (before b&c):

Real time             =    4.32 sec. (1817.00 ticks)

......

When i enable the FP heuristic using cplex.setParam(IloCplex.Param.MIP.Strategy.FPHeur, 2) just before cplex.solve(), the output logs remain the same as if Cplex don't use the feasibility pump but always branch and cut .

This is strange because when modifying any other algorithm such as Simplex or  Barrier Optimizer through cplex.setParam (IloCplex.IntParam.RootAlg, IloCplex.Algorithm.Barrier), etc ..., the output logs change depending on the concerned algorithm .

What's the problem please ? am i really using the FP heuristic ? why do the output logs seem like that ?

Thank you,

Zak

I think you are misunderstanding. You cannot use the feasibility pump heuristic to solve a MIP. With the exception of extreme cases, this heuristic will never prove optimality.

CPLEX contains many heuristics that it calls internally to find good feasible solutions. The FPHeur only controls how CPLEX calls the feasibility pump heuristic internally. The parameter does not change the algorithm CPLEX uses to solve a MIP. You cannot invoke the feasibility pump heuristic as a stand-alone algorithm.

Originally posted by: Zak86

Dear Daniel,

Thank you for replying. I understand that the FP is not an exact method to get an optimal solution.

My aim is to solve my MIP ( precisely my binary LP ) in large scale  ( by increasing the number N as i have Min ( sum x[i] ) , with i in [1..N] )  . For small scenarios, the standard resolution of CPLEX (by default the branch and Bound/cut method ), i get Optimal solution status.  However, when just increasing N = n*n*n (from the value 5*5*5 To 6*6*6),   CPLEX runs during few days and consumes all the memory (140 Giga bytes RAM ! ) in the cluster without converging to the optimality.

So, as the optimality resolution doesn't converge (due to the rapidly-growing number of local binary variables and constraints when N grows), i was searching another way to find just a feasible solution in large scale.  

I read in litterature, ( the authors' book of the FP), that FP heuristic is " ...a way of finding a feasible solution for a MIP problem without branch and bound ....". Logically, that can likely reduce the convergence time! Fortunately, i find that FP is already integrated in CPLEX and that will avoid me spending time on programming it :-).

So, Please Daniel, How can i enable the Feasibility Pump in CPLEX heuristic to obtain a "feasible solution" for my binary LP, which command should i write?

Thank you very much for your help,

Zak 

Originally posted by: hllsen

Hi Zak,

(If you keep FP switched on) CPLEX uses FP to find feasible solutions, you don't need to do anything special to get those solutions.

If your issue is related to the solution time and you just need feasible solution then just set an appropriate time limit and after CPLEX terminates query the feasible solutions identified during the optimization (depending on the problem there may be lots of feasible solutions in the solution pool).  If there is not any feasible solutions in the solution pool after considerable amount of time, may be you need to experiment with the MIPEmphasis parameter.

Good luck,

h.