Page 1 of 1
Problem with solving MIP with CPLEX (extremely low speed convergence)
Posted: Thu Mar 07, 2019 12:35 pm
by 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.
Re: Problem with solving MIP with CPLEX (extremely low speed convergence)
Posted: Thu Mar 07, 2019 1:58 pm
by bussieck
You might want to share the Excel workbook SC_input_mp_TXT8D300C100W25_190225.xlsx so one can experiment.
-Michael
Re: Problem with solving MIP with CPLEX (extremely low speed convergence)
Posted: Thu Mar 07, 2019 3:56 pm
by whan1013
Here is my datafile.
Re: Problem with solving MIP with CPLEX (extremely low speed convergence)
Posted: Thu Mar 07, 2019 6:05 pm
by 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
Re: Problem with solving MIP with CPLEX (extremely low speed convergence)
Posted: Fri Mar 08, 2019 6:36 am
by 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
Re: Problem with solving MIP with CPLEX (extremely low speed convergence)
Posted: Mon Mar 11, 2019 2:56 am
by 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?