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.
This software is also referenced in ORMS.
Keywords for this software
References in zbMATH (referenced in 96 articles )
Showing results 1 to 20 of 96.
Sorted by year (- Jordan, Charles; Joswig, Michael; Kastner, Lars: Parallel enumeration of triangulations (2018)
- Lee, Jon; Skipper, Daphne: Computing with an algebraic-perturbation variant of Barvinok’s algorithm (2018)
- Aguilera, Néstor E.; Katz, Ricardo D.; Tolomei, Paola B.: Vertex adjacencies in the set covering polyhedron (2017)
- Assarf, Benjamin; Gawrilow, Ewgenij; Herr, Katrin; Joswig, Michael; Lorenz, Benjamin; Paffenholz, Andreas; Rehn, Thomas: Computing convex hulls and counting integer points with polymake (2017)
- Cussens, James; Järvisalo, Matti; Korhonen, Janne H.; Bartlett, Mark: Bayesian network structure learning with integer programming: polytopes, facets and complexity (2017)
- Iervolino, Raffaele; Tangredi, Domenico; Vasca, Francesco: Lyapunov stability for piecewise affine systems via cone-copositivity (2017)
- Studený, Milan; Cussens, James: Towards using the chordal graph polytope in learning decomposable models (2017)
- Toth, Csaba D. (ed.); Goodman, Jacob E. (ed.); O’Rourke, Joseph (ed.): Handbook of discrete and computational geometry (2017)
- Akartunalı, Kerem; Fragkos, Ioannis; Miller, Andrew J.; Wu, Tao: Local cuts and two-period convex hull closures for big-bucket lot-sizing problems (2016)
- Jensen, Anders; Leykin, Anton; Yu, Josephine: Computing tropical curves via homotopy continuation (2016)
- Bhardwaj, Avinash; Rostalski, Philipp; Sanyal, Raman: Deciding polyhedrality of spectrahedra (2015)
- Deza, Michel; Dutour Sikirić, Mathieu: Voronoi polytopes for polyhedral norms on lattices (2015)
- Fomeni, Franklin Djeumou; Kaparis, Konstantinos; Letchford, Adam N.: Cutting planes for RLT relaxations of mixed 0-1 polynomial programs (2015)
- Hampe, Simon: a-tint: a polymake extension for algorithmic tropical intersection theory (2014)
- Kloetzer, Marius; Mahulea, Cristian: A Petri net based approach for multi-robot path planning (2014)
- Avis, David; Roumanis, Gary: A portable parallel implementation of the $lrs$ vertex enumeration code (2013)
- Jensen, Anders; Yu, Josephine: Computing tropical resultants (2013)
- Joswig, Michael; Theobald, Thorsten: Polyhedral and algebraic methods in computational geometry (2013)
- Deza, Michel; Dutour Sikirić, Mathieu: Zigzag and central circuit structure of $(\1,2,3\, 6)$-spheres (2012)
- Emiris, Ioannis Z.; Fisikopoulos, Vissarion; Konaxis, Christos; Peñaranda, Luis: An output-sensitive algorithm for computing projections of resultant polytopes (2012)