Originally posted by: Perth2

This has some relation to this previous post.

In a column generation setting for a maximisation problem using CPLEX with Java, I have generated two new columns with a relatively small, but nevertheless positive reduced cost (both 21). These two columns are added to my restricted master problem (RMP). 

If I solve the RMP in Java, neither of the two columns enter the basis. This is checked by calling

IloNumVar[] numVarArray = lpMatrix.getNumVars();
BasisStatus[] basisStatusArray = cplex.getBasisStatuses(numVarArray);

and running though the arrays to find the last two column variables. Both have BasisStatus AtLower.

I get the same result (new variables not in the basis) if I dump the model from Java into a .lp file, and its parameters to an .prm file, read both into the interactive optimiser and solve it. 

I am pretty sure my pricing algorithm is correct, because I keep comparing the reduced cost I am calculating in the subproblem to generate columns with the one CPLEX calculates upon solve. The values for reduced cost are always identical.

1. Shouldn't at least one of the new columns enter the basis (with zero or non-zero value)?

If I query the values for reduced cost calculated by CPLEX, I get:

Variable Name                                                              Reduced Cost

trajectory845_SA1058_SimpleShortestPath         -28209.981799

trajectory846_SA1113_SimpleShortestPath          -1549.699747

2. Does this make sense at all? Or is there a bug in the pricing? Or a numerical issue with the initial reduced cost of 21? 

If I save the model to an .sav file, and its parameters to a .prm file, read it into the interactive optimiser and solve it, both new variables actually do enter into the basis.

3. What could be the explanation for this difference in behaviour between Java/.lp files and .sav files? A numerical issue?

Different results using .sav and .lp files is likely the result of the rounding/truncation errors incurred by converting between binary internal representation to character encoding twice, once creating the .lp file and then again reading it. That can point to numerical instability in the model. It's also possible (I think) that export/import changes the order of the rows or columns in some way that alters the solution process.

Different results using a .sav file produced from the Java code v. the Java code itself makes me think you could have a numerical stability issue. One thing to do is look at the solution quality statistics, particularly the basis matrix kappa value (condition number). A common cause for instability (but not the only cause) is a wide spread of coefficient magnitudes (as, for instance, when the infamous "big M" gets too big).

Originally posted by: Perth2

Thanks, Paul. I understand the issues of conversion from and to .lp files, but the strange thing here is that Java shows the same behaviour as the .lp file (with possible rounding errors). I would expect the .lp file to be the one that behaves differently, and Java and the .sav file to behave the same.

CPLEX> display solution quality
There are no bound infeasibilities.
Max. unscaled (scaled) reduced-cost infeas. = 1.94049e-11 (1.94049e-11)
Max. unscaled (scaled) Ax-b resid.          = 1.3934e-13 (2.17719e-15)
Max. unscaled (scaled) c-B'pi resid.        = 3.61453e-11 (3.61453e-11)
Max. unscaled (scaled) |x|                  = 6.05436e+06 (6.05436e+06)
Max. unscaled (scaled) |slack|              = 570 (512)
Max. unscaled (scaled) |pi|                 = 120925 (120925)
Max. unscaled (scaled) |red-cost|           = 120925 (120925)
Condition number of scaled basis            = 2.9e+02

4. Looking at the solution quality, does it look like I have a numerical problem?

I have added code to keep track of the incoming and outgoing basis variables in each iteration of my column generation:

Iteration 75:

Incoming: [trajectory844, trajectory843]

Outgoing: [trajectory739, trajectory821]

Iteration 76:
Incoming: [trajectory739, covered_1, covered_2]
Outgoing: [trajectory830]

The peculiar thing is, that none of the columns generated in iteration 76 (trajectory844... and trajectory845) enter the basis in iteration 76, even though they both have a positive reduced cost of 21. Another peculiar thing is, that instead of this happening, trajectory739, which was pushed out of the basis in iteration 75, now re-enters the basis. I would at least expect that there would be no change in the solution, since I am only adding columns, not changing the model in any other way. There is no change in objective value. The incoming variables in both iterations enter the basis with value 0. 

5. Should I just accept that it is apparently not the case that at least one of the newly generated columns should enter the basis (and not take it as a sign of a bug in my model og code)?

I too would expect .lp to be the odd man out ... but I've learned to expect ambushes whenever I work on MIPs, and I suppose the same can happen with LPs and column generation.

Your solution quality numbers look fine -- no indication of a numerical problem. I don't know whether your (absolute) reduced costs being on the order of 10^5 and the computed reduced costs for your new columns being 21 would create a sufficient rounding problem to keep them out of the basis, but I doubt it.

I assume that "iteration" means one round of column generation and not one pivot (CPLEX's use of the term). So are you saying that at iteration 76 three variables entered the basis and only one exited? That makes no sense (unless you are choosing not to report slacks that enter/exit the basis).

Originally posted by: Perth2

Thanks, Paul. Yes, iteration means one round of finding new columns. Yes, you are right about that the number of incoming variables should equal the number of outgoing. This is how I calculate the number of variables:

IloNumVar[] numVarArray = lpMatrix.getNumVars();
BasisStatus[] basisStatusArray = cplex.getBasisStatuses(numVarArray);
for (int numVarIndex = 0; numVarIndex < numVarArray.length; numVarIndex++) {
                IloNumVar numVar = numVarArray[numVarIndex];
                BasisStatus basisStatus = basisStatusArray[numVarIndex];
                if (basisStatus == BasisStatus.Basic) {
                    currentBasisNumVarSet.add(numVar);
                }

}
Set<IloNumVar> incomingVariablesInBasis = new HashSet<IloNumVar>(currentBasisNumVarSet);
incomingVariablesInBasis.removeAll(previousBasisNumVarSet);
Set<IloNumVar> outgoingVariablesInBasis = new HashSet<IloNumVar>(previousBasisNumVarSet);
outgoingVariablesInBasis.removeAll(currentBasisNumVarSet);

I am keeping track of the current basic variables in a set. When the iteration terminates this set then becomes the previous set. I am calculating the incoming variables by taking all the ones I have in the current set and subtracting the ones from the previous set. I am calculating the outgoing by taking the variables in the previous set and subtracting all the ones in the current one.

Could the fact that this does not account for CPLEX internal slack variables be the cause for #incoming != #outgoing?

Yes, the count difference is a result of only tracking "decision" variables and not slacks (which is fine). FYI, you can invoke getBasisStatuses on a constraint array, which I think returns the basis statuses of their slack variables.

The fact that trajectory739 returned to the basis at iteration 76 is not necessarily bothersome. When you add variables and reoptimize, the dual solution changes, which means reduced costs change.

When you add a column to the master problem, is the new variable either unbounded (lower bound -infinity, upper bound +infinity) or nonnegative (lower bound 0, upper bound +infinity)? The reason I ask is that if you add new variables with finite upper bounds and they jump straight to that upper bound, they will not appear in your list of basic variables.

Originally posted by: Perth2

Thanks, Paul. Yes, I had the problem you are mentioning earlier, but now I do not have any implicit bounds thereby not accounted for in the pricing.

When you add variables and reoptimize, the dual solution changes, which means reduced costs change.

Yes, and it seems that the algorithm actually continues.

There is just one thing that I still don't get: How can you have variables with positive reduced cost added to the model, and then none of them enter the basis? If the primal basis does not change, how can the dual variables change?

Brace yourself for a long-winded reply. Let's start with a simple case: you add a single new column (with favorable reduced cost and no finite upper bound) at what turns out to be a non-degenerate vertex. The new variable enters the basis (thanks to its reduced cost) at a strictly positive value, which improves the objective value. Once pivoting ends, the new variable must still be in the basis, because if not your basic solution would be using all "old" variables, and the objective value is strictly better than anything you were able to get with the old variables. This supports your expectation.

Now suppose the starting vertex is degenerate. The new variable enters the basis (again due to its reduced cost), but possibly with value 0 (due to degeneracy). Thus the first pivot does not change the objective value. Now assume that at least a few more pivots occur, all without leaving the degenerate vertex. Besides cycling through multiple representations of the same primal solution, you're cycling through multiple optimal solutions to the dual, and I think it's possible that at some point you bang into a dual solution that makes some other variable look good and makes the new variable look bad, leading to its expulsion from the basis.

I don't know offhand a way to generate columns that are guaranteed to stick in the basis even at degenerate corners. Options that I do know are (1) forge ahead and live with the "wasted" column generation cycles (although your uncooperative variable could enter the basis later, after some more columns are generated) and (2) randomly perturb the master problem right-hand sides (to break up the degeneracy) and later, at some point, put the original RHS back and see what you've got.

Originally posted by: Perth2

Thanks for your reply, Paul.

(...) you add a single new column (with favorable reduced cost and no finite upper bound)

I presume you say no finite upper bound in the context that the duals from the finite upper bound have been dealt with when calculating the reduced cost? Because I actually have a finite upper bound of 1 on my new columns.

Also, could this my other post seem to be an explanation? I seems CPLEX is starting the solve process for the RMP all over after a new column has been added rather than from the previous and thus existing basis.

If your new columns have upper bound 1, you should check for status = at upper bound as well as status = basic. I suspect your new variable enters the basis, increases to its upper bound, and then drops out of the basis because it is nonbasic with value 1 ... which is consistent with the favorable initial reduced cost.

Originally posted by: Perth2

Thanks, Paul. My columns have an upper bound in the logic sense, enforced by an explicit constraint. Thus, no variables have status AtUpper.

Could these issues in my other post be an explanation? That way I am hitting a completely different solution.

Originally posted by: Perth2

The issues in my other post are not the explanation. I will try and set the log level to every iteration of the simplex algorithm and post my findings.

Originally posted by: Perth2

I now perform cplex.setParam(IloCplex.IntParam.SimDisplay, 2) to log incoming and outgoing variables in each of the simplex iterations in CPLEX to the console. The following is the log for the case where my newly generated column trajectory457_SA1018_Si with a positive reduced cost seemingly did not enter the basis. As may be seen, the column actually does enter the basis in iteration 1, but then, in iteration 4 it is pushed out. The net result of this is that the new column is not in the basis at the end of the simplex iterations, which is what I observed originally (not knowing that it had been in the basis, but was pushed out). 

Parallel mode: deterministic, using up to 3 threads for concurrent optimization.
Using devex.
Iteration           Objective            In Variable           Out Variable
     1         2817299.606861trajectory457_SA1018_Sitrajectory441_SA1018_Si
     2         2817299.606861coveredTightening slacktrajectory432_SA1018_Si
     3         2817299.606861coveredTightening slacktrajectory429_SA1018_Si
     4         2817299.606861trajectory396_SA1018_Sitrajectory457_SA1018_Si
     5         2817299.606861trajectory287_SE1011_Sitrajectory371_SE1011_Si
     6         2817299.606861coveredDefinition slacktrajectory435_SA1018_Si
     7         2817299.606861trajectory399_SA1018_Sitrajectory438_SA1018_Si
     8         2817299.606861trajectory419_SE1011_Sitrajectory287_SE1011_Si
Using devex.
Using devex.
Primal simplex solved model.

As may be seen there is no change in the objective value, this indicating degeneracy. Instead of my newly generated column ending up in the basis, "older" columns end up in the basis (but no change in objective value is observed.) Is this behaviour in CPLEX as expected? If "older" columns are candidates to enter the basis (with no change in objective value), will we not run the risk of running in circles with the same variables entering and leaving the basis again and again?

A degenerate primal solution corresponds to multiple dual solutions. When you add a new primal column, you are simultaneously adding a new dual constraint. That new dual constraint will cut off the dual solution that was previously being used for pricing. After a bunch of pivots (while stuck at the degenerate primal corner), you end up with a new dual solution. The good news is that the dual solution that produced the pricing that led you to generate trajectory457_SA1018_Si will never be feasible again (as long as you keep the column for trajectory457_SA1018_Si in the master problem), so I don't think you have to worry about cycling.

Originally posted by: Perth2

Thanks a lot for your answers, Paul.