I have a binary minimization programing problem that is non-convex (it is not concave either).
Originally, I used Lagrangian multipliers to get the Lagrangian dual problem to have a lower bound on the solution of primal. The dual problem was solved by sub-gradient method. In each iteration of this method, I had a new solution to the primal problem. But the end result was not a feasible solution for primal.
I asked around and realized that Lagrangian relaxations do not ensure feasibility. I was told to use Column Generation method to solve the dual sub-problem.
Do I need to apply the column generation method to my non-convex problem or its Lagrangian dual?
When using column generation, you need to iteratively solve a master-problem and a sub-problem. The master problem must be linear, but the sub-problem may not. The reason for this is that the output of the master-problem are dual variables (which you can easily get once the simplex algorithm is over), while the output of the sub-problem is simply a column: a variable for the master-problem. This column can be obtained with any algorithm, including algorithms for non convex optimization.