MIP Gap problem

[Luke Li]

Hi everyone,

I am using Cplex as my solver to solve an simple MIP problem.

The problem can be solved, but the solution has a big gap from optimum.

Since I didn't set 'mipgap' or 'absmipgap' in .run file, I thought it should run until gap reaches 0.

I'm wondering whether it is possible to reduce this gap by put some command on cplex? 

Any suggestion will be greatly appreciated. 

Regards

Luke

Below is the solving message.

################################################

Presolve eliminates 110 constraints and 1375 variables.

Adjusted problem:

2910 variables:

144 binary variables

2766 linear variables

565 constraints, all linear; 20975 nonzeros

1 linear objective; 2567 nonzeros.

CPLEX 12.2.0.0: mipdisplay 2

mipinterval 100

MIP Presolve eliminated 219 rows and 332 columns.

MIP Presolve modified 5240 coefficients.

Reduced MIP has 298 rows, 2530 columns, and 13805 nonzeros.

Reduced MIP has 37 binaries, 0 generals, 0 SOSs, and 0 indicators.

Probing time =    0.00 sec.

Reduced MIP has 298 rows, 2530 columns, and 13805 nonzeros.

Reduced MIP has 37 binaries, 0 generals, 0 SOSs, and 0 indicators.

Found feasible solution after 0.02 sec.  Objective = 2.5364e+007

Probing time =    0.00 sec.

Clique table members: 51.

MIP emphasis: balance optimality and feasibility.

MIP search method: dynamic search.

Parallel mode: deterministic, using up to 4 threads.

Root relaxation solution time =    0.03 sec.

        Nodes                                         Cuts/

   Node  Left     Objective  IInf  Best Integer     Best Node    ItCnt     Gap

*     0+    0                      2.53640e+007                    824     --- 

*     0+    0                      1.03120e+007                    824     --- 

      0     0  4317400.0000    16  1.03120e+007  4317400.0000      824   58.13%

*     0+    0                      6032000.0000  4317400.0000      824   28.43%

      0     0        cutoff        6032000.0000  4317400.0000      824   28.43%

Elapsed real time =   0.09 sec. (tree size =  0.00 MB)

Root node processing (before b&c):

  Real time             =    0.08

Parallel b&c, 4 threads:

  Real time             =    0.00

  Sync time (average)   =    0.00

  Wait time (average)   =    0.00

                          -------

Total (root+branch&cut) =    0.08 sec.

CPLEX 12.2.0.0: optimal integer solution; objective 6032000

824 MIP simplex iterations

0 branch-and-bound nodes

###################################################

[Paul]

On Wednesday, June 20, 2012 6:40:57 AM UTC-4, Luke Li wrote:

Since I didn't set 'mipgap' or 'absmipgap' in .run file, I thought it should run until gap reaches 0.

Default values for CPLEX are 1e-06 for the absolute gap and 1e-04 for the relative gap, although the README file for the AMPL-CPLEX connector claims the default for the absolute gap is 0.  (The README is dated 2006, I think, so I'm not sure it's current.)
 

I'm wondering whether it is possible to reduce this gap by put some command on cplex?

option cplex_options  "absmipgap=0 mipgap=0";  (although I'd recommend nonzero values to shorten run time).

Paul

[Luke Li]

Hi Paul,

Thanks for the suggestion.

Regards

Luke

[Robert Fourer]

I think there is a glitch in the CPLEX output here, so that it is reporting a large gap when it fact it has proved optimality at the root node.  Perhaps this problem has been fixed in the latest version (12.4).  Or, you could confirm CPLEX's answer by sending the same problem to another solver, such as Gurobi.

 

Current defaults for all of the CPLEX directives are given in the summary at

 

   http://www.netlib.org/ampl/solvers/cplex/README.cplex

 

The default absmipgap is 0 but the default mipgap is .0001 (meaning .01%).  CPLEX allows you to reduce the mipgap to as low as 1e-9, but not to zero.  But it will not return a solution with a 28% gap as "optimal".

 

Bob Fourer

4...@ampl.com

 

 

From: am...@googlegroups.com [mailto:am...@googlegroups.com]

On Behalf Of Luke Li
Sent: Wednesday, June 20, 2012 5:41 AM
To: am...@googlegroups.com
Subject: [AMPL 5927] MIP Gap problem

[Luke Li]

Hi Bob,

Thanks for the advice.

Regards
Luke