Originally posted by: SystemAdmin
[jgregory said:]
Hello Yajaira,
The lack of replies so far is not due to any deficiencies in your writing, but because you have tackled a hard (but interesting) problem and there are several potential pitfalls that might all be interacting. I suspect you will find this reply both overwhelming and insufficient. :) Quite a lot of work may be necessary to understand what is going on with your problem. I am writing somewhat in the hope and expectation that you are working on academic research and can devote the time and effort necessary.
First, since you are seeing different algorithmic results when running a given model in the Interactive Optimizer versus within your Callable Library environment, I ask whether you exporting the model using CPLEX's binary SAV format, or in the (ASCII) readable MPS or LP format? The latter are more convenient because you can look at them yourself, but they suffer the disadvantage that they are not an exact representation of the problem CPLEX was seeing inside your program. SAV format will be that exact image. Two ways that these formats can differ are 1) floating point values may not be exactly representable in decimal ASCII format, and 2) the order of variables and constraints may become different when the ASCII formats are read back in. (The good news is that, given a SAV file, you can still obtain MPS or LP versions to look at by reading and then writing using the Interactive Optimizer.)
In principle, you might expect the order of rows and columns should not matter, in determining the optimal solution. However, many models allow multiple optimal solutions. It is an unfortunate fact of life that the algorithms used for solving linear programs and extensions like MIP will take different paths based on how ties are broken during various computations, or in extreme cases ordering can even affect the results (computing a+b-a versus a-a+b if the value of 'a' is large can lead to a loss of significant digits for 'b' on finite precision computers).
For similar reasons, when a model possesses multiple optimal solutions, two different versions of CPLEX may reach two different answers, both optimal but perhaps quite different qualitatively.
Apart from having multiple optima, some models are numerically ill-conditioned - these would be characterized by very large changes in the solution values (including potentially the objective function) given only very small changes in input data. Again because of finite precision on computers, such models may likewise vary in the optimal solutions CPLEX will deliver, if re-run under virtually any perturbation (reordered rows and columns, different CPLEX versions, different computer hardware or operating system).
From your description, I am taking a guess that your master problem typically possesses multiple optima, and the subproblems may have both multiple optima and ill-conditioning. The choice of "epsilons" in particular seems a likely area for introducing numerical instability without realizing it. CPLEX operates using various tolerance values - in the Interactive Optimizer you may get an idea about some of these by looking at the choices under "set simplex tolerances" - in particular, the default values of the feasibility and optimality tolerances of 1e-6, might be interacting harmfully with the epsilons you are choosing. This could lead to otherwise-feasible solutions to be rejected, or even for infeasible solutions to be accepted - or conceivably if your choice of epsilon is very small it may in effect be nearly ignored. It is probably better to choose your epsilon in light of CPLEX's default tolerances, rather than to change CPLEX's tolerances to somehow try to "manage" your epsilons. You could try an epsilon in your model as large as 0.01 (if I'm understanding generally how these epsilons are being used in your decomposition) and see whether you get more robust behavior than with epsilons closer to zero. If this tactic helps, then you may have some difficult choices to balance the need for tight epsilons versus getting reliable results.
One tool to try, very conveniently in the Interactive Optimizer, is the solution quality report. When you have a solution, type "display solution quality". For a Mixed Integer problem, you will get a different group of quality measures than for a continuous model. For Mixed Integer, the entries involving "error" should be small, say 1e-6 or smaller, or else it's an indication of some trouble. For continuous models, the items marked infeasibility and residuals would be the place to look, for similar values; and it also shows the "Condition number" (sometimes called Kappa) of the basis, which is a very useful indication of the numerical issue I raised above - a value of up to 1e+08 for Kappa is usually pretty safe, but values creeping up above that can be a symptom of real trouble. The orders of magnitude for Kappa roughly correspond to the number of decimal digits of significance, and double precision (which is what CPLEX uses) has only about 16 digits so a really large Kappa can mean that accuracy of the computations is questionable. On a Mixed Integer model, which is solved by considering many many continuous submodels, you can get an idea of a typical Kappa value either by relaxing the problem to LP ("change problem lp") and solving it and then viewing the solution quality display, or by treating the integer solution as an LP by changing the problem type ("change problem fixed") and solving it and viewing the solution quality. You might try experimenting with different sizes of your "epsilon" to see whether it is having an effect on Kappa.
There is a section in the CPLEX User's Manual, in the LP section, titled "Interpreting solution quality", that might give you further insights on the solution quality report. But I'm afraid there are few absolute recommendations anyone can make, and if your decomposition framework is suffering from numerical instability then a good deal of experimentation, and art, will be necessary.
#DecisionOptimization#MathematicalProgramming-General