Originally posted by: Ouali

Hi Cplex developers and users,

I implemented column generation using the following steps :

1. Set up initial LP.
2. Solve with dual simplex.
3. Query dual solution and find new columns with pricing method. If nothing found, goto 7.
4. Add new columns to LP.
5. Solve with primal simplex.
6. Goto 3.
7. Declare all the added variables to be integer constrained.
8. Solve problem as MIP.

However, for my problem, I know that the optimal solution can be found in the root node using Cplex B&B fixed on the root node, but the solution given by these steps of column generation said that the solution is optimal which is in reality not the case. Another question of practical insight, why column generation takes so long to find a solution even on the root node? I experimented this on some moderate problems that can be solved directly by Cplex B&B.

Thanks for any answers.

---

Ouali

Originally posted by: EdKlotz

I'm not sure I follow.  In particular, there are two MIPs here.   First, there's the complete MIP associated with "the problem".   Then there's the MIP resulting from your column generation procedure, which typically will only have a subset of the columns of the complete MIP.    Because it does not have all the columns, it's objective can indeed be worse than the objective associated with MIP for the complete problem.   Your column generation procedure, which is frequently used in practice, is a heuristic designed to find good solutions, not an algorithm to find a provably optimal solution.    In situations where the total number of columns in the whole problem is too large to handle explicitly, this heuristic is often used.   However, based on your description here, it sounds like your complete model doesn't have an unmanageable number of columns, so you may be better off just passing the complete problem to CPLEX's B&B directly.   Note also that you can take the optimal solution from step 8 in your procedure and use it as a starting solution for the complete MIP.

Originally posted by: Ouali

Hi EdKlotz,

Thanks for replying.

My problem is unmanageable by Cplex's B&B, I'm using moderate instances in order to test this approach w.r.t the optimal solution before applying it to the big instances.

I would like to clarify more this heuristic and the situation:

Actually, there is one MIP (Let's call it LP, because all the variables are declared as Float) which is constructed by column generation approach (steps 1 to 6). This procedure allows to apply the column generation only on the root node of Branch and Price, as we don't have access to the whole tree in Cplex. So if we know that the optimal integer solution is reached on the root node by Cplex's B&B, this heuristic provides indeed the optimal solution to our second MIP. The second MIP (Let's call it ILP) is just a copy of the LP constructed by column generation except that the variables are now integers, it is used in order to find a feasible solution if the optimal solution can't not be found in the root node, and here we can accept that the solutions are worse compared to the optimal, which are in practice good ones.

So, I know that solving LP provides an integer optimal solution, no need for branching, which means that column generation applied to the root node must provide also an optimal solution, which is not the case when testing it, if my comprehension of the heuristic is correct!

Regards

---

Ouali

Originally posted by: EdKlotz

Sorry, but I don't follow your claim about optimality at the root node.    You first solve an LP by column generation, giving you an optimal LP solution for an LP associated with a subset of the columns of the original MIP you actually want to solve.   You now change all of the variables in this subset of columns to integer.  If CPLEX solves this MIP (ILP in your terminology) at the root, that does NOT mean that your solution to LP solved by column generation is optimal for ILP.  Nor does it imply that the objective values will match.    In fact, your column generation to LP may not be even integer feasible.   The reason for these differences  is that

1. When you turn the problem into a MIP and optimize, CPLEX applies MIP presolve reductions based on the integrality of the variables that were not applied during any of steps 1-6 of your column generation procedure.    These may tighten the formulation in a way that eliminates fractional solutions in your solution to LP, resulting in an optimal solution for ILP at the root which will have a different objective than the optimal objective to LP computed by your column generation scheme.
2. The root node includes a cut loop that applies cuts based on integrality that are completely missing from the optimization of LP.   As with MIP preprocessing, these can cut off fractional solution values that were acceptable in your optimization of LP.
3. Similar to 1 and 2, CPLEX's MIP heuristics can find feasible solutions at the root, which in turn enable fixings based on the resulting incumbent objective value (e.g., reduced cost fixing if you are familiar with that).   These can be viewed as a specific type of cut.

Perhaps I misunderstood something, but I don't think you should expect consistent objective values when solving LP by your column generation and solving MIP by CPLEX's B&B, regardless of whether it stops at the root (even if it does so before applying any cuts or heuristics).

Originally posted by: Ouali

Hi EdKlotz,

Thanks for clarification,

If I understand quite well, there is a presolving step of the models that results in different solving behavior, so we can't claim/guarantee that column generation on the root node will find the optimal solution even if the optimal solution is found on the root node by Cplex's B&B. 

To summarize, if we consider a problem P, solving restricted MIP by Cplex's B&B will result in a modified problem (let's call it A), while solving restricted LP will result in a modified problem (let's call it B), this modification is based on the presolving step which treat different formulation (here, the integrality of the variables for MIP). The search tree will be different in the two cases, especially at the root node.

The third point, even if I disable the presolving step, I can't claim about optimality on the root node of column generation as Cplex uses different heuristics for its MIP relaxation which are not the same for our LP. It sounds interesting to know these heuristics!

Well, thanks again for your feedback :-)

Regards

---

Ouali

Regards

---

Ouali