cdd

The program cdd+ (cdd, respectively) is a C++ (ANSI C) implementation of the Double Description Method [MRTT53] for generating all vertices (i.e. extreme points) and extreme rays of a general convex polyhedron given by a system of linear inequalities: P = {x c R^d : Ax <= b } where is an real matrix and is a real dimensional vector. See, [FP96] for an efficient implementation of the double description method which is employed in cdd+. One useful feature of cdd/cdd+ is its capability of handling the dual (reverse) problem without any transformation of data. The dual problem is known to be the (convex) hull problem which is to obtain a linear inequality representation of a convex polyhedron given as the Minkowski sum of the convex hull of a finite set of points and the nonnegative hull of a finite set of points in : , where the Minkowski sum of two subsets and of is defined as . As we see in this manual, the computation can be done in straightforward manner. There is one assumption for the input for hull computation: the polyhedron must be full-dimensional. Besides these basic functions, cdd/cdd+ can solve the general linear programming (LP) problem to maximize (or minimize) a linear function over polyhedron . It is useful mainly for solving dense LP’s with large (say, up to few hundred thousands) and small (say, up to 100).

This software is also referenced in ORMS.


References in zbMATH (referenced in 119 articles )

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

1 2 3 4 5 6 next

  1. Pfetsch, Marc E.; Rinaldi, Giovanni; Ventura, Paolo: Optimal patchings for consecutive ones matrices (2022)
  2. Toffano, Federico; Garraffa, Michele; Lin, Yiqing; Prestwich, Steven; Simonis, Helmut; Wilson, Nic: A multi-objective supplier selection framework based on user-preferences (2022)
  3. Bruno, A. D.; Batkhin, A. B.: Algorithms and programs for calculating the roots of polynomial of one or two variables (2021)
  4. Bruns, Winfried; Ichim, Bogdan: Polytope volume by descent in the face lattice and applications in social choice (2021)
  5. Svozil, Karl: Quantum violation of the suppes-zanotti inequalities and “contextuality” (2021)
  6. Bennett, Magdalena; Vielma, Juan Pablo; Zubizarreta, José R.: Building representative matched samples with multi-valued treatments in large observational studies (2020)
  7. Ivanović, Jelena: Geometrical realisations of the simple permutoassociahedron by Minkowski sums (2020)
  8. Legat, Benoît; Tabuada, Paulo; Jungers, Raphaël M.: Sum-of-squares methods for controlled invariant sets with applications to model-predictive control (2020)
  9. Alahmadi, Adel; Deza, Michel; Dutour-Sikirić, Mathieu; Solé, Patrick: The joint weight enumerator of an LCD code and its dual (2019)
  10. Jensen, Anders; Ren, Yue; Schönemann, Hans: The gfanlib interface in Singular and its applications (2019)
  11. Röhl, Annika; Bockmayr, Alexander: Finding MEMo: minimum sets of elementary flux modes (2019)
  12. Vinod, Abraham P.; Gleason, Joseph D.; Oishi, Meeko M. K.: Demo abstract: SReachTools: a MATLAB stochastic reachability toolbox. (2019)
  13. Vinod, Abraham P.; Gleason, Joseph D.; Oishi, Meeko M. K.: SReachTools: a MATLAB stochastic reachability toolbox (2019)
  14. Jordan, Charles; Joswig, Michael; Kastner, Lars: Parallel enumeration of triangulations (2018)
  15. Lee, Jon; Skipper, Daphne: Computing with an algebraic-perturbation variant of Barvinok’s algorithm (2018)
  16. Studený, Milan; Kratochvíl, Václav: Linear criterion for testing the extremity of an exact game based on its finest min-representation (2018)
  17. Aguilera, Néstor E.; Katz, Ricardo D.; Tolomei, Paola B.: Vertex adjacencies in the set covering polyhedron (2017)
  18. Assarf, Benjamin; Gawrilow, Ewgenij; Herr, Katrin; Joswig, Michael; Lorenz, Benjamin; Paffenholz, Andreas; Rehn, Thomas: Computing convex hulls and counting integer points with \textttpolymake (2017)
  19. Cussens, James; Järvisalo, Matti; Korhonen, Janne H.; Bartlett, Mark: Bayesian network structure learning with integer programming: polytopes, facets and complexity (2017)
  20. Epure, Raul; Ren, Yue; Schönemann, Hans: The polymake interface in Singular and its applications (2017)

1 2 3 4 5 6 next