Originally posted by: Matt31

Hi,

I've implemented a Dantzig-Wolfe algorithm (i.e. column generation) using CPLEX to solve the LP master problem. I'm working with the Java API. There were a number of other forum postings on the subject of column generation, and I followed the instructions to reuse the same IloCplex object for each iteration of Dantzig-Wolfe. That is, I define an IloLPMatrix and only add columns directly to this between calls to IloCplex.solve(). As noted in another post, reusing this IloCplex object should maintain basis information even after I've added new columns.
https://www.ibm.com/developerworks/forums/thread.jspa?messageID=14833017&#14833017

When I allow CPLEX to solve the master completely, the master's objective monotonically decreases each iteration. However, I found that when I limit the number of Simplex iterations to some small number (e.g. 10) with IntParam.ItLim, CPLEX sometimes reaches an objective that is worse than the previous iteration. This only seems possible if it's not re-using the basis status.

Accordingly, I started using setBasisStatuses() as below. However, the same problem occurs: limiting the number of iterations sometimes causes CPLEX to find an objective that is worse than the previous iteration.

cplex.setParam(IntParam.AdvInd, 1);
for (dwIter = 0; dwIter < maxDwIter; dwIter++) {
cplex.setBasisStatuses(warmStart.numVars, warmStart.numVarStatuses, warmStart.ranges, warmStart.rangeStatuses);
cplex.solve();
warmStart.numVarStatuses = cplex.getBasisStatuses(warmStart.numVars);
warmStart.rangeStatuses = cplex.getBasisStatuses(warmStart.ranges);

// Solve subproblems and add columns to |cplex|...
}

Is there a way to know for sure whether the basis is being used? If it's not, could there be something I'm missing?

Thanks a lot,
-Matt
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

Just to be sure, your new columns do not come with strictly positive lower bounds (or strictly negative upper bounds), correct?

What algorithm do you use to solve the master? Primal simplex?

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: Matt31

Each of my new columns, \lambda, corresponds to an extreme point of a Danzig-Wolfe subproblem. So they are lower bounded by zero:
IloNumVar lambdaVar = cplex.numVar(0.0, Double.MAX_VALUE, String.format("lambda_{%d}^{%d}", s, numLambdas++));

I've used both Primal simplex and Dual simplex to solve the master. With both algorithms, I've observed the aforementioned behavior: that after adding new columns, restricting the number of iterations, and using setBasisStatuses to set the basis to the solution from the previous solve, the master can return an objective function higher (for minimization) than the previous call to solve the master.

Just to clarify, my example code in the first post is an oversimplification of my use of setBasisStatuses(). In fact, I also set the basis status of all the new columns to BasisStatus.AtLower.

-Matt
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

It certainly seems that you're doing everything correctly, and I agree that the previous basis (with the new columns nonbasic at lower bound 0) should still be primal feasible, so progress should be monotonic. You might try setting SimDisplay = 2 (log every simplex iteration), along with a small iteration limit, and see if it reveals anything. You might also try printing the warm start information both at the end of a master solution and at the start of the next master solution, and see if anything looks funky.

One other possibility (groping in the dark here) is that you might try turning off presolving. I don't know if CPLEX will do anything during presolve that might screw up the objective value from a warm start.

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

Looking at the individual iterations in the simplex log file can indeed shed some light on the issue.
For example, it could happen that CPLEX encounters numerical difficulties, or that it perturbs the objective function.

What is the condition number of the optimal LP basis before you add the new columns?
Tobias
#CPLEXOptimizers
#DecisionOptimization