Originally posted by: PetBe

Hi all,

I have experienced a very strange problem. When solving a certain optimization problem the gap becomes negative. How can this be possible? I thought that the MIP gap quantifies the difference between the theoretical best solution of a relaxed linear problem and the feasible integer solution? Ihave attached a log of the solver information from CPLEX when using GAMS for the modelling. Would be happy, if someone could explain why this is happening and what it basically means?

Originally posted by: Rafael Colares

Hi,

It is indeed strange... Theoretically, integrality gap should always be positive... Try updating your tolerances. Maybe it is due to numerical instability...

Originally posted by: PetBe

Thanks Rafael for your answer,

I changed the tolerances, but it did not help. I still get negative MIP gaps. What is special about my model is that it is a two objectice optimization problem that uses the weighted sum approach to make the objetice funciton 1-dimensional (and normalize the two objectices by the optimal value of their single-objectice problem). Maybe this causes this strange behaviour by CPLEX?

What is also really strinking, is that even after CPLEX has found solutions that have a negative MIP gap, is sometimes proceeds searching for furher solutions with even lover MIP gap ("higher" neative value) altough the tolerance is set to 0.01%. This is extremely strange. You can see this behaviour in the newly attached log file "CPLEX_LOG_2.txt".

Is there a way how I can tell CPLEX to neglect the solutions with negative MIP gap?

Originally posted by: Rafael Colares

Can you try to execute your model (the same instance as in your previous log) without integrality constraints (i.e., all variables being real numbers) and share the log?

Originally posted by: PetBe

Thanks Rafael for your quick answer,

how can I exectute the model without integrality constraints? Of course I could change the GAMS code but this would require quite too much time. Can I do this faster?

I would suggest having GAMS export the model to a SAV file if possible, LP file if SAV is not possible, and then running it in the interactive optimizer. That tends to be easier for debugging purposes. I think you can relax integrality using the "change problem type" command in the interactive optimizer. You might also want to ask CPLEX to generate kappa statistics. That will help determine whether there are numerical stability problems that might result in anomalous results.

From everything that was said here, I guess that the issue is numerics and the log shows things that are not correct due to round-off error etc.

If you look at your first log then you can see that the best integer solution found is 1.0305 and that solution is later confirmed to be feasible by GAMS:

Solution satisfies tolerances.

MIP Solution:            1.030493    (11357 iterations, 13 nodes)

On the other hand, the dual bound reported by CPLEX is 1.0334 which would cut off the above solution:

Root relaxation solution time = 0.34 sec. (334.97 ticks)

        Nodes                                         Cuts/
   Node  Left     Objective  IInf  Best Integer    Best Bound    ItCnt     Gap

      0     0        1.0334   125                      1.0334    10189

So it looks that the dual bound displayed in the log is off. On the other hand, the dual bound used by CPLEX internally seems correct, as your second log shows: even though there is a solution that would be cut off, CPLEX keeps going and does not stop immediately. The reason why there may be two different dual bound informations is that internally CPLEX works with the presolved model while in the log data is shown with respect to the original model. Usually these values are exactly the same but depending on numerics they can differ.

In addition to tightening tolerances, I suggest to enable the CPX_PARAM_NUMERICALEMPHASIS parameter.

A likely culprit of this is the blended multi-objective. Are you mixing big and small terms there? Recent versions of CPLEX directly support multi-objective. Would it be an option to use that new feature and solve for the two objectives lexicographically?

Originally posted by: EdKlotz

Theoretically, the MIP gap can of course never be negative.   However, given the finite precision computing environment in which CPLEX operates, in practice it can occur, and the recommendations of Paul and Daniel try to address that.   In addition to their recommendations (check the kappastats, turn on numerical emphasis), I would suggest the following tests, which should be done on an exported SAV file with interactive CPLEX so we can take anything GAMS does out of the picture.

1)  Check the solution quality of the MIP solution with negative MIP gap (e.g. 'display solution quality' after solving the MIP in interactive CPLEX).  If there are significant violations, that could explain the issue.

2)  Run with the datacheck parameter set to 2, which will turn on CPLEX's modeling assistance feature, and perhaps point you to the particular aspect of the model that has numerical issues.

3)  Run with default settings and see if the negative MIP gap persists.   If not, start systematically adding your non default parameter settings until you see which one causes the negative MIP gap to occur.

4)   Do a run with presolve turned off.   Fundamentally, CPLEX's node log out translates information from the presolved model back to your original model.   If something went wrong with this, that could explain it.  

5) Add a constraint to the original MIP that the objective must be <= the 1.0305    solution objective value that resulted in the negative MIP gap.   Is the resulting model infeasible?   If so, run the conflict refiner to get an explanation of the infeasibility, which may shed light on what is happening.

Originally posted by: PetBe

Thanks a lot PaulRubin, DanileJunglas and EdKlotz for your answers and sorry for the late reply (I was on a business trip),

As DanielJunglas suggested I enabled CPX_PARAM_NUMERICALEMPHASIS  and as EdKlotz suggested I enabled datacheck parameter. However, I still sometimes get negative MIP gap values. Like I said before, I am using a multiobjective optimization, which is converted to a one-dimensional problem by applying the weighted sum approach. The objetice function looks like this:

min weight_1 * (objective_1/objective_1_normalization ) + weight_2 * (objective_2/objective_2_normalization )

So I first solve the respective opimization problems for both of the two objectives. In the first run I set weight_2 to 0 and weight_1 to 1 and use the optimal value as the normalization value for the first objective (objective_1_normalization ). Then I set weight_2 to 1 and weight_1 to 0 to get the normalization value for the second objective (objective_1_normalization ). Now I run the optimization problem 3 futher times with the weight combinaiton (Run 3: weight_1 = 0.25, weight_2 = 0.75), (Run 4: weight_1 = 0.5, weight_2 = 0.5),  (Run 5: weight_1 = 0.75, weight_2 = 0.25).

Due to these nummerical instability problems I sometimes get really weird results such as a increasing weight for one objetivce leads to worse results for that objective. I would really like to eliminate such kind of results. I have attached the Cplex log file from GAMS for the Run3 (weight_1 = 0.25, weight_2 = 0.75). Maybe you can infer something out of it.

Thanks for your help and effort. I really appreaciate it.

You can see a lot of warnings from the modeling assistance tool in the output:

CPLEX Warning  1044: Detected objective coefficient <= the value of CPX_PARAM_EPOPT at variable 'z'.
CPLEX Warning  1045: Detected nonzero <= the maximum value of either CPX_PARAM_EPRHS or CPX_PARAM_EPOPT at constraint 'eq_mHP_EV_energyLevelOfTheEV_kWh(1.Household__mHP_EV1)', variable 'energyLevelOfTheEV(1.Household__mHP_EV1)'.

These two basically guarantee (random) numerical issues: The numbers in your model are smaller than the tolerances. So these coefficients will give random noise.

Then you also have

CPLEX Warning  1048: Detected constraint with wide range of coefficients. In constraint 'eq_SOC(2.Household__mHP_EV1)' the ratio of largest and smallest (in absolute value) coefficients is 1.3644e+08.

This is also a frequent source for numerical trouble. There are more warnings. They don't seem as bad as the ones above but are still worth looking at.

Can you fix at least the warnings above? In particular the ones about numbers smaller than tolerances.

Originally posted by: PetBe

Thanks DanielJunglas for your answer,

unfortunately I have no clue how I can fix these three warnings. Here my comments:

CPLEX Warning  1044: Detected objective coefficient <= the value of CPX_PARAM_EPOPT at variable 'z'

--> Variable z is basically one of the two objectives. I do not understand why the numbers in my model are smaller than the tolerances. In fact I am sure that they are not with regard to the variable z. In the model run that is related to the previously posted log, the variable z has a value of 2956351.125041.

CPLEX Warning  1045: Detected nonzero <= the maximum value of either CPX_PARAM_EPRHS or CPX_PARAM_EPOPT at constraint 'eq_mHP_EV_energyLevelOfTheEV_kWh(1.Household__mHP_EV1)', variable 'energyLevelOfTheEV(1.Household__mHP_EV1)'.

--> I do not understand this warning. I have two variables. The variable energyLevelOfTheEV quantifies the energy content of an electric vehicle in the unit Joule [J], whereas the equation eq_mHP_EV_energyLevelOfTheEV_kWh is used to transform this energy unit into kilowatt hours [kWh] by defining the respective variable in kWh. The Joule value has to be divided by 3600000, and this is what is done by this equation. For the first timeslot (1.Household__mHP_EV1)I fix these values and read their initial values from a file. Again, as far as I understand, the numbers here are quite high (68220000 J and 18.95 kWh) and it is hard to imagine that they are smaller than nummerical tolerances.

The warnings are not about the values of the variables but about their coefficients. If the Joule value must be divided by 3600000 then maybe you have a coefficient of 1/3600000 for the respective variable?

Originally posted by: PetBe

Thanks DanielJunglas for your answer,

in fact - as mentioned above - I divided the value by 3600000. But there is no other way of doing this and anyways the variable which measure in kWh does not influence the objective function at all. I only use it to display the results. And for the z variable I use 0.001 as a coefficient. This can also not be changed as I penalize the use of certain actions with this. A higher value would lead to strongly biased results (even this value might be too high).

My generall question is: Is there a way to tell Cplex to neglect the found solutions with negative MIP gaps and proceed searching for solutions that satisfy the optimality constraints with positive MIP gaps?

No, sorry, there is no way to do that since technically a negative MIP gap should not happen.

And I don't think it as simple as that: In your particular case it seems that the solutions with negative MIP gap are feasible (at least that is what GAMS reports). So it seems you want to collect them. The negative MIP gap may be due to numerical issues when computing the Best Bound. So the best bound may look better than it actually is. And in that case you certainly want to keep the solutions with negative gap (they are better than the fake best bound but still feasible).

Note that it is in general hard to tell whether bad coefficients have an impact on the objective function or not. CPLEX may perform all sorts of aggregations, may zap tiny numbers to zero, etc. All this may influence the actual values of variables and thus the actual value computed for the objective function.

Originally posted by: PetBe

Thanks DanielJunglas for your answer and help,

I simply mutliplied the objective function by 100, as so far I have not encoutered negative MIP gaps in my model runs. As far as I remember they told us in lectures about optimization that multiplying the objective function by a constant coefficient does not change the optimal solution, as this will only scale the objective function. In my case, it changes the whole optimization procedure, as the runtime strongly increases by this but the results become better and (so far) I have not got negative MIP gaps.