Originally posted by: leoli

Dear all,

Can I use CPLEX and C language to implement the column generation? In CPLEX, I saw one chapter of column generation where C++ is suggested.

Thanks.

Leo
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

Yes, you can easily do this. CPLEX offers the possibility to query dual values and reduced costs, add new columns, and resolve the LP from a previous start basis.

Note, however, that CPLEX does not support branch-and-price (i.e., solving a MIP while adding new columns in the nodes of the search tree).

A very typical heuristic procedure to find good solutions to very large MIPs with column generation is the following:

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. Install 'ctype' vector to declare all or some of the variables to be integer constrained.
8. Solve problem as MIP.

Sometimes it is better to use the barrier algorithm in steps 2 and 5 instead of simplex. This depends on the structure of the problem.
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: leoli

Thanks.

But I want to know is it possible to implement the branch and price using CPLEX?
Do you have any suggestion about implementing the branch and price? Do we need to manage the whole tree by ourselves?

Leo
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

No, CPLEX is not able to handle branch-and-price. During MIP branch-and-bound search the number of columns has to stay constant.

I see only two options:
1. You manage the search tree yourself and use CPLEX only as the LP solver engine.
2. You implement the heuristic procedure I mentioned (column generation at the root, then solve the resulting problem as a MIP). Of course, this will not necessarily provide an optimal solution.

I think that for real world problems, approach 2 is good enough in most of the cases. You get a valid dual bound (you solved the root node completely by column generation), and most of the time a pretty good primal solution. For most column generation problems that I know the dual bound at the root is already pretty close to the true optimum, and the final gap will be reasonably small.

If you really want to do branch-and-price (I guess because you are an academic researcher and want to know the true optimum to your problem), you should consider to use frameworks like Abacus or SCIP. You can still use CPLEX as LP engine to get the reliability and speed of CPLEX, in particular for large problem instances.
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: leoli

> Tobias Achterberg wrote:

> If you really want to do branch-and-price (I guess because you are an academic researcher and want to know the true optimum to your problem), you should consider to use frameworks like Abacus or SCIP. You can still use CPLEX as LP engine to get the reliability and speed of CPLEX, in particular for large problem instances.
Yes I want to optimally solve the problem using the branch and price.
So as you stated, I have to consider other framework to develope the branch and price.
Can you give me the code of Abacus or SCIP? Do you have any example of implementing this framekwork?

Thank you very much.

Leo
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

I don't know too much about Abacus. SCIP can be downloaded from scip.zib.de, and it includes some examples for branch-and-price and column generation. If you need further help, please contact the SCIP team.

Since you have CPLEX, I really recommend to use CPLEX as LP solver. In particular for large LPs it is much better (speed and stability) than Soplex.
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: leoli

Thank you very much. I will downloda the code and try to implement it.

Leo
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: bob3333

please help me to implement column génération heuristic on cplex with the .mod and .dat from opl fleet example file

thanks in advense
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

Starting with column generation as a novice user is certainly not a good idea as this is pretty complex, both from a mathematical point of view as well as an implementation point of view.

I suggest that you start with browsing through the various examples that are part of the CPLEX and OPL distributions. From thereon, you should be able to improve your CPLEX skills and then ask more specific questions.
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: bob3333

hello

I have a large mip to solve with colum generation and price and cut methodes , I'm very interested in your heuristic but I'm new in cplex (java) I dont know how to do, would you please help me to implement your heuristic for this mip :
//creation des variables.
IloNumVar][ x = new IloNumVarI][;
for (int g = 0; g < W; ++g) {
y[g] = new IloNumVar[J];
for (int j = 0; j < J; ++j) {
y[g][j] = cplex.numVar(0, Double.MAX_VALUE, "y_" + g + "_" + j);
}
}

for (int i = 0; i < I; ++i) {
x[i] = new IloNumVar[J];
for (int j = 0; j < J; ++j) {
x[i][j] = cplex.boolVar( "x_" + i + "_" + j);
}
}
//coefficients of objectif function randomly

Random rand2 = new Random();
c = new double[I][J];
for (int i = 0; i < I; i++)
for (int j = 0; j < J; j++)
c[i][j] = 5000 + rand2.nextInt(30000 - 5000);

// Create objective function.
IloLinearNumExpr obj = cplex.linearNumExpr();
for (int i = 0; i < I; ++i) {
for (int j = 0; j < J; ++j) {
obj.addTerm(-c[i][j], x[i][j]);
}
}
//constraint
for (int i = 0; i < I; ++i) {
IloLinearNumExpr contr = cplex.linearNumExpr();
for (int j = 0; j < J; ++j) {
contr.addTerm(1, x[i][j]);
}
cplex.addEq(contr, 1, "constraint_" + i);
}
//
cplex.addMinimize(obj);

thank you so much
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: sana_

I want to know why choosing the dual simplex in the first iteration of the column generation, then using the primal one ? I see in the documentation of ILOG that the dual simplex provides more possibilities to store informations on the basis ? So why not to continue the column generation algorithm with the dual simplex?

Thanks !
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: T_O

I am not an expert on column generation, but in general, a basis remains primal feasible when you add new columns. It does not remain dual feasible in general. So you can just warmstart primal phase 2, but you could not warmstart dual phase 2.

Best regards,
Thomas
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: sana_

Thanks for your answer.
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: sana_

I want to know why choosing the dual simplex in the first iteration of the column generation, then using the primal one ? I see in the documentation of ILOG that the dual simplex provides more possibilities to store informations on the basis ? So why not to continue the column generation algorithm with the dual simplex?

Thanks !
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

I am novice at CG and I use row-based model to implement CG.

1. Create a LP model using a set of variables A.
2. Solve and obtain dual through getDual(..)
3. Add new variables to A.
4. Remove LP model (using model.end() , variables.end(), ...) - I posted a thread that you may find it useful about removing a model.
5. Repeat step 1-4.

Only a problem I notice that sometimes the objective value is worse after adding variables and then converge to a optimal solution. It seems to be a bug.
#CPLEXOptimizers
#DecisionOptimization