## cdd

 swMATH ID: 114 Software Authors: Komei Fukuda Description: 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). Homepage: http://www.inf.ethz.ch/personal/fukudak/cdd_home/ Programming Languages: C++ Keywords: orms; orms; cddplus Related Software: polymake; Gfan; PORTA; lrs; cddplus; gmp; Matlab; LattE; CPLEX; Normaliz; 4ti2; TOPCOM; nauty; MPT; CGAL; SoPlex; SeDuMi; ZRAM; Qhull; SCIP Cited in: 119 Publications This software is also referenced in ORMS.
all top 5

### Cited by 226 Authors

 8 Dutour-Sikiric, Mathieu 7 Bemporad, Alberto 7 Deza, Michel Marie 7 Jensen, Anders Nedergaard 6 Morari, Manfred 5 Joswig, Michael 4 Avis, David M. 4 Fukuda, Komei 3 Filippi, Carlo 3 Schürmann, Achill 3 Studený, Milan 3 Torrisi, Fabio Danilo 3 Vallentin, Frank 3 Yoshida, Ruriko 2 Aguilera, Néstor E. 2 Borrelli, Francesco 2 Cussens, James 2 De Loera, Jesús A. 2 Deza, Antoine 2 Deza, Elena Ivanovna 2 Dua, Vivek 2 Emiris, Ioannis Z. 2 Gleason, Joseph D. 2 Hemmecke, Raymond 2 Kastner, Lars 2 Kojima, Masakazu 2 Lee, Jon 2 Mélot, Hadrien 2 Oishi, Meeko M. K. 2 Olaru, Sorin 2 Paffenholz, Andreas 2 Pistikopoulos, Efstratios N. 2 Ren, Yue 2 Schönemann, Hans 2 Speyer, David E. 2 Thomas, Rekha R. 2 Vinod, Abraham P. 2 Yu, Josephine 1 Adrovic, Danko 1 Akartunalı, Kerem 1 Alahmadi, Adel N. 1 Alur, Rajeev 1 Andersen, Kasper K. S. 1 Assarf, Benjamin 1 Baotić, Mato 1 Bartlett, Mark 1 Batkhin, Alexandr B. 1 Bauer, Tilman 1 Baumeler, Ämin 1 Beck, Matthias 1 Bennett, Magdalena 1 Bhardwaj, Avinash 1 Bockmayr, Alexander 1 Bogart, Tristram 1 Bóna, Miklós 1 Boocher, Adam 1 Bremner, David 1 Bruno, Alexander Dmitrievich 1 Bruns, Winfried 1 Cafieri, Sonia 1 Cannon, Mark 1 Chan, Melody 1 Choi, Jin Young 1 Christof, Thomas 1 Christophe, Julie 1 Christophersen, Frank J. 1 Cinquemani, Eugenio 1 Dang, Thao 1 de Cooman, Gert 1 Devroye, Luc P. J. A. 1 Dewez, Sophie 1 Dimitriou, V. A. 1 Doignon, Jean-Paul 1 Elloumi, Sourour 1 Epure, Raul 1 Evdokimov, Sergeĭ Alekseevich 1 Fagundes, Gabriel 1 Fallat, Shaun M. 1 Farahi, Mohammad Hadi 1 Fasbender, Gilles 1 Feller, Christian 1 Ferrari-Trecate, Giancarlo 1 Ferrez, J.-A. 1 Findeisen, Rolf 1 Fisikopoulos, Vissarion 1 Fomeni, Franklin Djeumou 1 Fragkos, Ioannis 1 Froehle, Bradley 1 Fujie, Tetsuya 1 Fukuda, Mituhiro 1 Garraffa, Michele 1 Gawrilow, Ewgenij 1 Gekhtman, Mikhaèl I. 1 Geyer, Charles J. 1 Geyer, Tobias 1 Ghomanjani, Fateme 1 Giorgetti, Nicolò 1 Goodman, Jacob Eli 1 Gotoh, Jun-ya 1 Grégoire, Philippe ...and 126 more Authors
all top 5

### Cited in 62 Serials

 8 Discrete Applied Mathematics 7 Automatica 4 Mathematics of Computation 4 Journal of Symbolic Computation 3 Journal of Optimization Theory and Applications 3 International Journal of Approximate Reasoning 3 Computational Geometry 3 European Journal of Operational Research 3 Mathematical Programming. Series A. Series B 3 Mathematical Programming Computation 2 Discrete Mathematics 2 Journal of Algebra 2 Networks 2 European Journal of Combinatorics 2 Discrete & Computational Geometry 2 Annals of Operations Research 2 Journal of Global Optimization 2 Linear Algebra and its Applications 2 Experimental Mathematics 2 The Electronic Journal of Combinatorics 2 Lecture Notes in Control and Information Sciences 1 Computer Physics Communications 1 International Journal of Theoretical Physics 1 Information Processing Letters 1 Israel Journal of Mathematics 1 Journal of Mathematical Biology 1 The Annals of Statistics 1 Applied Mathematics and Computation 1 Fuzzy Sets and Systems 1 IEEE Transactions on Automatic Control 1 Inventiones Mathematicae 1 Programming and Computer Software 1 Theoretical Computer Science 1 Advances in Applied Mathematics 1 Operations Research Letters 1 American Journal of Mathematical and Management Sciences 1 Physica D 1 Discrete Event Dynamic Systems 1 International Journal of Robust and Nonlinear Control 1 SIAM Journal on Optimization 1 Journal of Algebraic Combinatorics 1 Computational Optimization and Applications 1 SIAM Journal on Scientific Computing 1 Computational and Applied Mathematics 1 Nordic Journal of Computing 1 Top 1 The Journal of Artificial Intelligence Research (JAIR) 1 Electronic Research Announcements of the American Mathematical Society 1 INFORMS Journal on Computing 1 Taiwanese Journal of Mathematics 1 Mathematical Methods of Operations Research 1 New Journal of Physics 1 Discrete Optimization 1 Optimization Letters 1 Journal of Physics A: Mathematical and Theoretical 1 Applicable Analysis and Discrete Mathematics 1 Nonlinear Analysis. Hybrid Systems 1 Electronic Journal of Statistics 1 Journal of Computational and Graphical Statistics 1 The Journal of Software for Algebra and Geometry 1 Universitext 1 Discrete Mathematics and its Applications
all top 5

### Cited in 25 Fields

 37 Operations research, mathematical programming (90-XX) 36 Convex and discrete geometry (52-XX) 33 Computer science (68-XX) 19 Combinatorics (05-XX) 18 Systems theory; control (93-XX) 16 Algebraic geometry (14-XX) 11 Numerical analysis (65-XX) 9 Commutative algebra (13-XX) 6 Number theory (11-XX) 6 Calculus of variations and optimal control; optimization (49-XX) 6 Statistics (62-XX) 4 Linear and multilinear algebra; matrix theory (15-XX) 3 Group theory and generalizations (20-XX) 3 Quantum theory (81-XX) 3 Game theory, economics, finance, and other social and behavioral sciences (91-XX) 2 Field theory and polynomials (12-XX) 2 Probability theory and stochastic processes (60-XX) 2 Information and communication theory, circuits (94-XX) 1 Order, lattices, ordered algebraic structures (06-XX) 1 Associative rings and algebras (16-XX) 1 Partial differential equations (35-XX) 1 Geometry (51-XX) 1 Algebraic topology (55-XX) 1 Manifolds and cell complexes (57-XX) 1 Biology and other natural sciences (92-XX)