Originally posted by: RemiG

Hi,

I am trying to use the feasibility pump (FP) from CPLEX for MIP:

https://www.ibm.com/support/knowledgecenter/SSSA5P_12.8.0/ilog.odms.cplex.help/CPLEX/UsrMan/topics/discr_optim/mip/heuristics/47_feas_pump.html

https://www.ibm.com/support/knowledgecenter/SSSA5P_12.8.0/ilog.odms.cplex.help/CPLEX/Parameters/topics/FPHeur.html

First I activated the switch (CPX_PARAM_FPHEUR -> 1) and told CPLEX to stop as soon as it gets a solution (CPX_PARAM_INTSOLLIM -> 1). I notice that branching/dynamic search still happens so I read the parameters list (https://www.ibm.com/support/knowledgecenter/SSSA5P_12.8.0/ilog.odms.cplex.help/CPLEX/Parameters/topics/introListAlpha.html) and deactivate all preprocessing and everything that could be deactivated. I tried to stay at the root/firstnode with CPX_PARAM_NODELIM=0 or 1 but CPLEX stop before any solution. Without this last tuning I got the following display for the instance 10teams.mps from MIPLIB2017 (https://miplib.zib.de/instance_details_10teams.html):

CPXPARAM_Advance                                 0
CPXPARAM_Preprocessing_Fill                      0
CPXPARAM_Preprocessing_Aggregator                0
CPXPARAM_Preprocessing_Dependency                0
CPXPARAM_Preprocessing_Presolve                  0
CPXPARAM_Read_Scale                              -1
CPXPARAM_Simplex_Limits_Singularity              0
CPXPARAM_TimeLimit                               20
CPXPARAM_Preprocessing_Dual                      -1
CPXPARAM_Preprocessing_NumPass                   0
CPXPARAM_Preprocessing_Reduce                    0
CPXPARAM_Preprocessing_Linear                    0
CPXPARAM_Threads                                 1
CPXPARAM_Sifting_Iterations                      0
CPXPARAM_RandomSeed                              0
CPXPARAM_Sifting_Simplex                         0
CPXPARAM_Simplex_DynamicRows                     0
CPXPARAM_Benders_Strategy                        -1
CPXPARAM_MIP_Strategy_Backtrack                  1
CPXPARAM_MIP_Cuts_Cliques                        -1
CPXPARAM_Preprocessing_CoeffReduce               0
CPXPARAM_MIP_Cuts_Covers                         -1
CPXPARAM_MIP_Limits_Solutions                    1
CPXPARAM_MIP_Strategy_Order                      0
CPXPARAM_Preprocessing_BoundStrength             0
CPXPARAM_MIP_Strategy_HeuristicFreq              1
CPXPARAM_MIP_Limits_CutsFactor                   0
CPXPARAM_Preprocessing_Relax                     0
CPXPARAM_MIP_Strategy_PresolveNode               -1
CPXPARAM_MIP_Strategy_BBInterval                 0
CPXPARAM_MIP_Cuts_FlowCovers                     -1
CPXPARAM_MIP_Cuts_Implied                        -1
CPXPARAM_MIP_Strategy_Probe                      -1
CPXPARAM_MIP_Cuts_GUBCovers                      -1
CPXPARAM_MIP_Limits_GomoryCand                   1
CPXPARAM_MIP_Cuts_Gomory                         -1
CPXPARAM_MIP_Cuts_PathCut                        -1
CPXPARAM_MIP_Cuts_MIRCut                         -1
CPXPARAM_MIP_Cuts_Disjunctive                    -1
CPXPARAM_MIP_Limits_AggForCut                    0
CPXPARAM_MIP_Strategy_CallbackReducedLP          0
CPXPARAM_MIP_Limits_CutPasses                    -1
CPXPARAM_Preprocessing_Symmetry                  0
CPXPARAM_MIP_Strategy_RINSHeur                   -1
CPXPARAM_MIP_Limits_SubMIPNodeLim                1
CPXPARAM_Preprocessing_RepeatPresolve            0
CPXPARAM_MIP_Limits_RepairTries                  -1
CPXPARAM_MIP_Strategy_FPHeur                     1
CPXPARAM_MIP_Limits_EachCutLimit                 0
CPXPARAM_MIP_Cuts_ZeroHalfCut                    -1
CPXPARAM_MIP_Cuts_MCFCut                         -1
CPXPARAM_MIP_Strategy_KappaStats                 -1
CPXPARAM_MIP_Cuts_LiftProj                       -1
CPXPARAM_MIP_Cuts_LocalImplied                   -1
CPXPARAM_MIP_Cuts_BQP                            -1
CPXPARAM_MIP_SubMIP_Scale                        -1
CPXPARAM_MIP_SubMIP_NodeLimit                    1
CPXPARAM_Barrier_Algorithm                       3
CPXPARAM_Barrier_Display                         0
CPXPARAM_Barrier_Limits_Iteration                0
CPXPARAM_Barrier_Limits_Corrections              0
CPXPARAM_Network_Iterations                      0
Clique table members: 170.
MIP emphasis: balance optimality and feasibility.
MIP search method: dynamic search.
Parallel mode: none, using 1 thread.
Root relaxation solution time = 0.04 sec. (47.47 ticks)

        Nodes                                         Cuts/
   Node  Left     Objective  IInf  Best Integer    Best Bound    ItCnt     Gap

      0     0      917.0000   150                    917.0000     1132         
      0     2      917.0000    90                    917.0000     1132         
Elapsed time = 0.56 sec. (900.24 ticks, tree = 0.01 MB, solutions = 0)
      2     4      917.0000   135                    917.0000     1683         
      7     9      923.0000   140                    917.0000     2245         
     10    12      924.0000   152                    917.0000     3109         
     13    15      918.0000   145                    917.0000     3212         
     19    21      918.0000   140                    917.0000     3467         
     25    27      918.0000   141                    917.0000     3669         
     29    31      918.0000   138                    917.0000     4005         
     32    34      920.0000   147                    917.0000     4374         
     34    36      920.0000   144                    917.0000     4465         
     48    50      922.0000   144                    917.0000     5272         
Elapsed time = 3.00 sec. (4527.23 ticks, tree = 0.15 MB, solutions = 0)
*    53+   44                          924.0000      917.0000             0.76%

Root node processing (before b&c):
  Real time             =    0.56 sec. (900.24 ticks)
Sequential b&c:
  Real time             =    2.68 sec. (3972.26 ticks)
                          ------------
Total (root+branch&cut) =    3.24 sec. (4872.50 ticks)

Can't I use FP on it's own? I don't get how FP can be activated and still I have a branching happening.

Thanks in advance,

Rémi

No, you cannot run the feasibilty pump implement in CPLEX as a stand-alone heuristic.

If you turn on the feasibility pump parameter then this means that among all the other heuristics implemented in CPLEX, CPLEX will also use the feasibility pump heuristic when searching for (new) feasible solutions. These heuristics are applied periodically during tree search. Heuristics are applied with a certain budget and if the budget runs out then tree search continues (until CPLEX decides it is time for another round of heuristics).

Originally posted by: RemiG

Thank you for this answer. This is what I though... But can't I give FP a budget big enough to be use until it find a solution or the time limit stop CPLEX?

No, sorry, that is not possible.

Originally posted by: RemiG

Thank you for your time and this answer. No more questions about FP, thanks!