Questions about the output of CPLEX

[Tiancivalen]

Dear all,

When solving a transportation problem (an integer programming model) using AMPL+CPLEX , the output was as follows:

CPLEX 12.6.2.0: optimal integer solution; objective 848
32842 MIP simplex iterations
0 branch-and-bound nodes
Tried aggregator 7 times
No basis.

Here I want to ask three questions about the above output, ranked by the importance:

(1) why so many MIP simplex iterations are used, but no branch-and-bound nodes are created?

(2) what does aggregator do? in what situation will it be triggered?

(3) what does No basis mean? does it matter?

Any help will be appreciated.

Thank you.

[Robert Fourer]

The important thing in this message is that CPLEX reported "optimal integer solution". That is your sign that the solve was successful and that you can use the solution that was returned to AMPL.

CPLEX's presolve phase, cut generation routines, and feasibility heuristics were able to solve your problem without any branch-and-bound search. Thus you see "0 branch-and-bound nodes". The "MIP simplex iterations" were used to solve the continuous relaxation of your problem and to re-solve after cuts were added. If you give the command

option cplex_options 'mipdisplay 2';

(or add mipdisplay 2 to your existing cplex_options string) before solving, then you will see more output from CPLEX including detailed simplex iteration counts.

You can ignore the "No basis" message which is normal for CPLEX MIP solves. Also "Tried aggregator 7 times" is a message from CPLEX's presolve phase which you can ignore when the solve was successful. We'll try to get these stray messages removed in the next release.

Bob Fourer
am...@googlegroups.com

=======

[Tiancivalen]

Thanks a lot, Robert. Your answer really helps.

I have one more question hoping you can give some advice:

when no branch-and-bound routines were performed, and a huge number of MIP simplex iterations were used, like in my case, is there any way to speed up the solution process by e.g. tuning the parameters of CPLEX?

In fact, I just want to get a good solution (not necessarily optimal) within limited calculation time.

Thank you.





在 2016年4月13日星期三 UTC+8下午10:36:52，Robert Fourer写道：

[Robert Fourer]

As a start you will need to set cplex_options to show a detailed log of CPLEX's progress, as explained in my previous post. Then you will see the number of constraints that were in your problem after CPLEX performed its presolve reductions. If the number of iterations divided by the number of constraints is less than 3, then the number of iterations is not really so huge, and the chances of improvement through tuning are not so great. Also you will see some information about the amount of time taken, and if it is only a few seconds then there is not much to be gained by tuning unless you are going to make a very large number of runs.

If you do want to try to speed up the solution process by tuning the CPLEX parameters, then you will have to study how a solver like CPLEX works at the root node, so that you can understand the log and the parameters. As a start you can look at the section on "Using CPLEX for Integer Programming" in this IBM document on CPLEX for AMPL: http://ampl.com/BOOKLETS/amplcplex122userguide.pdf. (They have not updated it since version 12.2 but it covers all of the basics that you need to know.)

Since CPLEX is finding and proving an optimal solution without any branch-and-bound search, options for stopping with a "good" solution are not applicable to the example you have given. However if you have other runs that do build a search tree, then you will find options for stopping the search in the IBM document mentioned above.

[Tiancivalen]

Thanks, Bob.

I tried to set the cplex_opitons. Now the more detailed output is as follows:

CPLEX 12.6.2.0: mipdisplay=2

integrality=0

absmipgap=1e-3

mipgap=0.1

boundstr=0

MIP Presolve eliminated 229269 rows and 92990 columns.

MIP Presolve modified 52620 coefficients.

Reduced MIP has 334462 rows, 391003 columns, and 4263166 nonzeros.

Reduced MIP has 390999 binaries, 4 generals, 0 SOSs, and 0 indicators.

Elapsed time = 103.22 sec. (10000.30 ticks) for 10% of probing (26972 vars fixed)

Elapsed time = 190.41 sec. (20002.18 ticks) for 28% of probing (30378 vars fixed)

Elapsed time = 256.42 sec. (30002.21 ticks) for 97% of probing (39933 vars fixed)

Probing fixed 112856 vars, tightened 0 bounds.

Probing changed sense of 421 constraints.

Probing time = 264.11 sec. (32136.62 ticks)

MIP Presolve eliminated 92282 rows and 114212 columns.

MIP Presolve modified 15320 coefficients.

Reduced MIP has 239308 rows, 273957 columns, and 3385921 nonzeros.

Reduced MIP has 273953 binaries, 4 generals, 0 SOSs, and 0 indicators.

Elapsed time = 72.27 sec. (10000.28 ticks) for 32% of probing (12016 vars fixed)

Probing fixed 19126 vars, tightened 0 bounds.

Probing time = 88.14 sec. (12510.27 ticks)

MIP Presolve eliminated 15968 rows and 20729 columns.

MIP Presolve modified 1954 coefficients.

Reduced MIP has 222185 rows, 252132 columns, and 3067282 nonzeros.

Reduced MIP has 252128 binaries, 4 generals, 0 SOSs, and 0 indicators.

Probing fixed 78 vars, tightened 0 bounds.

Probing time = 4.36 sec. (820.13 ticks)

Clique table members: 970484.

MIP emphasis: balance optimality and feasibility.

MIP search method: dynamic search.

Parallel mode: deterministic, using up to 8 threads.

Root relaxation solution time = 26.49 sec. (6432.67 ticks)

 

        Nodes                                         Cuts/

   Node  Left     Objective  IInf  Best Integer    Best Bound    ItCnt     Gap

 

      0     0      847.0000    92                    847.0000    25811        

*     0+    0                          849.0000      847.0000             0.24%

 

Root node processing (before b&c):

  Real time             =  452.59 sec. (126237.81 ticks)

Parallel b&c, 8 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) =  452.59 sec. (126237.81 ticks)

CPLEX 12.6.2.0: optimal integer solution within mipgap or absmipgap; objective 849

25811 MIP simplex iterations

0 branch-and-bound nodes

absmipgap = 2, relmipgap = 0.00235571

Tried aggregator 3 times

No basis.

The number of iterations is actually not huge, since the number of iterations divided by the number of constraints is about 25811/222185 << 3.

After noticing that the most time consuming operation is probing, I tried to disable probing via cplex_options. But it didn't help at all. The solution time even increased dramatically.

I found that the root relaxation solution time is only 26.49s. So, should I guess that my problem is actually not so difficult to solve fast, using perhaps some decomposition schemes like branch and price?

Thank you.

在 2016年4月15日星期五 UTC+8下午11:05:35，Robert Fourer写道：

[Robert Fourer]

CPLEX gives you some options to reduce the amount of probing without disabling it entirely. By default CPLEX makes an automatic choice between 'probe=1' or 'probe=2' or 'probe=3' and in some cases you may reduce the amount of probing by explicitly setting 'probe=1' or 'probe=2'. Alternatively you can use the probetime option to limit the time spent probing -- for example, 'probetime=100' to limit problem to 100 seconds. These options might help if the earlier probing steps are the most effective; but you will have to experiment to see how they work for your problem.

Note that your setting of 'mipgap=0.1' is already causing CPLEX's search to stop early. At the root node CPLEX quickly finds a lower bound of 847 an integer-feasible solution with objective 849, giving a relative gap of (849-847)/849 = 0.00235571; since this is smaller than 0.1, the CPLEX run stops and returns the solution that gives 849. The true optimal objective could by 849, 848, or 847, but the only way to find out would be to set mipgap smaller, which would probably result in a longer run.

Because the root relaxation allows all of the integer variables to be fractional, it can be easy to solve. This does not necessarily imply that the mixed-integer program will be easy to solve by a decomposition method.