GCG is a generic branch-cut-and-price solver for mixed integer programs. It is based on the branch-and-cut-and-price framework SCIP and is also part of the SCIP Optimization Suite. After the standard presolving process of SCIP, GCG performs a Dantzig-Wolfe decomposition of the problem to obtain an extended formulation of the problem. The decomposition is based on a structure either provided by the user or automatically detected by one of the structure detectors included in GCG. During the solving process, GCG manages two SCIP instances, one holding the original problem, the other one representing the reformulated problem. The original instance coordinates the solving process while the other one builds the tree in the same way, transfers branching decisions and bound changes from the original problem and solves the LP relaxation of the extended formulation via column generation. GCG is developed jointly by RWTH Aachen and Zuse-Institute Berlin and has more than 50,000 lines of C code.

References in zbMATH (referenced in 25 articles )

Showing results 1 to 20 of 25.
Sorted by year (citations)

1 2 next

  1. Ceselli, Alberto; Létocart, Lucas; Traversi, Emiliano: Dantzig-Wolfe reformulations for binary quadratic problems (2022)
  2. Kim, Kibaek; Dandurand, Brian: Scalable branching on dual decomposition of stochastic mixed-integer programming problems (2022)
  3. Lübbecke, Marco E.; Maher, Stephen J.; Witt, Jonas T.: Avoiding redundant columns by adding classical Benders cuts to column generation subproblems (2021)
  4. Basso, S.; Ceselli, Alberto; Tettamanzi, Andrea: Random sampling and machine learning to understand good decompositions (2020)
  5. Deleplanque, Samuel; Labbé, Martine; Ponce, Diego; Puerto, Justo: A branch-price-and-cut procedure for the discrete ordered Median problem (2020)
  6. Fukasawa, Ricardo; Poirrier, Laurent; Yang, Shenghao: Split cuts from sparse disjunctions (2020)
  7. Gleixner, Ambros; Maher, Stephen J.; Müller, Benjamin; Pedroso, João Pedro: Price-and-verify: a new algorithm for recursive circle packing using Dantzig-Wolfe decomposition (2020)
  8. Lam, Edward; Gange, Graeme; Stuckey, Peter J.; Van Hentenryck, Pascal; Dekker, Jip J.: Nutmeg: a MIP and CP hybrid solver using branch-and-check (2020)
  9. Melchiori, Anna; Sgalambro, Antonino: A branch and price algorithm to solve the quickest multicommodity (k)-splittable flow problem (2020)
  10. Bastubbe, Michael; Lübbecke, Marco E.; Witt, Jonas T.: A computational investigation on the strength of Dantzig-Wolfe reformulations (2018)
  11. Khaniyev, Taghi; Elhedhli, Samir; Erenay, Fatih Safa: Structure detection in mixed-integer programs (2018)
  12. Kim, Kibaek; Zavala, Victor M.: Algorithmic innovations and software for the dual decomposition method applied to stochastic mixed-integer programs (2018)
  13. Arulselvan, Ashwin; Rezapour, Mohsen; Welz, Wolfgang A.: Exact approaches for designing multifacility buy-at-bulk networks (2017)
  14. Kruber, Markus; Lübbecke, Marco E.; Parmentier, Axel: Learning when to use a decomposition (2017)
  15. Abe, Masayuki; Hoshino, Fumitaka; Ohkubo, Miyako: Design in type-I, run in type-III: fast and scalable bilinear-type conversion using integer programming (2016)
  16. Bergner, Martin; Lübbecke, Marco E.; Witt, Jonas T.: A branch-price-and-cut algorithm for packing cuts in undirected graphs (2016)
  17. Lutter, Pascal: Optimized load planning for motorail transportation (2016)
  18. Zhang, Xiandong; Gong, Yeming (Yale); Zhou, Shuyu; de Koster, René; van de Velde, Steef: Increasing the revenue of self-storage warehouses by optimizing order scheduling (2016)
  19. Alfandari, Laurent; Plateau, Agnès; Schepler, Xavier: A branch-and-price-and-cut approach for sustainable crop rotation planning (2015)
  20. Bergner, Martin; Caprara, Alberto; Ceselli, Alberto; Furini, Fabio; Lübbecke, Marco E.; Malaguti, Enrico; Traversi, Emiliano: Automatic Dantzig-Wolfe reformulation of mixed integer programs (2015)

1 2 next