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

Problems with modeling
whan1013
User
Posts: 3
Joined: 2 months ago

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

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.

Thanks.
Attachments
SC_190225(mp,inv).gms

bussieck
Moderator
Posts: 284
Joined: 2 years ago

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

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

-Michael

whan1013
User
Posts: 3
Joined: 2 months ago

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

Here is my datafile.
Attachments
SC_input_mp_TXT8D300C100W25_190225.xlsx

bussieck
Moderator
Posts: 284
Joined: 2 years ago

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

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
Moderator
Posts: 284
Joined: 2 years ago

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

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
Posts: 3
Joined: 2 months ago

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

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?