Implementing decomposition method

GAMS
1

Dear support team,

I have often used GAMS and now have tried to implement a Dantzig-Wolfe Decomposition for an LP problem. It works fine for a small instance. Now, I’m trying to extend the DW-based algorithm to solve the MIP model. I’m aware that some of the algorithms like heuristic-based CG, can be implemented in the GAMS but, for the reasons, I would like to try exact methods. I know that it is a complicated work and needs some advanced methods such as branching rule, separating procedure, stabilization, etc. I mean in the context of branch and price or branch-cut-price. Also, I know there are some of the frameworks like SCIP, BCP, DIP and … to implement such methods.

My question is:

  1. Is there any way to implement BP/BCP to solve MIPs using GAMS? If so, how can I find any related documents about that?

Regards
A. Omidi

2

Hi,

back in the days (12 years ago?) I wrote a BP for the graph coloring algorithm in GAMS. This uses some advanced GAMS magic. You can freely use this, but I can’t/won’t support this any longer.
gc.zip (371 KB)
-Michael

3

Dear Dr Bussieck,

Many thanks for your suggestion.
As I’m not any experience in the graph colouring and I am interested in scheduling model, I’m wondering if, are there any related materials for the scheduling problems?

Regards
Omidi