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

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

1 2 3 4 next

  1. Bhardwaj, Avinash; Rostalski, Philipp; Sanyal, Raman: Deciding polyhedrality of spectrahedra (2015)
  2. Deza, Michel; Sikirić, Mathieu Dutour: Voronoi polytopes for polyhedral norms on lattices (2015)
  3. Fomeni, Franklin Djeumou; Kaparis, Konstantinos; Letchford, Adam N.: Cutting planes for RLT relaxations of mixed 0-1 polynomial programs (2015)
  4. Hampe, Simon: a-tint: a polymake extension for algorithmic tropical intersection theory (2014)
  5. Kloetzer, Marius; Mahulea, Cristian: A Petri net based approach for multi-robot path planning (2014)
  6. Avis, David; Roumanis, Gary: A portable parallel implementation of the $lrs$ vertex enumeration code (2013)
  7. Jensen, Anders; Yu, Josephine: Computing tropical resultants (2013)
  8. Joswig, Michael; Theobald, Thorsten: Polyhedral and algebraic methods in computational geometry (2013)
  9. Deza, Michel; Dutour Sikirić, Mathieu: Zigzag and central circuit structure of $(\1,2,3\, 6)$-spheres (2012)
  10. Emiris, Ioannis Z.; Fisikopoulos, Vissarion; Konaxis, Christos; Peñaranda, Luis: An output-sensitive algorithm for computing projections of resultant polytopes (2012)
  11. Ghomanjani, F.; Farahi, M.H.; Gachpazan, M.: Bézier control points method to solve constrained quadratic optimal control of time varying linear systems (2012)
  12. 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)
  13. O’Shea, Edwin; Sebö, András: Alternatives for testing total dual integrality (2012)
  14. Prodan, Ionela; Stoican, Florin; Olaru, Sorin; Niculescu, Silviu-Iulian: Enhancements on the hyperplanes arrangements in mixed-integer programming techniques (2012)
  15. Raković, Saša V.; Kouvaritakis, Basil; Findeisen, Rolf; Cannon, Mark: Homothetic tube model predictive control (2012)
  16. Steinberger, John P.: The lowest-degree polynomial with nonnegative coefficients divisible by the $n$-th cyclotomic polynomial (2012)
  17. Vanderweele, Tyler J.; Richardson, Thomas S.: General theory for interactions in sufficient cause models with dichotomous exposures (2012)
  18. Beck, Matthias; van Herick, Andrew: Enumeration of $4 \times 4$ magic squares (2011)
  19. Chan, Melody; Jensen, Anders; Rubei, Elena: The $4\times 4$ minors of a $5\times n$ matrix are a tropical basis (2011)
  20. Aguilera, Néstor E.: On packing and covering polyhedra of consecutive ones circulant clutters (2010)

1 2 3 4 next