Originally posted by: martin#r

Hi,

I am doing column generation in cplex. Due to small overhead I generate all constraints in advance. As a result some constraints are trivial in the beginning. For example 0 <= x <= inf, when x is a variable between 0 and 1. In the pricing iterations these constraints get modified to 'make sense'. During this step of the solution process all variables are continuous (i.e. IloNum).

The problem I encountered is that getDual fails for some constraints, i.e. I get "CPLEX Error 1217: No solution exists.". What I already tried is to disable preprocessing via:

and I also tried adding all variables explicitly via model.add. My current work-around is to catch the exceptions and assume dual values of 0 for this case which seems to work. I also tracked the number of exceptions during each iteration and they turned out to decrease as more columns are generated.

So is there a better way to recognize for which consraints dual values are available or might this just be the consequence of some other problem?

Thanks

martin

Dual values should be available for all constraints or none. The error 1217 indicates that you either did not call cplex.solve() or that you modified the problem after the last call to cplex.solve(). The latter is a common mistake. If you make any change to the model (such as adding/removing constraints, changing coefficients, changing bounds, ...) then CPLEX will invalidate any solution information it has stored and subsequent calls to getValue(), getDual(), etc. will throw a 1217 exception. So are you modifying your model between calls to getDual()? If so then try to first get the dual values for all constraints and only then start modifying your model.

Originally posted by: martin#r

Thank you. I indeed modified the model before I retrieved all dual values. I changed this and no more exceptions appear. However, the disadvantage is that I have to store all duals values before I can start pricing. When I solve the pricing subproblem I never need all information at once. I guess there is no way besides storing all dual values or collecting the constraints modifications and adding them after pricing is completed.

I know that column generation for the root node is in general not optimal. For one of my test instances I obtained the  optimum before the modifications but now I do not. I guess the reason is that due to the described behavior I added columns in a different way before.

EDIT: I tried to add only one column per iteration and now I get the optimal value again.

You do not need to retrieve all the duals in one call. If you know which dual or duals you want, you can fetch just those values (after solving the LP), do pricing, fetch additional duals as needed, ...

Originally posted by: martin#r

Thanks for the suggestion. I think I described the situation in a worng way. What I meant is that I do not need all duals for one call to the pricing algorithm but I need all of them during the whole pricing iteration. I call the pricing algorithm multiple times, each time with a different part of the dual values and each of these calls may identify a variable to be added.

Another way to fix this problem would be to not apply your problem modifications directly but instead queue them up and in the end apply all of them in one shot via IloNumVarArray::setBounds() and IloRangeArray::setBounds(). That is the recommend way for making multiple changes to a model anyway.

Originally posted by: martin#r

Queuing up would indeed be a solution. However, I am doing more than just setting bounds. I really add new variables which have to be added only to some of the constraints with certain coefficients. Storing this information is also not quite easy and also has some overhead.

The good thing is that it turned out that I get better results when adding only one new variable per iteration. Thus, I do not have to retrieve any further duals after this single variable has been added. Therefore, I do not need to store the dual values.