Originally posted by: RafaelMartinelli

Hi,

I am working on a column generation on a LP problem and I sometimes receive the following warning on stderr:

---
Markowitz threshold set to 0.1
---

I don't know what is this warning, but it just take a little bit more time to start to solve the LP and it's not a problem for me. But, when I start to give new LBs and UBs for the columns (sometimes fixing them), I receive the following error and the program gives a runtime error:

---
Markowitz threshold set to 0.1
Repairing basis singularity.
Markowitz threshold set to 0.2
Repairing basis singularity.
Markowitz threshold set to 0.3
Repairing basis singularity.
Variable 'id23398' fixed because of singularity.
Markowitz threshold set to 0.4
Repairing basis singularity.
Variable 'id45324' fixed because of singularity.
Markowitz threshold set to 0.5
Repairing basis singularity.
Variable 'id971' fixed because of singularity.
Markowitz threshold set to 0.6
Repairing basis singularity.
Variable 'id17331' fixed because of singularity.
Markowitz threshold set to 0.7
Repairing basis singularity.
Variable 'id5275' fixed because of singularity.
Markowitz threshold set to 0.8
Repairing basis singularity.
Variable 'id16247' fixed because of singularity.
Markowitz threshold set to 0.9
Repairing basis singularity.
Variable 'id44041' fixed because of singularity.
Variable 'id38002' fixed because of singularity.
Markowitz threshold set to 0.99999
Repairing basis singularity.
Variable 'id27486' fixed because of singularity.
---

Does anyone know what's the problem?

Rafael Martinelli
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

You are experiencing numerical issues here. The Markowitz tolerance gives you a trade-off between sparsity and numerical accuracy in the factorization of the basis matrix inside the simplex algorithm. If CPLEX discovers numerical issues, then it will automatically crank up the tolerance to aim for better numerical accuracy in the linear system solves. But even this is not enough in your case, as you can see by the "Repairing basis singularity" messages.

You need to first assess where the numerical problems come from in your model. Then, you should try to find a better way of modeling your problem that has better numerical properties.
The first step to assess the numerical issues would be to write out the model to a *.sav file. In the C API, this is done by CPXwriteprob(), in the object oriented APIs there should be some method that is called exportModel() or something like this.

Having the *.sav file, you can then use the interactive CPLEX to analyze it in a convenient way. First, read it in, and then display the statistics of your model:

read yourmodel.sav
display problem statistics

Post the output of this command to this thread in the forum. Then we can discuss additional steps.
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: RafaelMartinelli

Hello Tobias,

I've done it, but it says:

---
CPLEX> read output.sav
Warning: File contains basis. Basis is loaded.
Problem 'output.sav' read.
Read time = 0.06 sec.
CPLEX> display problem statistics
Option 'statistics' does not exist.
---

Rafael Martinelli
PS.: How do I put these outputs in "code style"?
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: John Cui

It should be

dis problem stats

If you put your code in \{code\} and \{code\} block,
then your code will be displayed in code style.
John Cui
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: RafaelMartinelli

So, the output is:

Problem name: output.sav
Variables            :   18199  [Nneg: 18198,  Fix: 1]
Objective nonzeros   :   18199
Linear constraints   :     288  [Less: 95,  Greater: 105,  Equal: 88]
  Nonzeros           : 1477204
  RHS nonzeros       :     285
 
Variables            : Min LB: 0.0000000        Max UB: 0.0000000
Objective nonzeros   : Min   : 1.000000         Max   : 1447.000
Linear constraints   :
  Nonzeros           : Min   : 1.000000         Max   : 13.00000
  RHS nonzeros       : Min   : 1.000000         Max   : 1.000000e+020

So, I am trying to undestand this. Does "Max UB: 0.0" means that every variable must be zero?

The RHS nonzeros have 1e20 as max values because I have some bounds constraints like: 0 <= SUM(X) <= IloInfinity. I run the LP several times changing these bounds. It's like a B&B, but the braching variable is not explicit, it's a sum of serveral variables.

Rafael Martinelli
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: RafaelMartinelli

After getting this information above, I optimize the problem using just "optimize" on the interactive optimizer (which I use almost never) and cplex solved it using barrier optimizer without resulting in any problem. It was interesting, because my algorithm uses primal all the time.

Now I changed my algorithm to IloCplex::AutoAlg and I am running everything again. It runs the LP several hundreds of times, so it will take some hours.

But even if it works, I would still like further comments about the output above.

Rafael Martinelli
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

> RafaelMartinelli wrote:
>
> So, I am trying to undestand this. Does "Max UB: 0.0" means that every variable must be zero?

No, it means that the smallest lower bound of any variable with a finite lower bound was 0, as was the largest upper bound of any variable with a finite upper bound. So, assuming all your variables were nonnegative, you had one variable fixed at 0 and the rest had upper bound +infinity.

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

Originally posted by: SystemAdmin

I am not sure whether CPLEX will really discard the right hand side value 1e+20. The CPX_INFBOUND = 1e+20 is really just for bounds. The better way would be to change the sense of the constraint to be a "G" constraint instead of an "R" constraint.

In your case, though, I think what you should do is to add explicit slack variables like this:

sum(x) - s = 0
0 <= s <= ub

Now, ub is really an upper bound of a variable and you can set it to CPX_INFBOUND to declare that it is unbounded in this direction. When you want to update the bounds, just use the CPXchgbds() method. Afterwards, you should use the dual simplex algorithm to reoptimize since this is usually the fastest as changing bounds does not destroy dual feasibility of your previously optimal LP solution. If you just call CPXlpopt() then this will also call the dual simplex in your situation.
Tobias
#CPLEXOptimizers
#DecisionOptimization