Originally posted by: chintasunny

Hi
I have an MIP that is modeled in CPLEX (JAVA environment). Typically the objective function coefficients range from 0.001- 10E4. I need to add some penalty terms to the objective function. In a given model multipliers range from 10E5- 10E20 (i.e. I will have some penalty terms having a value of 10E5, some with 10E10 and so on). Typically there may be 5000- 50000 such terms in my objective function. My question is

• Will there be any issues due to numeric precision? (A JAVA double can store values upto 10E300)
• Will the huge variation in penalty terms impact the performance?

Thanks in Advance
Sunil
#DecisionOptimization
#MathematicalProgramming-General

Originally posted by: SystemAdmin

Your problem will not be the range that an IEEE double precision number can represent but the accuracy with which you can perform computations on such a wide range of values. You will get all kinds of numeric trouble with data that ranges from 1e-3 to 1e20.

Concerning CPLEX: CPLEX considers anything larger than 1e20 as infinity. And coefficients ranging from 1e-3 to 1e10 may give CPLEX considerable trouble. Is there any way you can limit your penalty terms to a much smaller range?
#DecisionOptimization
#MathematicalProgramming-General

Originally posted by: SystemAdmin

One cannot say this in advance, but I am pretty sure that these large objective coefficients will cause trouble. Note that for bounds of variables, CPLEX would treat values equal or larger than 1e+20 as infinity. And since objective function coefficients in the primal are right hand side values in the dual, I wouldn't be so sure whether everything works well if you use 1e+20 in the objective...

If this is a hierarchical objective function, I think you would be better off by solving this in consecutive rounds instead of merging everything into a single objective function. What I mean is the following:

Let's assume your first level variables are called x (these are the ones with 1e+20 objective function coefficients), your second level variables are called y (the 1e+10 objectives) and the remaining variables are called z. Then you first solve the model with the objective coefficients set to 1 for x and 0 for all other variables. This will give you the optimal objective value X that you can get from the first level decision. Then you add this as a constraint. If you are minimizing, this would be sum x_i <= X.
Replace the objective function using 1 for all y and 0 for everything else. Solve again to get objective value Y. Finally, add constraints sum y_i <= Y, install the objective function on z, and solve the model again to get the final optimal solution to your hierarchical objective function model.

On the first sight it sounds strange to replace a single optimization with three, but merging three different objectives into a single one can often cause more pain (both in terms of performance and numerical stability) in a single solve than you would have in three individual solves.
Tobias
#DecisionOptimization
#MathematicalProgramming-General

Originally posted by: phl70

Dear Tobias and Daniel,

I am using the method you described above from time to time. One phenomenon that I encounter regularly is that even though X may be the minimum of sum x_i, adding the constraint sum x_i <= X to the problem may render it infeasible according to cplex (at least if the problem is numerically challenged). Is there a standard pattern to deal with this issue (other than reformulating the problem to be numerically more stable)?

Best,
Peter
#DecisionOptimization
#MathematicalProgramming-General

Originally posted by: SystemAdmin

Yes, I can imagine that this may happen due to numerical difficulties in the model and/or the solving process. The easiest and probably most practical solution is to just use X+eps instead of X for the rhs of the constraint, with eps chosen appropriately. In most cases, the hierarchical objective is not completely strict, i.e., you probably would allow for a 0.1% deviation of the first level optimal value.

Tobias
#DecisionOptimization
#MathematicalProgramming-General