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

Problems with modeling
Post Reply
whan1013
User
User
Posts: 3
Joined: 1 week ago

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

Post by whan1013 » 1 week ago

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.
Attachments
SC_190225(mp,inv).gms
(13.33 KiB) Downloaded 4 times

User avatar
bussieck
Moderator
Moderator
Posts: 268
Joined: 2 years ago

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

Post by bussieck » 1 week ago

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

-Michael

whan1013
User
User
Posts: 3
Joined: 1 week ago

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

Post by whan1013 » 1 week ago

Here is my datafile.
Attachments
SC_input_mp_TXT8D300C100W25_190225.xlsx
(115.73 KiB) Downloaded 3 times

User avatar
bussieck
Moderator
Moderator
Posts: 268
Joined: 2 years ago

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

Post by bussieck » 1 week ago

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

User avatar
bussieck
Moderator
Moderator
Posts: 268
Joined: 2 years ago

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

Post by bussieck » 1 week ago

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
User
User
Posts: 3
Joined: 1 week ago

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

Post by whan1013 » 1 week ago

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?

Post Reply