Originally posted by: JaimeFernandez

While solving a pretty large but simple MIP on CPLEX 12.6.1 (running on a 64 bit Windows 7), the branch and cut process seems to hang.

It does not actually hang, but rather keeps indefinitely looking for a better integer solution, which is never found.

The following is the final part of the output:

Elapsed time = 2832.70 sec. (3418758.51 ticks, tree = 484.68 MB, solutions = 2)
 896094 71920        cutoff           2525.0000     2504.6667  4536005    0.81%
 897075 71980        cutoff           2525.0000     2504.6667  4541073    0.81%
 898140 72209        cutoff           2525.0000     2504.6667  4546359    0.81%
 899058 71883        cutoff           2525.0000     2504.6667  4552707    0.81%
 899980 71755     2504.6667    24     2525.0000     2504.6667  4558265    0.81%
 901067 71957        cutoff           2525.0000     2504.6667  4563252    0.81%
 901979 72074     2504.6667    30     2525.0000     2504.6667  4568905    0.81%
 903029 72148        cutoff           2525.0000     2504.6667  4573899    0.81%
 903802 71926     2504.6667    30     2525.0000     2504.6667  4579546    0.81%
 904759 72217        cutoff           2525.0000     2504.6667  4584395    0.81%
Elapsed time = 2871.64 sec. (3459392.67 ticks, tree = 485.04 MB, solutions = 2)
 905820 72268     2504.6667    31     2525.0000     2504.6667  4588845    0.81%
 907172 72894     2504.6667    29     2525.0000     2504.6667  4592952    0.81%
 908226 72858        cutoff           2525.0000     2504.6667  4597708    0.81%
 909043 72501     2504.6667    30     2525.0000     2504.6667  4603497    0.81%
 910047 72648     2504.6667    31     2525.0000     2504.6667  4608082    0.81%
 911156 72725        cutoff           2525.0000     2504.6667  4612835    0.81%
 912246 72942        cutoff           2525.0000     2504.6667  4616996    0.81%
 913188 72702     2504.6667    28     2525.0000     2504.6667  4623554    0.81%
 914260 72772     2504.6667    30     2525.0000     2504.6667  4628345    0.81%
 915406 73038     2504.6667    31     2525.0000     2504.6667  4632672    0.81%
Elapsed time = 2912.27 sec. (3497568.91 ticks, tree = 490.50 MB, solutions = 2)
 916892 73957     2504.6667    30     2525.0000     2504.6667  4636299    0.81%
 917738 73736     2504.6667    25     2525.0000     2504.6667  4641323    0.81%
 918661 73777     2504.6667    33     2525.0000     2504.6667  4646037    0.81%
 920377 74992        cutoff           2525.0000     2504.6667  4650314    0.81%
 921158 74936     2504.6667    31     2525.0000     2504.6667  4655203    0.81%
 922326 75265        cutoff           2525.0000     2504.6667  4662038    0.81%
 923420 75640        cutoff           2525.0000     2504.6667  4665277    0.81%
 924554 75938     2504.6667    28     2525.0000     2504.6667  4669396    0.81%
 925730 76196        cutoff           2525.0000     2504.6667  4673396    0.81%
 926708 76112    infeasible           2525.0000     2504.6667  4677992    0.81%
Elapsed time = 2948.61 sec. (3535737.13 ticks, tree = 510.99 MB, solutions = 2)
 927670 75866        cutoff           2525.0000     2504.6667  4683272    0.81%
 928717 75929        cutoff           2525.0000     2504.6667  4688305    0.81%
 929709 75814        cutoff           2525.0000     2504.6667  4693872    0.81%
 930040 75852     2504.6667    31     2525.0000     2504.6667  4695395    0.81%
 931051 75718        cutoff           2525.0000     2504.6667  4700301    0.81%
 932052 75754     2504.6667    27     2525.0000     2504.6667  4705942    0.81%
 932880 75483     2504.6667    27     2525.0000     2504.6667  4711551    0.81%
 933473 75207        cutoff           2525.0000     2504.6667  4716143    0.81%
 934492 75196        cutoff           2525.0000     2504.6667  4720828    0.81%

Gomory fractional cuts applied:  2

Root node processing (before b&c):
  Real time             =    5.27 sec. (4951.65 ticks)
Sequential b&c:
  Real time             = 2994.00 sec. (3584056.75 ticks)
                          ------------
Total (root+branch&cut) = 2999.27 sec. (3589008.40 ticks)

Solution pool: 2 solutions saved.

MIP - Aborted, integer feasible:  Objective = 2.5250000000e+003
Current MIP best bound = 2.5046666667e+003 (gap = 20.3333, 0.81%)
Solution time = 2999.48 sec.  Iterations = 4735412  Nodes = 936896 (74647)
Deterministic time = 3589008.49 ticks  (1196.54 ticks/sec)

As you can see I aborted the process after 3000 seconds.

This MIP is part of a much larger scheduling problem. Each MIP represents the problem for each week. MIPs for other weeks (which are quite similar to the problematic MIP in question here) usually take less than 10 seconds to solve. That's why it's specially odd that the problematic MIP cannot get solved in les than 3000 seconds.

I attached the model and parameter files in case they are needed to reproduce the problem.

Originally posted by: EXCT_RALF_GOLLMER

Hi,

I think you should tune your CPLEX settings a bit for all the week MIPs.

Especially I do not understand why you don't use symmerty breaking, since your problem seems to exhibit symmetries.

Try e.g.

CPLEX> Changed parameter settings:
mip cuts gomory 2
mip cuts zerohalfcut 2
mip interval 100
mip strategy probe -1
mip tolerances absmipgap 0
mip tolerances mipgap 0
preprocessing repeatpresolve 3
preprocessing symmetry 5
simplex tolerances feasibility 1e-09
simplex tolerances optimality 1e-09
threads 1

With these settings it solved on my Core 2 Q9300 in the root node after  less than 9 secs.

probing doesn't help in that specific problem, that's why I switched it off. This might be different for other weeks.

CPLEX> New value for default parallel thread count: 1
CPLEX> Problem 'MIP_MODEL_Comparator_D_Week_37.lp' read.
Read time = 0.43 sec. (5.64 ticks)
CPLEX> New value for interval for printing mixed integer node display: 100
CPLEX> New value for absolute mixed integer optimality gap tolerance: 0
CPLEX> New value for mixed integer optimality gap tolerance: 0
CPLEX> New value for feasibility tolerance: 1e-09
CPLEX> New value for reduced cost optimality tolerance: 1e-09
CPLEX> New value for probing strategy: -1
CPLEX> New value for repeat mip presolve: 3
CPLEX> New value for indicator for symmetric reductions: 5
CPLEX> New value for type of Gomory fractional cut generation: 2
CPLEX> New value for type of zero-half cut generation: 2
CPLEX> Found incumbent of value 8.1917751e+08 after 0.00 sec. (2.13 ticks)
Tried aggregator 1 time.
MIP Presolve eliminated 0 rows and 1 columns.
MIP Presolve added 42 rows and 42 columns.
Reduced MIP has 134 rows, 33509 columns, and 350400 nonzeros.
Reduced MIP has 33383 binaries, 126 generals, 0 SOSs, and 0 indicators.
Presolve time = 0.38 sec. (138.32 ticks)
Tried aggregator 1 time.
MIP Presolve eliminated 42 rows and 42 columns.
MIP Presolve added 42 rows and 42 columns.
Reduced MIP has 134 rows, 33509 columns, and 350400 nonzeros.
Reduced MIP has 33383 binaries, 126 generals, 0 SOSs, and 0 indicators.
Presolve time = 0.41 sec. (137.46 ticks)
Clique table members: 50.
MIP emphasis: balance optimality and feasibility.
MIP search method: dynamic search.
Parallel mode: none, using 1 thread.
Root relaxation solution time = 0.36 sec. (213.22 ticks)

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

*     0+    0                       8.19178e+08        0.0000           100.00%
      0     0     2357.7692    51   8.19178e+08     2357.7692      324  100.00%
      0     0     2364.3333    46   8.19178e+08       Cuts: 4      348  100.00%
      0     0     2364.3333    48   8.19178e+08       Cuts: 5      362  100.00%
      0     0     2375.0000    51   8.19178e+08       Cuts: 2      416  100.00%
*     0+    0                       3.27664e+07     2375.0000            99.99%
*     0+    0                       1.63847e+07     2375.0000            99.99%
*     0+    0                       1.63808e+07     2375.0000            99.99%
*     0+    0                         5167.0000     2375.0000            54.04%
      0     0     2375.0000    55     5167.0000   ZeroHalf: 5      427   54.04%
*     0+    0                         2525.0000     2375.0000             5.94%

Repeating presolve.
Tried aggregator 2 times.
MIP Presolve eliminated 27 rows and 25120 columns.
MIP Presolve modified 6711 coefficients.
Aggregator did 25 substitutions.
Reduced MIP has 82 rows, 8364 columns, and 74454 nonzeros.
Reduced MIP has 8339 binaries, 25 generals, 0 SOSs, and 0 indicators.
Presolve time = 0.22 sec. (110.95 ticks)
Tried aggregator 1 time.
Reduced MIP has 82 rows, 8364 columns, and 74454 nonzeros.
Reduced MIP has 8339 binaries, 25 generals, 0 SOSs, and 0 indicators.
Presolve time = 0.07 sec. (28.52 ticks)
Represolve time = 0.67 sec. (267.42 ticks)
Clique table members: 50.
MIP emphasis: balance optimality and feasibility.
MIP search method: dynamic search.
Parallel mode: none, using 1 thread.
Root relaxation solution time = 0.07 sec. (48.63 ticks)

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

*     0+    0                         2525.0000     2375.0000             5.94%
      0     0     2375.0000    45     2525.0000     2375.0000      622    5.94%
      0     0        cutoff           2525.0000                    622    0.00%
Elapsed time = 8.80 sec. (4731.78 ticks, tree = 0.00 MB, solutions = 6)

Zero-half cuts applied:  2
Gomory fractional cuts applied:  1

Root node processing (before b&c):
  Real time             =    8.81 sec. (4733.87 ticks)
Sequential b&c:
  Real time             =    0.00 sec. (0.00 ticks)
                          ------------
Total (root+branch&cut) =    8.81 sec. (4733.87 ticks)

I could reproduce the b&c process being stuck at 0.81% gap with other settings.

Branch&Bound in the end is a lottery, the progress heavily depends on the settings you use. 

Best regards

Ralf Gollmer

Originally posted by: JaimeFernandez

Thanks a lot Ralf, that was quite useful.

By using some of those parameter settings you suggested changing from their default values CPLEX managed to find an optimal solution in a reasonable amount of time (around 10 seconds, even less in some cases).

Just out of curiosity: what is it exactly about Branch&Bound that makes it a lottery whether or not it progresses rapidly while looking for the optimal solution?

Again, thanks for your time.

Best regards,

Jaime Fernandez

Originally posted by: EXCT_RALF_GOLLMER

The Branch&Bound tree is determined by two things: the choice of the next node to be branched and the choice of the (non-integer) variable to be branched on. Both decisions depend on the variable values in the solutions of the node problems and the resulting bounds. A change of CPLEX parameters like simplex tolerances, aggressivity level of cuts, or even the number of threads allocated to the program (resulting in different times and order, how feasible solutions are found via heuristics) might easily change these choices, resulting in a different tree.  A small change at one point of the solution process might lead to a radically different progress of the total procedure.

This way e.g. allocating more threads to the same problem might even lead to much longer solution times - though one could expect that it always helps to invest more computing power.

At a certain node just looking at the solution it is nearly impossible to know which branching decision would  be the best. A wrong choice might produce a lot of nodes with similar objective bounds, which need to be branched further, resulting in a very slow progress.

This is especially true if a problem exhibits symmetries. If e.g. there are binary variables reflecting the on/off status of facilities with identical cost coefficients the bounds would be just dependent on how many of these are on, not which ones. Thus a huge number of 0-1-vectors within the solution would lead to equivalent problems, a lot of which might have to be branched further before a change of bounds is reached. IF it is possible in such a  problem to express all dependencies and conditions in an aggregate way (using just one general integer variable expressing the number of facilities in on state) one could at least partly eliminate this adverse effect.

If from the meaning of the variables it is clear that some branching decisions are most important, better progress could be achieved by specifying this importance by assigning biger weights in a branching order.

For the special posted problem a solution could be found without branching in the root node by adding the right cuts and/or increasing the effort spent for heuristics.

Since there are so many possibilities of influencing by parameters, the consequences of which could not completely be foreseen, I think of it as something like a lottery. The only chance is to test combinations of parameter choices which seem to be reasonable for the problem. This effort and the computing time spent in the tests pays off, if many similar problems have to solved in the sequel.

I wish you success with solving your scheduling problem (this class is known to be especially hard)

Ralf
 

Originally posted by: JaimeFernandez

Thank you for your detailed response and for your help.

I can now clearly see how the many symmetries in my model may be negatively affecting the branch&bound process.

I will look for a way to break them, ar at least group them into more general variables.

Sincerely,

Jaime