Originally posted by: brownflaming1

Hi guys,

I'm calling cplex from c++ to solve some LP. The algorithm solves a large number of LPs, sequentially. At some point, CPLEX reports unboundedness to an LP, however in fact, as soon as it reports the error, I output the problem to an LP file. If I read the .lp file in CPLEX console, it actually has an optimal solution. All variables in the problem are bounded. Anybody knows why? Thanks very much for your help!

When it reports unboundedness, the log looks like follows:

Iteration log . . .
Iteration:     1   Dual objective     =       -210757.947641
Iteration:    14   Scaled dual infeas =             0.000002
Iteration:    16   Dual objective     =       -210725.023620
Iteration:    35   Dual objective     =       -210725.023620
Repairing basis singularity.
Iteration:    87   Scaled dual infeas =             1.500003
Iteration:    88   Scaled dual infeas =             1.500000
Iteration:    89   Scaled dual infeas =             1.500000
Reinitializing dual norms . . .

Iteration log . . .
Iteration:     1   Scaled dual infeas =             1.500010
Markowitz threshold set to 0.99999
Iteration:     6   Scaled dual infeas =             1.499999

Dual simplex solved model.

Solution status: Unbounded

When I solve the .lp file in cplex console, it reports optimality:

Parallel mode: deterministic, using up to 4 threads for concurrent optimization.
Tried aggregator 1 time.
LP Presolve eliminated 1214 rows and 2542 columns.
Reduced LP has 361 rows, 1024 columns, and 13221 nonzeros.
Presolve time = 0.01 sec. (4.38 ticks)
Initializing dual steep norms . . .

Iteration log . . .
Iteration:     1   Dual objective     =      -1126080.000000
Iteration:   105   Dual objective     =       -211442.398591
Markowitz threshold set to 0.1
Iteration:   110   Dual objective     =       -211442.398591
Iteration:   113   Dual objective     =       -211249.773501
Iteration:   115   Dual objective     =       -211220.752818
Removing shift (1).
Iteration:   117   Dual objective     =       -211220.752818
Markowitz threshold set to 0.2
Iteration:   125   Dual objective     =       -210724.886007
Reinitializing dual norms . . .
Reinitializing dual norms . . .

Iteration log . . .
Iteration:     1   Dual objective     =       -211220.752818
Markowitz threshold set to 0.2
Iteration:     9   Dual objective     =       -210724.886007
Iteration:    21   Scaled dual infeas =             0.000000

Dual simplex solved model.

Maximum unscaled bound infeasibility = 651.682.

Dual simplex - Optimal:  Objective = -2.1122075282e+05
Solution time =    0.05 sec.  Iterations = 159 (1)
Deterministic time = 16.94 ticks  (353.35 ticks/sec)

Originally posted by: BoJensen

You should save the model in .sav and not .lp format. SAV format is a binary format, which also stores the current basic solution and doesn't have the drawback of LP format, which can loose numeric accuracy. 

Looking at the log output, your model seems to be numerical unstable (cplex reports basis singular and increases markowitz tolerance). This can of course happen, but you should check your model for tiny and/or huge numbers that may be a source of instability. You can also play with the scaling parameter and maybe set it to aggresive (scale=1) and switch numerical emphasis on (emphasis=numerical). Also setting the markowitz to a high value (say 0.5 -0.9) from the beginning may ensure a more stable basis is maintained. Please post new log from the interactive command with SAV format and if inconsistency persists, then also post the problem if possible.

Originally posted by: EdKlotz

I am particularly concerned about the following output in the iteration log from the run that declared unboundedness:

Maximum unscaled bound infeasibility = 651.682.

That is quite a large unscaled bound infeasibility and suggests the presence of some really large matrix coefficients in the model.   I would look at the variable associated with that unscaled bound infeasibility, then look at the constraints it intersects.

Originally posted by: BoJensen

I should add, that it's possible (but rare) a problem can be declared both optimal and unbounded within the current absolute tolerances. This is often an indication your problem is numerical unstable.

Originally posted by: EdKlotz

You can assess whether the problem is right on the edge of optimality and unboundedness by

1. Checking the solution quality.   From interactive CPLEX, use the 'display solution quality' command.    If you see reduced cost infeasibilities just below the optimality tolerance setting (which defaults to 1e-6), that increases the likelihood that this is the case.
2. Solve the model with a reduced optimality tolerance of 1e-9.   If that yields consistent results of feasibility, that too suggests the model is right on the boundary.

Originally posted by: brownflaming1

Sorry I was caught up with something else so didn't get back to you in time. Thanks very much for your help. I save the file in .sav format and cplex console still can solve that problem to optimality. I did have some auxiliary variables with large penalties in the model, so I think you guys are right, those large coefficients make the model unstable. I think to avoid this problem, I have to come up some other way to construct the model.

Thanks so much for your help.