# Question on Column generation

I am implementing a Column Generation algorithm to solve a set partitioning problem. The master problem takes the form : $$\min \sum_{i \in I} c_i \lambda_i$$
s.t
$$\sum_{i \in I} a_{ji} \lambda_i = 1, \forall j \in J, \text{(each element j can be partitioned to exactly one partition i)}\\ \lambda_i \in \{0,1\}$$
where $$J$$ is the set of elements to be partitioned, $$I$$ set of all partitions, $$c_i$$ the cost of partition $$i$$, binary parameter $$a_{ji} =1$$ if element $$j$$ is in partition $$i$$, and each column $$\lambda_i$$ is a binary variable equals 1 if partition $$i$$ is selected in the optimal solution.

After relaxing the integrality constraint on $$\lambda_i$$, let $$\pi_j$$ be the dual variable of each partitioning constraint. Using this dual info, a pricing problem which is solved exactly through a MILP model to find one or more new columns with negative reduced cost : $$\hat{c_i} = c_i - \sum_{j \in J} a_{ij} \pi_i$$.

However the problem I have, is that after comparing the solution of CG approach to a brute force method (full enumeration of all partitions for small instance), i found out that for example one column that was not added to the master problem because it has a positive reduced cost ($$c_i > \sum_{j \in J} a_{ij} \pi_i$$) appeared in the optimal solution of the SPP in the brute force method. Which is quite surprising.

I would like to know if anyone has dealt with the same issue? or is there something I am overlooking here? If needed I can provide you with a small example.

I have seen such behavior when relaxing $$\lambda_i$$ to $$[0,1]$$, because the reduced cost calculation does not include the dual variable that corresponds to the (redundant) upper bound $$\lambda_i \le 1$$. Try relaxing to $$\lambda_i \ge 0$$ instead.

• Thank you for your answer. While it successfully solved the issue on a few instances, it persists in others. Any suggestions or ideas on how to fix this ? Thank you.
– CHE
Dec 23, 2023 at 18:15
• Are you perhaps taking the columns that were generated by relaxing $\lambda$ and then solving a restricted master MILP with those columns? That price-and-branch approach is only a heuristic and is not guaranteed to find an integer optimal (or even feasible) solution. Dec 23, 2023 at 18:28
• Suppose we have an upper-bound on the size of partitions ($k$: number of items in a partition). I initialize the RMP by partitions of size k=1 (easy to solve). For k=2 I use the duals from the RMP containing columns of k=1 to generate columns of k=2 with negative reduced cost. Similarly, for k = 3 I use duals of columns of size 1 and 2. Finally I solve the RMP with integrality constraints. If we can enumerate all partitions of size 2 (or 3) in advance and use the dual info as a checker to calculate the reduced cost, wouldn't this guarantee finding an integer optimal solution?.
– CHE
Dec 23, 2023 at 19:12
• No, there is no such guarantee. In general, you need to branch on $\lambda$. You might want to take a look at this example: or.stackexchange.com/questions/9059/… Dec 23, 2023 at 19:30
• oh I see now what you mean. Thank you for your help. It is very clear for me.
– CHE
Dec 23, 2023 at 19:55