Originally posted by: A.Omidi

As far as I understand, this Gilmore-Gomory procedure assumes a very specific structure of the subproblem so that a dedicated algorithm can be applied.

Dantzig-Wolfe instead assumes a more general setting.

Originally posted by: A.Omidi

Hello Everyone 

About my last question, I solved a tiny LP problem using D-W decomposition. I try to solve an IP model (such as my lp model with the integrality constraints)  using the same algorithm. I solved master-problem using relaxation (RMIP) and solved subproblem using MIP. In the limited iteration, convergence achieved but when I check the solution its appear to be in the LP form. 

Would you please say that can I use LP D-W decomposition to solve IP models or its different and could you please help me to find a suitable D-W algorithm or example for solving MIP problems?

Best regards
Omidi. A

Dantzig-Wolfe is for LPs, not MILPs. For a column generation technique for MILPs, look up "Branch-and-Price" or "Branch-Price-and-Cut".

What you are doing (linear relaxation of the master, integer subproblem) sounds like Gilmore-Gomory to me. The way G-G works is that you repeatedly solve the relaxed master (LP), use the shadow prices to adjust the subproblem objective, solve the subproblem and add any new column it generates to the master. When the subproblem fails to find a new column, you are not quite done. You have to go back to the master, remove the integrality relaxation (so the master goes back to being an integer or mixed-integer program) and solve that to get an integer-feasible solution. Note that this is a heuristic; the final solution, while integer-feasible, is not guaranteed to be optimal.

Originally posted by: A.Omidi

Dear Prof. Rubin
Thanks so much for your replay.
I used from Column Generation reference in the attached file.

Would you please say that do this method (attached file) used for integer program or I should use branch and price or other techniques such as G-G?

Best regards
Omidi. A

There are some statements in your PDF file that I'm finding hard to digest (and in some cases appear incorrect to me).

In any case, there is an extension of D-W to integer programming. While I'm not particularly familiar with it, my impression is that the RMP is an integer program, not an LP. You relax the RMP to an LP to get dual prices, use them to generate new columns (which must be integer feasible in the original problem), add them to the (relaxed) RMP and continue until no new columns are generated. To this point, it resembles the G-G heuristic, although that was intended for a very specific problem (cutting stock). My understanding is that once column generation stops, you have to solve the RMP as an integer program to get a candidate solution to the original problem. Also (and again, I stress this is not something I use myself), my understanding is that this is typically embedded in a branch-and-price framework.

So my guess is that, assuming your problem requires column generation, you will want to use branch-and-price, and D-W may be employed at nodes of the search tree. But that's just a guess.

Originally posted by: A.Omidi

Dear Prof. Rubin
Thanks so much for your useful advice.

I try to use a branch and price framework for my problem.

Best regards

Omidi. A