0

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.

RobPratt
  • 32,006
  • 1
  • 44
  • 84
CHE
  • 113
  • 7

1 Answers1

1

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.

See also Variable bounds in column generation

RobPratt
  • 32,006
  • 1
  • 44
  • 84
  • 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 '23 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. – RobPratt Dec 23 '23 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 '23 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: https://or.stackexchange.com/questions/9059/cant-solve-a-specific-instance-of-gilmore-gomory-cutting-stock-with-delayed-c – RobPratt Dec 23 '23 at 19:30
  • oh I see now what you mean. Thank you for your help. It is very clear for me. – CHE Dec 23 '23 at 19:55