# How should one proceed with column generation when the subproblem generates only columns with positive reduced costs?

I try to solve a MILP with Column generation. The Master Problem is a minimization problem with " $$\le$$ " constraint which lead to non-positive dual values. The problem is that the subproblem returns just columns with positive reduced cost which seems logical because $$\overline{c_{i j}}=c_{i j}-\pi_{i j}\geq 0$$, where $$c_{i j}=d_{i j} \text{(distance to travel from i to j)} \geq 0 \forall(i, j)$$. The question is how could make progress in Column Generation algorithm in this situation. (N.B: The objective of the Master Problem is to minimize $$\sum_{r \in \bar{\omega}} c_r y_r$$, and the objective of the Subproblem is to minimize $$\sum_{(i, j) \in r} \overline{c_{i j}} x_{i j}$$.)

• Is that any possible to transfer your formulation to greater than or equal to? Sep 20 at 14:14
• The nonpositive dual values should not create any difficulties. To diagnose the problem, I think we need to see more details of the master and pricing problems.
– prubin
Sep 20 at 18:40
• I think you should get non-negative duals. What solver are you using? Maybe it doesn't follow the same convention for dual signs Sep 22 at 13:59
• What I see happening here is that because your packing constraints restrict the covering of each item by above, the optimal solution of your problem is the empty column, of cost 0. I also suspect that this column somehow cannot be feasible, meaning that there must be at least one other constraint pushing your column to cover items. This is where negativity would appear. I concur with Dr Rubin that these are mere speculations if we do not get to actually see the models and context under which you are applying them Sep 22 at 23:04