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 112 articles )
Showing results 1 to 20 of 112.
Sorted by year (- Ivanović, Jelena: Geometrical realisations of the simple permutoassociahedron by Minkowski sums (2020)
- Legat, Benoît; Tabuada, Paulo; Jungers, Raphaël M.: Sum-of-squares methods for controlled invariant sets with applications to model-predictive control (2020)
- Alahmadi, Adel; Deza, Michel; Dutour-Sikirić, Mathieu; Solé, Patrick: The joint weight enumerator of an LCD code and its dual (2019)
- Jensen, Anders; Ren, Yue; Schönemann, Hans: The gfanlib interface in Singular and its applications (2019)
- Röhl, Annika; Bockmayr, Alexander: Finding MEMo: minimum sets of elementary flux modes (2019)
- Vinod, Abraham P.; Gleason, Joseph D.; Oishi, Meeko M. K.: Demo abstract: SReachTools: a MATLAB stochastic reachability toolbox. (2019)
- Vinod, Abraham P.; Gleason, Joseph D.; Oishi, Meeko M. K.: SReachTools: a MATLAB stochastic reachability toolbox (2019)
- 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)
- Studený, Milan; Kratochvíl, Václav: Linear criterion for testing the extremity of an exact game based on its finest min-representation (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 \textttpolymake (2017)
- Cussens, James; Järvisalo, Matti; Korhonen, Janne H.; Bartlett, Mark: Bayesian network structure learning with integer programming: polytopes, facets and complexity (2017)
- Epure, Raul; Ren, Yue; Schönemann, Hans: The polymake interface in Singular and its applications (2017)
- Fagundes, Gabriel; Kleinmann, Matthias: Memory cost for simulating all quantum correlations from the Peres-Mermin scenario (2017)
- Iervolino, Raffaele; Tangredi, Domenico; Vasca, Francesco: Lyapunov stability for piecewise affine systems via cone-copositivity (2017)
- Kastner, Lars: Toric Ext and Tor in \textttpolymakeand \textbfSingular: the two-dimensional case and beyond (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)