Originally posted by: Ouali

Hi Cplex users and developers,

I'm applying a column generation to solve a big instances for a MIP problem, which contain a large number of columns. The column generation is applied only on the root node - that is the relaxation of MIP is solved at each iteration using primal Simplex, a best column is added to the LP, and repeat the process until no column is found. I was observing that Cplex's primal Simplex takes on average the same time to solve the relaxation, I wonder if Cplex's primal Simplex manage to use previous information about previous iteration of column generation in order to solve the current relaxation? Especially, computing inverse matrix as the LP model of previous iteration is quite similar to the current one, the only difference is the added column!

Thanks for your answers.

Regards

---

Ouali

Originally posted by: BoJensen

It's a bit unclear to me how you implement the column generation, but in general CPLEX will reuse a previous simplex solution stored. If you add a column, this new column will probably become non basic (at zero), the previous basis will still be primal feasible, but iterations may be applied to find the optimal solution (the added column may violate dual feasibility i.e reduced costs). You should look at the log output and confirm the expected behavior. 

Originally posted by: Ouali

Hi Bojensen,

I detailed the algorithm of column generation in another post Column generation algorithm.

I didn't look yet at the log file, but I didn't understand the quote "(the added column may violate dual feasibility i.e reduced costs)", If you look to the algorithm, you will find that the added column - that is added to the current LP, have the best reduced cost, this is why I didn't understand. I know that primal Simplex maintains primal feasibility and works towards dual feasibility, which is already done by the current iteration of column generation?

I will inform you if I found something in the log file.

Regards

---

Ouali

Originally posted by: BoJensen

By "(the added column may violate dual feasibility i.e reduced costs)", I meant in step 5) before calling the primal simplex algorithm, the solution should be primal feasible, but you have added columns in 3) which have a negative reduced cost. Such columns are said to violate dual infeasibility.

Originally posted by: Ouali

Sorry, now it is clear for "iterations may be applied to find the optimal solution". Thanks for the answer.