Originally posted by: DSL

Dear all,

I am using CPLEX 12.5 concert technology to implement a column generation (CG) algortihm to solve some large-scale LP.

Since my program got stuck after a few iterations during some test runs, I was debugging my code and experienced a really strange phenomenon.

At first glance, the reason why the CG algorithm failed was that it ran into an infinite loop repeatedly finding a specific cloumn with positive reduced cost, but this column was already existing in the master problem. (Reduced costs should be positive in this case since the master is a maximization problem.)

I immediately checked that none of the following causes were responsible for the failure:

1) Dual prices from the master are accessed correctly. (No unnecessary copies of the dual prices are made, i.e., I feed the pricing problem using the original values from the cplex instance which solves the master problem.)
2) Reduced costs are computed correctly and there is no confusion in the definition of 'reduced costs'.

Out of curiosity, I checked the validity of the dual prices coming from the master. Therefore, I started the CPLEX interactive optimizer, solved a given instance of the master, and compared the dual prices against the values concert technology told me within my application.

Surprisingly, both sets of dual prices were remarkably different. Furthermore, using the dual prices from the interactive optimizer, the reduced cost of the generated column were zero. Thus, if concert had used the "right" dual prices, then the pricer would not have priced out an existing column (at least not with positive reduced cost).

Does anyone have had similar experience? Is there anything that can be done to be sure that reduced costs are always computed based on correct (not misleading) dual prices?

Any comments are greatly appreceiated.

Best regards,
David

Originally posted by: UserCplex

I have had experience with this, but on probing the issue further, it has always been that the error was on my end. The usual culprits were:

(1)Tolerance value. I initially set epsilon value at 1e-8. In some instances, the reduced cost was between 0 and -1e-8. (I was solving a minimizing master problem.). So, even though the column should actually price out to zero reduced cost (the column was already in the basis), due to numerical issues, the column was regenerated. I modified the epsilon value to 1e-5 and did not encounter the problem subsequently.

(2)Are you pricing at the root node or at a child node? Depending on your branching strategy, you are going to regenerate columns that actually have a negative reduced cost. This can occur in child nodes where there is a <= branching constraint. So, even though the column is already in the basis, this variable has a negative reduced cost. Your pricing algorithm has to be modified/changed so that you do not regenerate such columns.

Good luck.

Originally posted by: DSL

@ UserCplex: Thanks for your answer.
(1) I can confirm that it is definitely not a numeric issue in my case.
(2) I am pricing at the root node since I try to solve a pure linear prorgam.

@ all: I tested what happens when the master problem is re-extracted in each iteration before the master is actually solved. And see there, the dual prices are now 'correct' in the sense that the algorithm regenerates an existing column due to misleading reduced costs.

Despite that I have a workaround for now (of course, it requires some further experiments to see if the failure really happens no more...), I am still confused.

As I learned from here, one should take advantage of CPLEX' capability to use advanced basis information when succesively solving (slightly altered) models. Now, it appears that I should do the reverse and let CPLEX solve the master problem in each CG iteration from scratch....?

Regards,
David

Originally posted by: UserCplex

David,

The whole point of Branch and Price is that newly discovered columns can be pivoted into the basis in a handful of iterations once they are discovered. So, it is crucial that the restricted master problem continues to maintain its current basis.  It is a bad idea to re-extract models and solve the entire restricted master problem afresh again when new columns are discovered.

By default, CPLEX maintains the current basis and turns pre-solve off when columns are being added to a model during branch and price. So, with default settings, you should be good to code your own branch and price code.

Are you sure you have coded your pricing algorithm correctly?

Originally posted by: Laci Ladanyi

Did you properly account for the dual values corresponding to the variable bounds? If you have non-zero variable bounds (e.g., you have binary variables which implies having an upper bound of 1) then in a CG scheme it is not sufficient to extract the dual values corresponding to the rows of the matrix, you also need to account for the duals corresponding to those bound constraints. You should either avoid having variables with nonzero bounds (usually this is trivial since most of the time the variables are binary and there are clique-type constraints on the generated columns which will automatically enforce an upper bound of 1 on the variables), or if you do have variables with nonzero bounds then you have to account for the duals corresponding to the bound constraints (and these values are not returned when you query the solution, you have to derive then from the other available vectors, like reduced costs, duals, primals).

--Laci

Originally posted by: Perth2

Hi Laci. Must you also account for the duals of a variable with a lower bound of zero? If not, what is the rationale?

The fact that the interactive optimizer gave you significantly different dual prices suggests that your master problem solution may be degenerate. In that case, the column generation problem may be workingfrom equally valid dual prices, but perhaps some tiny numerical issue prevents the resulting new column from entering the basis. When this happens, you might try making a slight random perturbation of the master problem right hand side (to break up the degeneracy) and see if that breaks the bottleneck.

Paul

Originally posted by: Mathsg

Hello sir,

I am getting an error of (Scripting runtime error: Undefined methode 'add') while optimizing the network planing problem through column generation method. Master problem has been relaxed for the given set of lighpaths for a flow between source to distination while pricing problem give me the result 6 which seems to be not correct as pricing problem should display the results with negative number if there is a lightpaths which can improve the master problem but PP give me positive result while in declaring next iteration for the MP OPL give me the mentioned above error. Kindly guide me how to write next iteration part for master problem to put the value of sub problem and also how to get the value of sub problem with the negative values. I am looking forward to hearing from you. thank you

Originally posted by: DSL

The erroneous computation of the reduced costs was due to a tiny little (but not obvious) bug in the objective function of the pricing problem. Argh... So, thanks to UserCplex for referring me back to that point again!

Thanks to Laci and Paul for your suggestions as well.

Regards,
David

Originally posted by: Perth2

Hi David. I have a similar problem. Can you tell me what your "tiny little (but not obvious) bug" was for inspiration?