Problems finding a feasible solution in a MIP

Question

I am using CPLEX with Julia using the package JuMP to solve a MIP problem. In a small instance, I have tested my problem but, after 10 minutes, nothing happens. I have defined the following parameters in CPLEX:

1. set_optimizer_attribute(modelo,"CPX_PARAM_ZEROHALFCUTS",2) -->> Generate zero-half cuts aggressively
2. set_optimizer_attribute(modelo,"CPXPARAM_MIP_Cuts_Covers",2) -->> Generate cover cuts aggressively
3. set_optimizer_attribute(modelo,"CPXPARAM_MIP_Strategy_SubAlgorithm",1) -->> Emphasize feasibility over optimality

The branch-and-bound does not even begin. Look the CPLEX report:

CPXPARAM_TimeLimit                               600
CPXPARAM_MIP_Cuts_Covers                         2
CPXPARAM_MIP_Tolerances_MIPGap                   0.01
CPXPARAM_MIP_Strategy_SubAlgorithm               1
CPXPARAM_MIP_Cuts_ZeroHalfCut                    2
Warning:  Non-integral bounds for integer variables rounded.
Warning:  No solution found from 1 MIP starts.
Retaining values of one MIP start for possible repair.

Root node processing (before b&c):
  Real time             =  600.11 sec. (206099.96 ticks)
Parallel b&c, 12 threads:
  Real time             =    0.00 sec. (0.00 ticks)
  Sync time (average)   =    0.00 sec.
  Wait time (average)   =    0.00 sec.
                          ------------
Total (root+branch&cut) =  600.11 sec. (206099.96 ticks)

In another test, I used all of the default parameters but the result was the same.

My problem does not have any big-$M$ usage in the formulation.

Is there a combination of CPLEX parameters that accelerate obtaining an integer feasible solution?

Answer 1

1. Aggressive cut generation will slow the processing of the root node (and other nodes, if cuts are generated beyond the root), so it's more likely to slow finding a feasible solution than to speed it up.
2. Setting MIP_Strategy_Subalgorithm to 1 tells CPLEX to use primal simplex on node subproblems. To emphasize finding feasible solutions, you want to set CPXPARAM_Emphasis_MIP to 1.
3. You might try setting CPXPARAM_Emphasis_MIP to 4 ("hidden feasibility") if setting 1 does not yield a good incumbent.
4. If you are using CPLEX 20.1, there is a new value (5) for CPXPARAM_Emphasis_MIP. The documentation describes this as "Emphasize finding high quality feasible solutions earlier".
5. The log indicates that you gave CPLEX an incomplete or infeasible solution as a warm-start, but that it failed to turn that into a feasible starting solution. If this came from some heuristic, you might look at whether you can improve the heuristic. Also, if you think the starting "solution" can be turned into a feasible solution, you can try increasing the value of CPXPARAM_MIP_Limits_RepairTries. (The default is to let CPLEX decide how much it tries to repair your starting solution.)
6. Assuming that you have no quadratic constraints, you can try using the feasibility pump heuristic, by setting CPXPARAM_MIP_Strategy_FPHeur to 1 or 2.

I would not try all of these at once, but rather experiment with one or two at a time.