Problem with solving MIP with CPLEX (extremely low speed convergence)

[whan1013]

Dear all

Hi guys
It's my first post in this forum. I hope that I chose the right thread for my question.
I am modeling the supply chain optimization MILP model of biorefinery which determines location, capacity, and pathway of biorefineries and when they will be constructed.
In solving this problem with CPLEX, the relative gap of the problem decreases extremely slow than I expected. It took about 2 days to get an optimal solution.
I tried mipemphasis 2 option, but the execution time was not reduced much.
I attached the model file. Please help me.

Thanks.

[bussieck]

You might want to share the Excel workbook SC_input_mp_TXT8D300C100W25_190225.xlsx so one can experiment.

-Michael

[whan1013]

Here is my datafile.

[bussieck]

You get quickly below very reasonable gap (<3%):

Code: Select all

Elapsed time = 196.51 sec. (253073.64 ticks, tree = 12.86 MB, solutions = 16)
    780   143   9.83385e+08    41   1.00967e+09   9.83365e+08   112971    2.61%

Your data and model error are most likely much bigger, so from a practical point of view the problem is solved. If you need the proven optimum (for theoretical reasons) you probably need to experiment with different formulations of the model.

-Michael

[bussieck]

BTW, Gurobi (in default) solved the problem on my machine (i7-4770) in 7.2 hours:

Code: Select all

               S O L V E      S U M M A R Y

     MODEL   biorefinery         OBJECTIVE  z
     TYPE    MIP                 DIRECTION  MINIMIZE
     SOLVER  GUROBI              FROM LINE  251

**** SOLVER STATUS     1 Normal Completion         
**** MODEL STATUS      1 Optimal                   
**** OBJECTIVE VALUE       1001068793.2410

 RESOURCE USAGE, LIMIT      25828.258 1000000000.000
 ITERATION COUNT, LIMIT 210951898    2000000000

It also warns you about problematic scaling of the model:

Code: Select all

 Coefficient statistics:
 Matrix range     [3e-03, 1e+11]
  Objective range  [1e+00, 1e+00]
  Bounds range     [1e+00, 1e+00]
  RHS range        [1e+00, 2e+09]
Warning: Model contains large matrix coefficient range
Warning: Model contains large rhs
         Consider reformulating model or setting NumericFocus parameter
         to avoid numerical issues.

Cplex (with option datacheck=2) also reports on issues of the model (just an excerpt):

Code: Select all

CPLEX Warning  1039: Chain of symmetry breaking inequalities of length 7: ('U(1.400.1.8)', 'U(1.400.1.7)', ..., 'U(1.400.1.1)').
CPLEX Warning  1047: Decimal part of coefficients in constraint 'Eq5(1.1)' are fractions and can be scaled with 11/3.
CPLEX Warning  1048: Detected constraint with wide range of coefficients. In constraint 'Eq5(1.2)' the ratio of largest and smallest (in absolute value) coefficients is 1.20698e+08.

-Michael

[whan1013]

So we can say it's long execution time is due to bad scaling of the parameters?
But though after fixed it, there were no significant differences.
What else can I try to speed up the solution?