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

Citations by Year