DIP

DIP (Decomposition for Integer Programming) is an open-source extensible software framework for implementing decomposition-based bounding algorithms for use in solving large-scale discrete optimization problems. The framework provides a simple API for experimenting with various decomposition-based algorithms, such as Dantzig-Wolfe decomposition, Lagrangian relaxation, and various cutting plane methods. Given a compact formulation and a relaxation, the framework takes care of all algorithmic details associated with implementing any of a wide range of decomposition-based algorithms, such as branch and cut, branch and price, branch and cut and price, subgradient-based Lagrangian relaxation, branch and relax and cut, and decompose and cut. The user can specify customizations, such as methods for generating valid inequalities and branching, in terms of the variables of the compact formulation, without having to worry about the details of any required reformulations. DIP is used in combination with ​CHiPPS, which provides the underlying tree search methodology. DIP does not currently have extensive documentation, but the design and implementation of DIP are described in more detail in Chapter 4 of the doctoral dissertation of Matthew Galati (linked below) and the thoery behind DIP is described in both of the following below links. M. Galati, ​Decomposition in Integer Linear Programming, Doctoral Dissertation, Lehigh University, December 2009. T.K. Ralphs and M. Galati, ​Decomposition in Integer Programming, in ​Integer Programming: Theory and Practice, John Karlof, ed. (2005), 57-110.


References in zbMATH (referenced in 18 articles )

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

  1. Basso, S.; Ceselli, Alberto; Tettamanzi, Andrea: Random sampling and machine learning to understand good decompositions (2020)
  2. Fischer, Tobias; Pfetsch, Marc E.: On the structure of linear programs with overlapping cardinality constraints (2020)
  3. 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)
  4. Muts, Pavlo; Nowak, Ivo; Hendrix, Eligius M. T.: The decomposition-based outer approximation algorithm for convex mixed-integer nonlinear programming (2020)
  5. Hertz, Alain; Montagné, Romain; Gagnon, François: A comparison of integer programming models for the partial directed weighted improper coloring problem (2019)
  6. Nowak, Ivo; Muts, Pavlo; Hendrix, Eligius M. T.: Multi-tree decomposition methods for large-scale mixed integer nonlinear optimization (2019)
  7. Khaniyev, Taghi; Elhedhli, Samir; Erenay, Fatih Safa: Structure detection in mixed-integer programs (2018)
  8. Kim, Kibaek; Zavala, Victor M.: Algorithmic innovations and software for the dual decomposition method applied to stochastic mixed-integer programs (2018)
  9. Nowak, Ivo; Breitfeld, Norman; Hendrix, Eligius M. T.; Njacheun-Njanzoua, Grégoire: Decomposition-based inner- and outer-refinement algorithms for global optimization (2018)
  10. 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)
  11. Plum, Christian E. M.; Pisinger, David; Salazar-González, Juan-José; Sigurd, Mikkel M.: Single liner shipping service design (2014)
  12. Wang, Jiadong; Ralphs, Ted: Computational experience with hypergraph-based methods for automatic decomposition in discrete optimization (2013)
  13. Bergner, Martin; Caprara, Alberto; Furini, Fabio; Lübbecke, Marco E.; Malaguti, Enrico; Traversi, Emiliano: Partial convexification of general mips by Dantzig-Wolfe reformulation (2011)
  14. Nishi, Tatsushi; Hiranaka, Yuichiro; Grossmann, Ignacio E.: A bilevel decomposition algorithm for simultaneous production scheduling and conflict-free routing for automated guided vehicles (2011)
  15. Burke, Edmund K.; Mareček, Jakub; Parkes, Andrew J.; Rudová, Hana: Decomposition, reformulation, and diving in university course timetabling (2010)
  16. Ralphs, Ted K.; Galati, Matthew V.: Decomposition in integer linear programming (2006)
  17. Ralphs, Ted K.; Galati, Matthew V.: Decomposition and dynamic cut generation in integer linear programming (2006)
  18. Lucena, Abilio: Non delayed relax-and-cut algorithms (2005)