I would be grateful if anyone could tell me how the McCormick error can be reduced systematically. In fact, I would like to know how we can efficiently recognize and obtain a tighter relaxation for bi-linear terms when we use McCormick envelopes.
For instance, consider the simple optimization problem below. The results show a big McCormick error! Its MATLAB code is attached. Min Z = x^2 - x s.t. -1
Dear Morteza,
There are only two ways to reduce the NLP-LP relaxation gap.
The first, used by all commercial solvers is to do spatial branch-and-bound, which works similar as for {0,1} variables in MIP problems, but now you branch on the domain of the continuous variables. As the McCormick envelopes depend on the variables bounds, the relaxation will become tighter.
The second is to rely on piecewise relaxations. You pick a variable for partitioning in each bilinear term (all partitioned variables are dealt with at the same time), select the number of partitions and then solve the MIP relaxation. As the number of partitions tends to infinity, the relaxation gap tends to zero.
Perhaps the most efficient piecewise relaxation is the multiparametric disaggregation, since the number of binary variables scales better with the number of partitions. It should be relatively easy to implement!
You can find more in the papers:
DOI:10.1007/s10898-012-0022-1
DOI:10.1007/s10898-015-0342-z
Best regards,
Pedro Castro
Dear Pedro,
Many thanks for your constructive comment. Since I need this method for online applications, what will be happened for its run time if the number of partitions tends to infinity? What about the the second approach (i.e., multi-parametric disaggregation), how fast is it?
Best,
Morteza
Hi Morteza,
I am a new researcher in this field and I am working on similar problems. I hope you will find following paper useful:
Article Computational Comparison of Piecewise−Linear Relaxations for...
Cheers,
Zaid
- Badges
- Science topic
- Similar topics
- Mathematical Sciences
- Graphs