I am dealing with an integer model, and I'm using Dantzig-Wolfe (DW) algorithm that I have developed in Matlab to decompose the model into a master and sub-problems. I put the integer constraints in the sub-problems. The algorithm works fine; however, for some integer models I end up with a solution that needs to be rounded to nearest integers. I'm wondering: 1)am I using DW in the right context? I mean can DW be used to solve integer problems? does the model have to be continuous LP? Because an integer model in not convex. Doesn't DW require convexity? 2)How can I avoid rounding the solution? What improvement do I need to apply to the algorithm? In the following I have elaborated the issue.
Assume the structure of the model under study is as below: $$Min\ c_1^Tx_1+c_2^Tx_2+...+c_i^Tx_i+...+c_n^Tx_n$$ $$s.t. A_1x_1+A_2x_2+...+A_ix_i+...+A_nx_n=b$$ $$B_1x_1=r_1$$ $$B_2x_2=r_2$$ $$.$$ $$.$$ $$.$$ $$B_nx_n=r_n$$ $$x_i \in \{0,1\}^{m_i}$$ We know that the above model has the following restricted master problem (RMP): $$RMP: Min\ \sum_{i = 1}^{n}\sum_{i \in J} \lambda_{ij}(c_i^Tx_{ij}) $$ $$s.t. \sum_{i = 1}^{n}\sum_{i \in J} \lambda_{ij}(A_ix_{ij})=b \ \ \ \ \ (\pi_{0j})$$ $$\sum_{i \in J}^{n}\lambda_{ij}=1 \ \ \ \ \ (\pi_{ij})$$ $$\lambda_{ij} \in \mathbb{R_+}$$
The subproblems are: $$SP_i: Min \ (c_i-\pi_{0j}^TA_i)^T-\pi_{ij}$$ $$s.t. B_ix_{ij}=r_i \ , x_{ij} \in \{0,1\}^{m_i}$$
$\pi_{0j}$ and $\pi_{ij}$ are the dual variables. We know at the end, which is when $0\leq (c_i-\pi_{0j}^TA_i)^T-\pi_{ij}$ for any $i$ and $j$, the final optimal solution for subproblem $i$ is computed as $x_i^*$=$\sum_{j \in J} \lambda_{ij}x_{ij}$. This is where I get a non-integer value for $x^*$. The model is integer. All the $x_{ij}$ I get from the subproblems are integer. However, the result of the sum $\sum_{j \in J} \lambda_{ij}x_{ij}$ sometimes lead to a non-integer value, which I have to round up. The rounded $x^*$ is always the correct answer. Please let me know how I can avoid the rounding at the end of optimization. Why the sum leads to non-integer solutions?
Even if $x$ takes integer values, there is no guarantee that $\sum_j \lambda_{ij} x_{ij}$ does, and there is also no guarantee that rounding this convex combination gives you an optimal or even an integer feasible solution. When there are no more improving columns from the subproblems, you have solved the root node of the master problem. If the resulting convex combination solution is not integer, you then need to branch, and the full algorithm of column generation within branch-and-bound is called branch-and-price, which is what @Kuifje mentioned in a comment.