Topic
  • 2 replies
  • Latest Post - ‏2013-06-03T08:55:45Z by TobiasAchterberg
Aaronlidebiao
Aaronlidebiao
10 Posts

Pinned topic How to speed up the search for the Binary MIP?

‏2013-05-29T20:32:20Z |

Hi,

I have a model in CPLEX IDE and all the variables are binary type.

When I run the large data, the search seems very struggling.

Here is the engine log:

"

 

Tried aggregator 3 times.
MIP Presolve eliminated 848 rows and 1 columns.
Aggregator did 1370 substitutions.
Reduced MIP has 3246 rows, 164990 columns, and 965788 nonzeros.
Reduced MIP has 161696 binaries, 0 generals, 0 SOSs, and 2544 indicators.
Presolve time = 1.87 sec. (1173.12 ticks)
Found incumbent of value 2.5301771e+007 after 2.37 sec. (1519.64 ticks)
Probing time = 0.75 sec. (389.73 ticks)
Cover probing fixed 0 vars, tightened 49 bounds.
Tried aggregator 1 time.
MIP Presolve eliminated 0 rows and 98 columns.
Reduced MIP has 3246 rows, 164892 columns, and 965690 nonzeros.
Reduced MIP has 161647 binaries, 0 generals, 0 SOSs, and 2446 indicators.
Presolve time = 1.11 sec. (519.07 ticks)
Probing time = 0.16 sec. (53.53 ticks)
Clique table members: 3448.
MIP emphasis: balance optimality and feasibility.
MIP search method: dynamic search.
Parallel mode: deterministic, using up to 24 threads.
Root relaxation solution time = 26.88 sec. (33324.87 ticks)
 
        Nodes                                         Cuts/
   Node  Left     Objective  IInf  Best Integer    Best Bound    ItCnt     Gap
 
*     0+    0                      2.53018e+007        0.0000      231  100.00%
      0     0  9915021.0000  1628  2.53018e+007  9915021.0000      231   60.81%
      0     0  9915021.0000  1650  2.53018e+007     Cuts: 633    77824   60.81%
      0     0  9915021.0000  1655  2.53018e+007     Cuts: 384   270568   60.81%
Heuristic still looking.
Heuristic still looking.
      0     2  9915021.0000  1644  2.53018e+007  9915021.0000   270568   60.81%
Elapsed time = 2507.97 sec. (2779243.13 ticks, tree = 0.01 MB, solutions = 1)
      1     3  9927543.9167   992  2.53018e+007  9915021.0000   526442   60.81%
      2     4  9931688.2493  1654  2.53018e+007  9915021.0000   832350   60.81%
      4     6  9927543.9167  1662  2.53018e+007  9915021.0000  1089284   60.81%
      7     9  9927543.9167  1654  2.53018e+007  9915021.0000  1508998   60.81%
      9    11  9915021.0000  1647  2.53018e+007  9915021.0000  1536084   60.81%
     11    13  9931688.2493  1652  2.53018e+007  9915021.0000  1546619   60.81%
     14    16  9931688.2493  1652  2.53018e+007  9915021.0000  1547227   60.81%
     16    18  9927543.9167  1655  2.53018e+007  9915021.0000  1553405   60.81%
     17    19  9925806.8158  1655  2.53018e+007  9915021.0000  1596410   60.81%
     21    23  9943696.4434  1647  2.53018e+007  9915021.0000  1675047   60.81%
Elapsed time = 7441.67 sec. (8559054.84 ticks, tree = 0.01 MB, solutions = 1)
     24    26  9943696.4434  1647  2.53018e+007  9915021.0000  1710662   60.81%
     26    28  9947918.0114  1643  2.53018e+007  9915021.0000  1731320   60.81%
     28    30  9927543.9167  1655  2.53018e+007  9915021.0000  1735812   60.81%
     29    31  9924877.2500  1664  2.53018e+007  9915021.0000  1736118   60.81%
     30    32  9916213.9472  1669  2.53018e+007  9915021.0000  1753932   60.81%

"

Any settings will speed up the search for the Binary variable type MIP? Thanks.

 

  • PaulRubin
    PaulRubin
    49 Posts

    Re: How to speed up the search for the Binary MIP?

    ‏2013-05-31T21:13:57Z  

    All sorts of parameter settings may speed up (or slow down) the solution process, but it is all very problem-specific. I suggest that you create a smaller instance of your problem, one that can be solved in reasonable time but is not trivial, and then use the CPLEX tuning tool to try to find better parameter settings than the defaults.

    Paul

  • TobiasAchterberg
    TobiasAchterberg
    8 Posts

    Re: How to speed up the search for the Binary MIP?

    ‏2013-06-03T08:55:45Z  

    If you are allowed to share your problem instance, I would be very interested in having a look at them. Maybe I can come up with some suggestions.

    You can send the model (preferably as a *.sav.gz file) to my email address at achterbeg [at] de [dot] ibm [dot] com (and refer to this forum post).

     

    Tobias