Originally posted by: alamaranka

Hi,

I have a relatively small MIP problem to solve. See below for Cplex log during the solve. Cplex cannot reach the target gap in the given time. This looks awkward to me. Is it normal?

CPLEX logs:

CPXPARAM_TimeLimit 60
CPXPARAM_Threads 1
CPXPARAM_MIP_Tolerances_MIPGap  0.01
Tried aggregator 2 times.
MIP Presolve eliminated 932 rows and 787 columns.
MIP Presolve modified 323 coefficients.
Aggregator did 368 substitutions.
Reduced MIP has 343 rows, 268 columns, and 881 nonzeros.
Reduced MIP has 81 binaries, 120 generals, 0 SOSs, and 0 indicators.
Presolve time = 0.01 sec. (2.32 ticks)
Found incumbent of value 2.1056929e+07 after 0.01 sec. (2.81 ticks)
Probing fixed 0 vars, tightened 3 bounds.
Probing time = 0.00 sec. (0.13 ticks)
Tried aggregator 1 time.
Reduced MIP has 343 rows, 268 columns, and 881 nonzeros.
Reduced MIP has 81 binaries, 120 generals, 0 SOSs, and 0 indicators.
Presolve time = 0.00 sec. (0.61 ticks)
Probing time = 0.00 sec. (0.13 ticks)
Clique table members: 60.
MIP emphasis: balance optimality and feasibility.
MIP search method: dynamic search.
Parallel mode: deterministic, using up to 8 threads.
Root relaxation solution time = 0.00 sec. (0.77 ticks)

What makes you think this problem is simple? Whether a problem is easy or hard to solve does not only depend on its size. It mainly depends on the problem's structure. So what you see may be very well expected.

If you post your model or at least the log we try to investigate. Maybe there are some parameters settings that can help in your case.

Originally posted by: alamaranka

I agree that the problem size is not the only dimension for a problem being hard to easy. But still it did not seem normal at the first glance. 

Right after posting the question here, I realized that the problem is with the large coefficients in b vector, in particular with BIG_M used in the constraints. Reducing it resolved the problem. I know that large coefficients make the problem harder, but I cannot explain why in a theoretical point of view. Could you help me to understand the theoretical reason, other than numerical issues caused by these large numbers?

Thank you.

Consider the trivial problem z = min {10x | 5 <= y <= Mx, x binary, y >= 0}. This would be solved by presolve, but for illustration purposes assume presolve is turned off. The optimal solution is clearly x = 1, y = 5 with objective value z* = 10. When you solve the LP relaxation, however, you get the solution y = 5, x = 5/M, z_LP = 50/M. The larger M is, the smaller z_LP is, i.e., the looser the LP relaxation bound is.

Now translate that to a meaningful problem. The larger M, the looser the LP bounds, which means the harder it is to prune nodes. (The looser bounds may also affect how CPLEX attacks the search tree, meaning how much time it spends in unproductive portions of the tree.)

Originally posted by: alamaranka

Thank you for this nice explanation, very intuitive. Regards.