Originally posted by: konstantin.ermakov

Hallo, everyone.

We are using the ILOG CPLEX version 11.2 library within our product written
in C#, Visual Studio 2008. The problem (formula) we would like to optimize is generated dynamically. As soon as we reach the certain number of variables we receive the error message : Error 1217 No Solution Exists. On a later stage, the solution is found again. We also receive a warning message:

Warning: diagonal perturbation of 2.4e-005 Default row names c1, c2 ... being created.

The file, that produces an error is attached, two other files will be attached in the next messages

Thanks,
Konstantin

---
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: konstantin.ermakov

This is the first working case
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: konstantin.ermakov

This is the second working case
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: konstantin.ermakov

Hello,

I was able to reduce the number of variables. The following case throws an error: no solution exists

\Problem name: ILOG.CPLEX
 
Minimize
 obj: IloX0 + 0 x1 + 0 x2 + [ 4413792617.12304 x1 ^2 + 26017194878.2574 x1 * x2
      - 53812266950.7606 x2 ^2 ] / 2
Bounds
      IloX0 = 24296804629.6239
 0 <= x1 <= 1
 0 <= x2 <= 1
End

#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

Don't you see a message like
CPLEX Error 5002: Q in objective is not positive semi-definite.
The quadratic matrix in your objective function is not positive
semi-definite. CPLEX only supports positive semidefinite matrices there.
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: konstantin.ermakov

No, we do not have this error message. I also tried to reduce the numbers and
the error is still there,

\Problem name: ILOG.CPLEX
 
Minimize
 obj: IloX0 + 0 x1 + 0 x2 + [ 0.181661444144862 x1 ^2 + 1.0708072635418 x1 * x2
      - 2.21478781967691 x2 ^2 ] / 2
Bounds
      IloX0 = 1
 0 <= x1 <= 1
 0 <= x2 <= 1
End

#CPLEXOptimizers
#DecisionOptimization

Originally posted by: konstantin.ermakov

I tried a simple test (all the matrix elements are -1) and we receive the error
message - no solution exists. So, this is definitely the problem that we have.
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: RWunderling

Konstantin,

I tried your simple model in the following interactive session:

ILOG CPLEX 11.000, licensed to "ILOG CPLEX Internal", options: e m b q p=2 MaintenanceEnd=20100901 
 
Welcome to CPLEX Interactive Optimizer 11.0.0
  with Simplex, Mixed Integer & Barrier Optimizers
Copyright (c) ILOG 1997-2007
CPLEX is a registered trademark of ILOG
 
Type 'help' for a list of available commands.
Type 'help' followed by a command name for more
information on commands.
 
CPLEX> enter
Enter name for problem: test
Enter new problem ['end' on a separate line terminates]:
Minimize
 obj: IloX0 + 0 x1 + 0 x2 + [ 0.181661444144862 x1 ^2 + 1.0708072635418 x1 * x2
      - 2.21478781967691 x2 ^2 ] / 2
Bounds
      IloX0 = 1
 0 <= x1 <= 1
 0 <= x2 <= 1
End
CPLEX> opt
Number of nonzeros in lower triangle of Q = 1
Using Approximate Minimum Degree ordering
Total time for automatic ordering = 0.00 sec.
Summary statistics for factor of Q:
  Rows in Factor            = 2
  Integer space required    = 2
  Total non-zeros in factor = 3
  Total FP ops to factor    = 5
CPLEX Error  5002: Q in objective is not positive semi-definite.
Presolve time =    0.03 sec.

As you see I only get error 5002 as expected. Of course, if you now try to access the solution
you will get

CPLEX Error  1217: No solution exists.

but the core problem is that your model is not positive semi-definite.

Roland
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: konstantin.ermakov

Hi,
i do not think, that the matrices provided in the first three cases are non PSD. What we just noticed is the following - If we are loading all the models into the interactive solver, the solution is found. But the call from C# does not work. Hese is the piece of pseudo-code that we have

Cplex cplex = new Cplex()
   ...
   cplex.ExportModel("tmp.lp");
   cplex.Solve()

threw an exception. After the following change

Cplex cplex = new Cplex()
   ...
   cplex.ExportModel("tmp.lp");
   cplex.ImportModel("tmp.lp");
   cplex.Solve()

we receive the solution. Does somebody has an explanation to such a phenomena?
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

Yes, there is an explanation: Exporting to an LP file introduces round-off errors.
In your case it seems that the round-off errors decide between being psd or not :-(
Can you try saving to a .sav file:

Cplex cplex = new Cplex()
...
cplex.ExportModel("tmp.sav");
cplex.ImportModel("tmp.sav");
cplex.Solve()

Does this throw an exception? If so, can you post the .sav file?
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: konstantin.ermakov

Hi,
with the .sav file it does not work. The file is attached.
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

Just to clarify: You read in the .sav file, invoke solve() and don't get a solution?
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: konstantin.ermakov

yes, i read the file, and the solution does not exists.
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

I read in TestData.sav, wrote it out in LP format, solved the .sav version and then read and solved the .lp version. CPLEX 12.1 reports that the objective of the SAV file version is not positive semi-definite; the objective of the LP version looks positive semi-definite, but only after a perturbation:

Warning:  diagonal perturbation of 3.2e-04 required to create PSD Q.

So I suspect that the objective is not PSD, either by design or as a result of poor scaling (CPLEX reports that the non-zero quadratic coefficients range from 0.05445 to 6.6e+10). The LP version probably looks (approximately) PSD as a result of a loss of precision passing the problem through a text file, as I believe was suggested earlier in the thread.

12 orders of magnitude difference in the objective coefficients of a QP seems rather risky w.r.t. rounding/truncation errors.

/Paul

Mathematicians are like Frenchmen: whenever you say something to them, they translate it into their own language, and at once it is something entirely different. (Goethe)
#CPLEXOptimizers
#DecisionOptimization