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 85 articles )

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

1 2 3 4 5 next

  1. Assarf, Benjamin; Gawrilow, Ewgenij; Herr, Katrin; Joswig, Michael; Lorenz, Benjamin; Paffenholz, Andreas; Rehn, Thomas: Computing convex hulls and counting integer points with polymake (2017)
  2. Cussens, James; Järvisalo, Matti; Korhonen, Janne H.; Bartlett, Mark: Bayesian network structure learning with integer programming: polytopes, facets and complexity (2017)
  3. Iervolino, Raffaele; Tangredi, Domenico; Vasca, Francesco: Lyapunov stability for piecewise affine systems via cone-copositivity (2017)
  4. Toth, Csaba D. (ed.); Goodman, Jacob E. (ed.); O’Rourke, Joseph (ed.): Handbook of discrete and computational geometry (2017)
  5. Akartunalı, Kerem; Fragkos, Ioannis; Miller, Andrew J.; Wu, Tao: Local cuts and two-period convex hull closures for big-bucket lot-sizing problems (2016)
  6. Bhardwaj, Avinash; Rostalski, Philipp; Sanyal, Raman: Deciding polyhedrality of spectrahedra (2015)
  7. Deza, Michel; Sikirić, Mathieu Dutour: Voronoi polytopes for polyhedral norms on lattices (2015)
  8. Fomeni, Franklin Djeumou; Kaparis, Konstantinos; Letchford, Adam N.: Cutting planes for RLT relaxations of mixed 0-1 polynomial programs (2015)
  9. Hampe, Simon: a-tint: a polymake extension for algorithmic tropical intersection theory (2014)
  10. Kloetzer, Marius; Mahulea, Cristian: A Petri net based approach for multi-robot path planning (2014)
  11. Avis, David; Roumanis, Gary: A portable parallel implementation of the $lrs$ vertex enumeration code (2013)
  12. Jensen, Anders; Yu, Josephine: Computing tropical resultants (2013)
  13. Joswig, Michael; Theobald, Thorsten: Polyhedral and algebraic methods in computational geometry (2013)
  14. Deza, Michel; Dutour Sikirić, Mathieu: Zigzag and central circuit structure of $(\1,2,3\, 6)$-spheres (2012)
  15. Emiris, Ioannis Z.; Fisikopoulos, Vissarion; Konaxis, Christos; Peñaranda, Luis: An output-sensitive algorithm for computing projections of resultant polytopes (2012)
  16. Ghomanjani, F.; Farahi, M.H.; Gachpazan, M.: Bézier control points method to solve constrained quadratic optimal control of time varying linear systems (2012)
  17. Kéri, Gerzson; Szántai, Tamás: Combinatorial results on the fitting problems of the multivariate gamma distribution introduced by Prékopa and Szántai (2012)
  18. O’Shea, Edwin; Sebö, András: Alternatives for testing total dual integrality (2012)
  19. Prodan, Ionela; Stoican, Florin; Olaru, Sorin; Niculescu, Silviu-Iulian: Enhancements on the hyperplanes arrangements in mixed-integer programming techniques (2012)
  20. Raković, Saša V.; Kouvaritakis, Basil; Findeisen, Rolf; Cannon, Mark: Homothetic tube model predictive control (2012)

1 2 3 4 5 next