I have a model with quadratic objective function and linear constraints. I am using CPLEX to solve a minimization problem. I have set the gap value %0.0 and I have noticed that the model loses a lot o time around very low gap values and I have noted the objective function value at low gap values. When I set the gap those low values, I have obtained an objective function value which is much more higher than the one I have noted, and this value cannot be true according to the gap.

What can be the reason? Is there any setting for quadratic programming which I might have missed? Thank you in advance.

asked 17 Apr '15, 16:14

yasemin's gravatar image

yasemin
1113
accept rate: 0%

1

Is this a continuous QP or a mixed integer QP? Assuming it's mixed integer, it might help if you showed the last several lines of the node log.

(17 Apr '15, 19:53) Paul Rubin ♦♦

It is a mixed integer QP. Here are some lines and last lines of the node log at gap %0.0:

      Nodes                                         Cuts/
Node  Left     Objective  IInf  Best Integer    Best Bound    ItCnt     Gap
7130   450        cutoff          72249.0000    72240.2000   103954    0.01%
*  8930+  469                        72247.0000    72240.2000   133305    0.01%
*  9527+  458                        72243.0000    72240.2000   141544    0.00%

2685010 21898    72241.0000    10    72243.0000    72241.0000 36477426    0.00%
2793907 19769    72241.0000     9    72243.0000    72241.0000 37725151    0.00%
2905181 10260    72242.0000    18    72243.0000    72242.0000 38864248    0.00%

Last lines when the gap is 0.01%:

    Nodes                                         Cuts/ 
Node  Left     Objective  IInf  Best Integer    Best Bound    ItCnt     Gap
521813 13800        cutoff          81683.0000    81664.2000  4607042   0.02%
542708 12295        cutoff          81683.0000    81664.4531  4803536    0.02%
563565  6666        cutoff          81683.0000    81666.3333  4966647    0.02%

I know the optimal objective function value is 72243, but the model with gap updates best bound in a way that I couldn't understand and finds incorrectly high z*.

(18 Apr '15, 04:02) yasemin

This sort of radical change in results is often a sign of numerical instability in the model. I don't know why changing only the gap parameter would trigger the instability, but I suppose it is possible.

Two things you can try:

  • set the numerical emphasis parameter (Java name Emphasis.Numerical) to 1, which tells CPLEX to be extra careful with numerical precision (but can cause performance to degrade); or
  • collect basis condition number statistics by setting the parameter MIP.Strategy.KappaStats to 1 or 2 (2 will degrade performance more than 1 will).

If turning on the numerical emphasis switch (combined with setting the gap limit) eliminates the inflated solution and lower bound, chances are high that your model is numerically unstable. If you collect kappa statistics and they reveal the presence of unstable basis matrices, that would be a clear signal of numerical problems.

At least in the latest version of CPLEX, turning on the numerical emphasis parameter automatically sets the KappaStats parameter to 1 (collect a sample of condition numbers).

link

answered 18 Apr '15, 09:52

Paul%20Rubin's gravatar image

Paul Rubin ♦♦
14.6k412
accept rate: 19%

Thank you very much for your response. Setting the numerical emphasis parameter to 1 solved the problem.

As you have said, this kind of effect of gap is really unexpected, and so, I cannot be sure about the correctness of my solutions. I am going to use the model with a reasonable gap value and collect the solutions of several runs. Because of long solution times, it is not possible to set gap value to 0%. So, should I always set numerical emphasis parameter to 1 disregarding worse performances? (I was already using EpInt and EpRhs parameters at low values. I have read your comments about numerical instabilities and possible actions to be taken on your blog. If I understand correctly, numerical instabilities may be solved by changing some parameters, but they may not be solved at the end. Is it true?)

(19 Apr '15, 16:18) yasemin

Numerical difficulties can be mitigated to some extent by changing the numerical emphasis parameter (the other parameter I mentioned just captures statistics; it does not fix anything). The only true solution to instability is to modify the model.

One common source of instability (though not the only one) is a mix of large and small coefficients in the constraint matrix. What are the largest and smallest coefficients (in absolute value) in your model?

(19 Apr '15, 16:27) Paul Rubin ♦♦

It is a routing problem and the coefficients are 1's and costs between 1 and 20. They are not different from each other, the model is quite sparse.

(19 Apr '15, 16:52) yasemin

So no "big M" constraints, eh? That's probably the most common source of instability and also perhaps the easiest to fix. You might want to look in the "Tutorial" section of https://www.ibm.com/developerworks/community/wikis/home?lang=en#!/wiki/W1a790e980a7d_49c5_963d_2965e5d01401/page/INFORMS%202014%20Annual%20Meeting (sorry for the long URL, not my doing). The slides for a talk by Ed Klotz on numerical instability might be helpful.

(19 Apr '15, 17:07) Paul Rubin ♦♦

"So, should I always set numerical emphasis parameter to 1 disregarding worse performances?" For this model, yes, unless you can identify and fix the source of the instability. In general (meaning for other models), no. The usual practice is to leave it off unless something suspicious appears in the output.

"I cannot be sure about the correctness of my solutions." Again, for this particular model, it might be a good idea to have your program verify that the CPLEX solution is feasible (to within tolerances) and that the objective value is what CPLEX says it is (to within rounding error).

(19 Apr '15, 17:11) Paul Rubin ♦♦

I don't have any bigM constraints, the model forces to use a given number of routes. I think much lower values of feasibility tolerances seem to solve the problem, and I may continue to live without numerical emphasis parameter adjustment. Thank you very much for the materials and your comments.

(19 Apr '15, 17:19) yasemin
showing 5 of 6 show 1 more comments
Your answer
toggle preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "Title")
  • image?![alt text](/path/img.jpg "Title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported

Tags:

×191
×5
×3
×1

Asked: 17 Apr '15, 16:14

Seen: 1,274 times

Last updated: 19 Apr '15, 17:19

OR-Exchange! Your site for questions, answers, and announcements about operations research.