Originally posted by: lbr33

First of all, is it ok if, in a column generation algorithm, the pricing subproblem generates  redundant columns (columns that were previously added to the master problem)?

Believing that it is the case, it is necessary to verify, at each iteration, before adding a column, if this column hasn't  been already added before to the master problem?

Or it is possible to guarantee the convergence of the algorithm even though redundant columns are added to the master problem?

Originally posted by: UserCplex

The pricing subproblem should not generate redundant column. If it does that, either there is a bug in your code, or else, your threshold for deciding whether a column has negative reduced cost (assuming master problem is a minimization problem) needs to increase. In any case, it is unnecessary in a rightly programmed code to check if a new column already exists in the master problem.

Note that in a minimization master problem, all columns already discovered and present in the master problem either have 0 reduced cost or positive reduced cost (those columns not in the basis). So, if your pricing problem regenerates such columns, you are wrongly concluding that the column has negative reduced cost.

The only other case where a pricing problem can legitimately discover a negative reduced cost column is when your master problem branches on such variables directly. Then, any branch where that variable is upper bounded, it will have a negative reduced cost. However, you may want to then reconsider your branching strategy to avoid branching on such variables directly. If that is somehow not possible (i.e., if it is not possible to develop alternative branching rules), then, you will have to redesign your pricing algorithm to disregard already discovered columns and return the most negative reduced cost column that is not part of the master problem.

Originally posted by: lbr33

Thanks for your answer.

I am worried exactly with the case when a variable (column) gets a value equal its upper bound.

In that case, the variable will have a negative reduced cost and then can be detected in my pricing subproblem.

I didn't get the part of changing my branch strategies.

I am dealing with a linear programming and not with a mixed-integer program right now. I am using column generation to find a lower bound to my original problem.

Could you be more clear please?
 

Originally posted by: UserCplex

Suppose you are solving a facility location problem. The pricing problem is supposed to give an assignment of customers to assign to a facility, say. Suppose each column of the master problem encodes an assignment. If you branch on this assignment variable directly, then in the branch where this variable is restricted to 0, you will have a negative reduced cost for this column. Then, your pricing algorithm will have to somehow exclude this assignment. That is likely to be difficult. In many cases, if the pricing problem is polynomially solvable, finding an assignment while excluding a set of assignments generally tends to not be polynomially solvable. 

One way around would be to branch on the following idea. One child will include two customers i and j in the same assignment. Another child will never include i and j in the same assignment. In this case, the pricing problem can possibly be solved with minor changes.  See http://scip.zib.de/doc/html/BINPACKING_BRANCHING.php

You will encounter this problem only at non-root nodes of the branch and bound tree when you are doing branch and price. This problem does not arise if you are solving the LP relaxation at the root node.

Originally posted by: lbr33

Sorry, but I am making a confusion.

Suppose I call my column as lambda variables.
Suppose that the lower and upper bound of them are 0 and 1, respectively and that lambda is >= 0.
Suppose that the pricing subproblem finds all column with negative reduced cost.
If a non basic variable, lambda_1, (column) is active (receiving the value of 1) in the master problem in iteration i, and if the reduced cost of this value is negative, in the pricing subproblem, in iteration i+1, I will found lambda_1, won't I?

Your pricing problem uses the dual values of the master problem constraints, correct? Let's say that it generates variable lambda, which you add to the master problem with an upper bound. That upper bound was not previously part of the master problem (since lambda did not yet exist). Let's say further that lambda reaches its upper bound in the next master problem solution, with a negative reduced cost. You need to incorporate the negative reduced cost in the pricing problem, treating it exactly as if it were the dual value for the constraint lambda  <= upper bound (which it in fact is). I believe that will give you a zero objective value for lambda in the pricing problem, so you won't generate lambda again unless the pricing problem optimal objective value is zero (in which case you have run out of useful columns and are done).

Originally posted by: lbr33

I didn't get how I will incorporate the dual variable related to the upper bound constraint in the reduced cost.

Suppose I have the minimization master problem below:

min sum_{k in K} COST_k * lambda_k _ sum_{(i,j) in W} c_ij * x_ij

sa:

r1: sum_{(i,j) in W, (k,m) in A}: x_{ijkm} = w_ij
r2{(k,m) in A}: sum_{(i,j) in W} x_{ijkm} <= sum_{k in K: (k,m) in k} cap_{k} lambda_{k}

r3{p in P}: sum_{k in K: f(k) == p} lambda_{k} <= b_{p}

r4{k in K}: lambda_{k} <= 1

r5{(i,j) in W, (k,m) in A}: x_{ijkm} >= 0

r6{k in K}: 0 <= lambda_{k} <= 1

K represents the set of columns that have been already generated, lambda_{k} represents the column.

Then, to calculate the reduced cost of lambda_{k}, without considering the dual variable related to r4, we have:

reduced_cost_lambda_{k} = COST_{k} - ( - sum_{(k,m) in A: (k,m) in k} var_dual(r2)*cap_{k} + var_dual(r3)

To consider var_dual(r4), I need to verify if the column have been already added to the master problem, don't I?

If it is the case, I think  it will becomputationally hard.

Let's say k0 is the index of the most recently generated column. If you add another inequality in r4, corresponding to k = k0, and if lambda_{k0} ends up 1 in the new solution to the master, you should have a negative dual value for r4{k0} and zero reduced cost for lambda_{k0} ... and no problem. Does your master problem really contain the r4 constraints?
 

Originally posted by: lbr33

The thing is that the dual variable r4{k0} will be part of the calculation of only lambda_{k0} reduced cost, won't it?
As I understand, the dual variable r4{k} participates of the calculation of the reduced cost of lambda_{k}, if lambda_{k} has been already added to the master problem.

To know that I need to verify, for each generated lambda in the pricing problem, if this lambda has been already added to the master problem or not.
 

Yes, you have identified a key difficulty. It's tied to the fact that you are bounding the new columns individually (maximum value of 1 each), rather than with a shared bound (say, sum of all lambdas <= 1). In the latter case, you would know the dual value to apply to that constraint when you formulated the subproblem, and it would apply regardless of whether the subproblem solution was new or not. In your case, the dual value is specific to the subproblem solution.

I'm not a column generation user, but I don't recall every seeing an instance of column generation where the master problem contained constraints specific to a single column. So you may be trying to do something for which column generation was not designed.