{"diffoscope-json-version": 1, "source1": "/srv/reproducible-results/rbuild-debian/r-b-build.ceWbIh0w/b1/cddlib_094m-1.1_arm64.changes", "source2": "/srv/reproducible-results/rbuild-debian/r-b-build.ceWbIh0w/b2/cddlib_094m-1.1_arm64.changes", "unified_diff": null, "details": [{"source1": "Files", "source2": "Files", "unified_diff": "@@ -1,7 +1,7 @@\n \n  d9f4b886079d3d22fd430bb214ce32cc 18516 libdevel optional libcdd-dev_094m-1.1_arm64.deb\n- 887ee058b9961fd0189839cf1aa4f813 254988 doc optional libcdd-doc_094m-1.1_all.deb\n+ afe0701dbb62b50e058d2d52fc17eb87 252748 doc optional libcdd-doc_094m-1.1_all.deb\n  3f52c8b8d27ab23e6dce4cf97fa5df49 120064 debug optional libcdd-tools-dbgsym_094m-1.1_arm64.deb\n  466daaa22b890ae24e6cc033f93345c4 30536 math optional libcdd-tools_094m-1.1_arm64.deb\n  7bf5d7cf9da7f9d27b7012a71b05b2d2 384048 debug optional libcdd0t64-dbgsym_094m-1.1_arm64.deb\n  fad7615174f79ca4cf2f6ab49fa28120 96428 libs optional libcdd0t64_094m-1.1_arm64.deb\n"}, {"source1": "libcdd-doc_094m-1.1_all.deb", "source2": "libcdd-doc_094m-1.1_all.deb", "unified_diff": null, "details": [{"source1": "file list", "source2": "file list", "unified_diff": "@@ -1,3 +1,3 @@\n -rw-r--r--   0        0        0        4 2024-02-28 05:59:09.000000 debian-binary\n--rw-r--r--   0        0        0      840 2024-02-28 05:59:09.000000 control.tar.xz\n--rw-r--r--   0        0        0   253956 2024-02-28 05:59:09.000000 data.tar.xz\n+-rw-r--r--   0        0        0      836 2024-02-28 05:59:09.000000 control.tar.xz\n+-rw-r--r--   0        0        0   251720 2024-02-28 05:59:09.000000 data.tar.xz\n"}, {"source1": "control.tar.xz", "source2": "control.tar.xz", "unified_diff": null, "details": [{"source1": "control.tar", "source2": "control.tar", "unified_diff": null, "details": [{"source1": "./control", "source2": "./control", "unified_diff": "@@ -1,13 +1,13 @@\n Package: libcdd-doc\n Source: cddlib\n Version: 094m-1.1\n Architecture: all\n Maintainer: Debian Math Team <team+math@tracker.debian.org>\n-Installed-Size: 258\n+Installed-Size: 256\n Breaks: libcdd-dev (<< 094g-3)\n Replaces: libcdd-dev (<< 094g-3)\n Section: doc\n Priority: optional\n Multi-Arch: foreign\n Homepage: https://github.com/cddlib/cddlib\n Description: documentation for libcdd\n"}, {"source1": "./md5sums", "source2": "./md5sums", "unified_diff": null, "details": [{"source1": "./md5sums", "source2": "./md5sums", "comments": ["Files differ"], "unified_diff": null}]}]}]}, {"source1": "data.tar.xz", "source2": "data.tar.xz", "unified_diff": null, "details": [{"source1": "data.tar", "source2": "data.tar", "unified_diff": null, "details": [{"source1": "file list", "source2": "file list", "unified_diff": "@@ -1,12 +1,12 @@\n drwxr-xr-x   0 root         (0) root         (0)        0 2024-02-28 05:59:09.000000 ./\n drwxr-xr-x   0 root         (0) root         (0)        0 2024-02-28 05:59:09.000000 ./usr/\n drwxr-xr-x   0 root         (0) root         (0)        0 2024-02-28 05:59:09.000000 ./usr/share/\n drwxr-xr-x   0 root         (0) root         (0)        0 2024-02-28 05:59:09.000000 ./usr/share/doc/\n drwxr-xr-x   0 root         (0) root         (0)        0 2024-02-28 05:59:09.000000 ./usr/share/doc/libcdd-dev/\n--rw-r--r--   0 root         (0) root         (0)   245728 2024-02-28 05:59:09.000000 ./usr/share/doc/libcdd-dev/cddlibman.pdf.gz\n+-rw-r--r--   0 root         (0) root         (0)   243473 2024-02-28 05:59:09.000000 ./usr/share/doc/libcdd-dev/cddlibman.pdf.gz\n drwxr-xr-x   0 root         (0) root         (0)        0 2024-02-28 05:59:09.000000 ./usr/share/doc/libcdd-doc/\n -rw-r--r--   0 root         (0) root         (0)      572 2024-02-28 05:59:09.000000 ./usr/share/doc/libcdd-doc/changelog.Debian.gz\n -rw-r--r--   0 root         (0) root         (0)     5059 2020-12-08 14:43:12.000000 ./usr/share/doc/libcdd-doc/changelog.gz\n -rw-r--r--   0 root         (0) root         (0)     1209 2018-09-29 19:12:01.000000 ./usr/share/doc/libcdd-doc/copyright\n drwxr-xr-x   0 root         (0) root         (0)        0 2024-02-28 05:59:09.000000 ./usr/share/doc-base/\n -rw-r--r--   0 root         (0) root         (0)     1173 2018-09-29 19:40:06.000000 ./usr/share/doc-base/libcdd-doc.cddlibman\n"}, {"source1": "./usr/share/doc/libcdd-dev/cddlibman.pdf.gz", "source2": "./usr/share/doc/libcdd-dev/cddlibman.pdf.gz", "unified_diff": null, "details": [{"source1": "cddlibman.pdf", "source2": "cddlibman.pdf", "unified_diff": null, "details": [{"source1": "pdftotext {} -", "source2": "pdftotext {} -", "unified_diff": "@@ -2,110 +2,48 @@\n Komei Fukuda\n Institute for Operations Research\n and Institute of Theoretical Computer Science\n ETH Zentrum, CH-8092 Zurich, Switzerland\n (cddlib ver. 0.94, manual ver. February 7, 2008)\n \n Contents\n-1 Introduction\n-\n-1\n-\n-2 Polyhedra H- and V-Formats (Version 1999)\n-\n-2\n-\n-3 Basic Object Types (Structures) in cddlib\n-\n-4\n-\n-4 Library Functions\n-4.1 Library Initialization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .\n-4.2 Core Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .\n-4.3 Data Manipulations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .\n-4.3.1 Number Assignments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .\n-4.3.2 Arithmetic Operations for mytype Numbers . . . . . . . . . . . . . . . . . . .\n-4.3.3 Predefined Constants . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .\n-4.3.4 Sign Evaluation and Comparison for mytype Numbers . . . . . . . . . . . . .\n-4.3.5 Polyhedra Data Manipulation . . . . . . . . . . . . . . . . . . . . . . . . . . .\n-4.3.6 LP Data Manipulation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .\n-4.3.7 Matrix Manipulation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .\n-4.4 Input/Output Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .\n-4.5 Obsolete Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .\n-4.6 Set Functions in setoper library . . . . . . . . . . . . . . . . . . . . . . . . . . . . .\n-\n-6\n-7\n-7\n-10\n-10\n-11\n-11\n-12\n-12\n-13\n-13\n-14\n-14\n-15\n-\n-5 An Extension of the CDD Library in GMP mode\n-\n-15\n-\n-6 Examples\n-\n-15\n-\n-7 Numerical Accuracy\n-\n-16\n-\n-8 Other Useful Codes\n-\n-16\n-\n-9 Codes Using Cddlib\n-\n-17\n Abstract\n-\n This is a reference manual for cddlib-094. The manual describes the library functions and\n data types implemented in the cddlib C-library which is to perform fundamental polyhedral\n computations such as representation conversions and linear programming in both floating-point\n-\n-1\n-\n-\fand GMP rational exact arithmetic. Please read the accompanying README file and test\n+and GMP rational exact arithmetic. Please read the accompanying README file and test\n programs to complement the manual.\n The new functions added in this version include dd MatrixCanonicalize to find a nonredundant proper H- or V-representation, dd FindRelativeInterior to find a relative interior\n point of an H-polyhedron, and dd ExistsRestrictedFace (Farkas-type alternative theorem\n verifier) to check the existence of a point satisfying a specified system of linear inequalities\n possibly including multiple strict inequalities.\n The new functions are particularly important for the development of related software packages MinkSum (by Ch. Weibel) and Gfan (by Anders Jensen),\n \n 1\n \n Introduction\n \n-The program cddlib is an efficient implementation [16] of the double description Method [19] for\n+The program cddlib is an efficient implementation [?] of the double description Method [?] for\n generating all vertices (i.e. extreme points) and extreme rays of a general convex polyhedron given\n by a system of linear inequalities:\n P = {x = (x1 , x2 , . . . , xd )T \u2208 Rd : b \u2212 Ax \u2265 0}\n where A is a given m \u00d7 d real matrix and b is a given real m-vector. In the mathematical language, the computation is the transformation of an H-representation of a convex polytope to an\n V-representation.\n cddlib is a C-library version of the previously released C-code cdd/cdd+. In order to make\n this library version, a large part of the cdd source (Version 0.61) has been rewritten. This library\n version is more flexible since it can be called from other programs in C/C++. Unlike cdd/cdd+,\n cddlib can handle any general input and is more general. Furthermore, additional functions have\n been written to extend its functionality.\n One useful feature of cddlib/cdd/cdd+ is its capability of handling the dual (reverse) problem\n without any transformation of data. The dual transformation problem of a V-representation to\n a minimal H-representation and is often called the (convex) hull problem. More explicitly, is to\n-obtain a linear inequality representation of a convex polyhedron given as the Minkowski sum of the\n+\n+1\n+\n+\fobtain a linear inequality representation of a convex polyhedron given as the Minkowski sum of the\n convex hull of a finite set of points and the nonnegative hull of a finite set of points in Rd :\n P = conv(v1 , . . . , vn ) + nonneg(rn+1 , . . . , rn+s ),\n where the Minkowski sum of two subsets S and T of Rd is defined as\n S + T = {s + t |s \u2208 S and t \u2208 T }.\n As we see in this manual, the computation can be done in straightforward manner. Unlike the\n earlier versions of cdd/cdd+ that assume certain regularity conditions for input, cddlib is designed\n to do a correct transformation for any general input. The user must be aware of the fact that\n@@ -113,27 +51,25 @@\n representations. For example, a line segment (1-dimensional polytope) in R3 has infinitely many\n minimal H-representations, and a halfspace in the same space has infinitely many minimal Vrepresentations. cddlib generates merely one minimal representation.\n cddlib comes with an LP code to solve the general linear programming (LP) problem to maximize (or minimize) a linear function over polyhedron P . It is useful mainly for solving dense LP\u2019s\n with large m (say, up to few hundred thousands) and small d (say, up to 100). It implements a\n revised dual simplex method that updates (d + 1) \u00d7 (d + 1) matrix for a pivot operation.\n The program cddlib has an I/O routines that read and write files in Polyhedra format which\n was defined by David Avis and the author in 1993, and has been updated in 1997 and 1999. The\n-2\n-\n-\fprogram called lrs and lrslib [2] developed by David Avis is a C-implementation of the reverse\n-search algorithm [4] for the same enumeration purpose, and it conforms to Polyhedra format as\n+program called lrs and lrslib [?] developed by David Avis is a C-implementation of the reverse\n+search algorithm [?] for the same enumeration purpose, and it conforms to Polyhedra format as\n well. Hopefully, this compatibility of the two programs enables users to use both programs for the\n same input files and to choose whichever is useful for their purposes. From our experiences with\n relatively large problems, the two methods are both useful and perhaps complementary to each\n other. In general, the program cddlib tends to be efficient for highly degenerate inputs and the\n program rs tends to be efficient for nondegenerate or slightly degenerate problems.\n Although the program can be used for nondegenerate inputs, it might not be very efficient.\n For nondegenerate inputs, other available programs, such as the reverse search code lrs or qhull\n-(developed by the Geometry Center), might be more efficient. See Section 8 for pointers to these\n-codes. The paper [3] contains many interesting results on polyhedral computation and experimental\n+(developed by the Geometry Center), might be more efficient. See Section ?? for pointers to these\n+codes. The paper [?] contains many interesting results on polyhedral computation and experimental\n results on cdd+, lrs, qhull and porta.\n This program can be distributed freely under the GNU GENERAL PUBLIC LICENSE. Please\n read the file COPYING carefully before using.\n I will not take any responsibility of any problems you might have with this program. But I will\n be glad to receive bug reports or suggestions at the e-mail addresses above. If cddlib turns out\n to be useful, please kindly inform me of what purposes cdd has been used for. I will be happy to\n include a list of applications in future distribution if I receive enough replies. The most powerful\n@@ -144,15 +80,17 @@\n Polyhedra H- and V-Formats (Version 1999)\n \n Every convex polyhedron has two representations, one as the intersection of finite halfspaces and\n the other as Minkowski sum of the convex hull of finite points and the nonnegative hull of finite\n directions. These are called H-representation and V-representation, respectively.\n Naturally there are two basic Polyhedra formats, H-format for H-representation and V-format\n for V-representation. These two formats are designed to be almost indistinguishable, and in fact,\n-one can almost pretend one for the other. There is some asymmetry arising from the asymmetry\n+2\n+\n+\fone can almost pretend one for the other. There is some asymmetry arising from the asymmetry\n of two representations.\n First we start with the H-representation. Let A be an m \u00d7 d matrix, and let b be a column\n m-vector. The Polyhedra format (H-format ) of the system b \u2212 Ax \u2265 0 of m inequalities in d\n variables x = (x1 , x2 , . . . , xd )T is\n various comments\n H-representation\n (linearity t i1 i2 . . . it )\n@@ -164,17 +102,15 @@\n various options\n where numbertype can be one of integer, rational or real. When rational type is selected, each\n component of b and A can be specified by the usual integer expression or by the rational expression\n \u201cp/q\u201d or \u201c\u2212p/q\u201d where p and q are arbitrary long positive integers (see the example input file\n rational.ine). In the 1997 format, we introduced \u201cH-representation\u201d which must appear before\n \u201cbegin\u201d. There was one restriction in the old polyhedra format (before 1997): the last d rows must\n determine a vertex of P . This is obsolete now.\n-3\n-\n-\fIn the new 1999 format, we added the possibility of specifying linearity. This means that for\n+In the new 1999 format, we added the possibility of specifying linearity. This means that for\n H-representation, some of the input rows can be specified as equalities: bij \u2212 Aij x = 0 for all\n j = 1, 2, . . . , t. The linearity line may be omitted if there are no equalities.\n Option lines can be used to control computation of a specific program. In particular both cdd\n and lrs use the option lines to represent a linear objective function. See the attached LP files,\n samplelp*.ine.\n Next we define Polyhedra V-format. Let P be represented by n generating points and s generating directions (rays) as P = conv(v1 , . . . , vn ) + nonneg(rn+1 , . . . , rn+s ). Then the Polyhedra\n V-format for P is\n@@ -201,15 +137,17 @@\n \n 0\n rn+s\n end\n various options\n Here we do not require that vertices and rays are listed separately; they can appear mixed in\n arbitrary order.\n-Linearity for V-representation specifies a subset of generators whose coefficients are relaxed to\n+3\n+\n+\fLinearity for V-representation specifies a subset of generators whose coefficients are relaxed to\n be free: for all j = 1, 2, . . . , t, the k = ij th generator (vk or rk whichever is the ij th generator) is\n a free generator. This means for each such a ray rk , the line generated by rk is in the polyhedron,\n and for each such a vertex vk , its coefficient is no longer nonnegative but still the coefficients for all\n vi \u2019s must sum up to one. It is highly unlikely that one needs to use linearity for vertex generators,\n and it is defined mostly for formality.\n When the representation statement, either \u201cH-representation\u201d or \u201cV-representation\u201d, is omitted, the former \u201cH-representation\u201d is assumed.\n It is strongly suggested to use the following rule for naming H-format files and V-format files:\n@@ -222,39 +160,42 @@\n \n Here are the types (defined in cddtypes.h) that are important for the cddlib user. The most\n important one, dd MatrixType, is to store a Polyhedra data in a straightforward manner. Once\n the user sets up a (pointer to) dd MatrixType data, he/she can load the data to an internal data\n type (dd PolyhedraType) by using functions described in the next section, and apply the double\n descrition method to get another representation. As an option dd MatrixType can save a linear\n objective function to be used by a linear programming solver.\n-4\n-\n-\fThe two dimensional array data in the structure dd MatrixType is dd Amatrix whose components are of type mytype. The type mytype is set to be either the rational type mpq t of the\n+The two dimensional array data in the structure dd MatrixType is dd Amatrix whose components are of type mytype. The type mytype is set to be either the rational type mpq t of the\n GNU MP Library or the C double array of size 1. This abstract type allows us to write a single\n program that can be compiled with the two or more different arithmetics, see example programs\n such as simplecdd.c, testlp*.c and testcdd*.c in the src and src-gmp subdirectories of the source\n distribution.\n There is another data type that is used very often, dd SetFamilyType. This is to store a\n family of subsets of a finite set. Such a family can represent the incidence relations between the\n set of extreme points and the set of facets of a polyhedron. Also, it can represent a graph structure by listing the set of vertices adjacent to each vertex (i.e. the adjacency list). To implement\n-dd SetFamilyType, we use a separate set library called setoper, that handles the basic set operations, This library is briefly introduced in Section 4.6.\n+dd SetFamilyType, we use a separate set library called setoper, that handles the basic set operations, This library is briefly introduced in Section ??.\n \n #define dd_FALSE 0\n #define dd_TRUE 1\n typedef long dd_rowrange;\n typedef long dd_colrange;\n typedef long dd_bigrange;\n typedef set_type dd_rowset;\n-/* set_type defined in setoper.h */\n typedef set_type dd_colset;\n typedef long *dd_rowindex;\n typedef int *dd_rowflag;\n typedef long *dd_colindex;\n-typedef mytype **dd_Amatrix; /* mytype is either GMP mpq_t or 1-dim double array. */\n-typedef mytype *dd_Arow;\n+typedef mytype **dd_Amatrix;\n+\n+/* set_type defined in setoper.h */\n+\n+/* mytype is either GMP mpq_t or 1-dim double array. */\n+4\n+\n+\ftypedef mytype *dd_Arow;\n typedef set_type *dd_SetVector;\n typedef enum {\n dd_Real, dd_Rational, dd_Integer, dd_Unknown\n } dd_NumberType;\n typedef enum {\n dd_Inequality, dd_Generator, dd_Unspecified\n } dd_RepresentationType;\n@@ -263,17 +204,15 @@\n dd_LexMin, dd_LexMax, dd_RandomRow\n } dd_RowOrderType;\n typedef enum {\n dd_InProgress, dd_AllFound, dd_RegionEmpty\n } dd_CompStatusType;\n typedef enum {\n dd_DimensionTooLarge, dd_ImproperInputFormat,\n-5\n-\n-\fdd_NegativeMatrixSize, dd_EmptyVrepresentation,\n+dd_NegativeMatrixSize, dd_EmptyVrepresentation,\n dd_IFileNotFound, dd_OFileNotOpen, dd_NoLPObjective,\n dd_NoRealNumberSupport, dd_NoError\n } dd_ErrorType;\n typedef enum {\n dd_LPnone=0, dd_LPmax, dd_LPmin\n } dd_LPObjectiveType;\n typedef enum {\n@@ -288,15 +227,18 @@\n /* a subset of rows of linearity (ie, generators of\n linearity space for V-representation, and equations\n for H-representation. */\n dd_colrange colsize;\n dd_RepresentationType representation;\n dd_NumberType numbtype;\n dd_Amatrix matrix;\n-dd_LPObjectiveType objective;\n+\n+5\n+\n+\fdd_LPObjectiveType objective;\n dd_Arow rowvec;\n } dd_MatrixType;\n typedef struct setfamily *dd_SetFamilyPtr;\n typedef struct setfamily {\n dd_bigrange famsize;\n dd_bigrange setsize;\n dd_SetVector set;\n@@ -307,18 +249,15 @@\n dd_LPObjectiveType objective;\n dd_LPSolverType solver;\n dd_rowrange m;\n dd_colrange d;\n dd_NumberType numbtype;\n dd_LPStatusType LPS; /* the current solution status */\n mytype optvalue; /* optimal value */\n-\n-6\n-\n-\fdd_Arow sol;\n+dd_Arow sol;\n /* primal solution */\n dd_Arow dsol; /* dual solution */\n dd_colindex nbindex; /* current basis represented by nonbasic indices */\n dd_rowrange re; /* row index as a certificate in the case of inconsistency */\n dd_colrange se; /* col index as a certificate in the case of dual inconsistency */\n long pivots[5];\n /* pivots[0]=setup (to find a basis), pivots[1]=PhaseI or Criss-Cross,\n@@ -334,21 +273,23 @@\n matrixP, of type dd MatrixPtr*, err is of type dd ErrorType*, ifile and ofile are of type\n char*, A is of type dd Amatrix, point and vector are of type dd Arow, d is of type dd colrange,\n m and i are of type dd rowrange, x is of type mytype, a is of type signed long integer, b is\n of type double, set is of type set type. Also, setfam is of type dd SetFamilyPtr, lp is of type\n dd LPPtr, lps is of type dd LPSolutionPtr, solver is of type dd LPSolverType, roworder is of\n type dd RowOrderType.\n \n-4.1\n+6\n+\n+\f4.1\n \n Library Initialization\n \n void dd set global constants(void) :\n This is to set the global constants such as dd zero, dd purezero and dd one for sign recognition and basic arithmetic operations. Every program to use cddlib must call this function\n-before doing any computation. Just call this once. See Section 4.3.3 for the definitions of\n+before doing any computation. Just call this once. See Section ?? for the definitions of\n constants.\n void dd free global constants(void) :\n This is to free the global constants. This should be called when one does not use cddlib\n functions anymore.\n \n 4.2\n \n@@ -361,34 +302,35 @@\n know that there is a serous limit in the sizes of problems that can be practically solved. Please\n check *.ext and *.ine files that come with cddlib to get ideas of tractable problems.\n In addition to previously defined objects, the symbol roworder is of dd RowOrderType. The\n symbol matrixP is a pointer to dd MatrixType. the arguments impl lin and redset are both\n a pointer to dd rowset type, and newpos is a pointer to dd rowindex type.\n dd PolyhedraPtr dd DDMatrix2Poly(matrix, err) :\n Store the representation given by matrix in a polyhedra data, and generate the second representation of *poly. It returns a pointer to the data. *err returns dd NoError if the\n-7\n-\n-\fcomputation terminates normally. Otherwise, it returns a value according to the error occurred.\n+computation terminates normally. Otherwise, it returns a value according to the error occurred.\n dd PolyhedraPtr dd DDMatrix2Poly2(matrix, roworder, err) :\n This is the same function as dd DDMatrix2Poly except that the insertion order is specified by the user. The argument roworder is of dd RowOrderType and takes one of the values: dd MaxIndex, dd MinIndex, dd MinCutoff, dd MaxCutoff, dd MixCutoff, dd LexMin,\n dd LexMax, dd RandomRow. In general, dd LexMin is the best choice which is in fact chosen\n in dd DDMatrix2Poly. If you know that the input is already sorted in the order you like, use\n dd MinIndex or dd MaxIndex. If the input contains many redundant rows (say more than\n 80% redundant), you might want to try dd MaxCutoff which might result in much faster\n-termination, see [3, 16]\n+termination, see [?, ?]\n boolean dd DDInputAppend(poly, matrix, err) :\n Modify the input representation in *poly by appending the matrix of *matrix, and compute\n the second representation. The number of columns in *matrix must be equal to the input\n representation.\n boolean dd LPSolve(lp, solver, err) :\n Solve lp by the algorithm solver and save the solututions in *lp. Unlike the earlier versions\n (dplex, cdd+), it can deal with equations and totally zero right hand sides. It is recommended\n that solver is dd DualSimplex, the revised dual simplex method that updates a d \u00d7 d dual\n basis matrix in each pivot (where d is the column size of lp).\n-The revised dual simplex method is ideal for dense LPs in small number of variables (i.e.\n+\n+7\n+\n+\fThe revised dual simplex method is ideal for dense LPs in small number of variables (i.e.\n small column size, typically less than 100) and many inequality constraints (i.e. large row\n size, can be a few ten thousands). If your LP has many variables but only few constraints,\n solve the dual LP by this function.\n When it is compiled for GMP rational arithmetic, it first tries to solve an LP with C double\n floating-point arithmetic and verifies whether the output basis is correct with GMP. If so, the\n correct solution is computed with GMP. Otherwise, it (re)solves the LP from scratch with\n GMP. This is newly implemented in the version 093. The original (non-crossover) version of\n@@ -402,18 +344,15 @@\n changing the polyhedron. The function works for both V- and H-representations.\n dd boolean dd SRedundant(matrix, i, point, err) :\n Check whether ith data in matrix is strongly redundant for the representation. If i is a linearity, it does nothing and always returns dd FALSE. Here, ith inequality in H-representation\n is strongly redundant if it is redundant and there is no point in the polyhedron satisfying the\n inequality with equality. In V-representation, ith point is strongly redundant if it is redundant\n and it is in the relative interior of the polyhedron. If it is not strongly redundant, it returns\n a certificate.\n-\n-8\n-\n-\fdd boolean dd ImplicitLinearity(matrix, i, err) :\n+dd boolean dd ImplicitLinearity(matrix, i, err) :\n Check whether ith row in the input is forced to be linearity (equality for H-representation).\n If i is linearity itself, it does nothing and always returns dd FALSE.\n dd rowset dd ImplicitLinearityRows(matrix, err) :\n Returns the set of indices of rows that are implicitly linearity. It simply calls the library\n function dd ImplicitLinearity for each inequality and collects the row indices for which\n the answer is dd TRUE.\n dd boolean dd MatrixCanonicalize(matrixP, impl lin, redset, newpos, err) :\n@@ -424,15 +363,17 @@\n are returned by the array newpos.\n The cardinality of the new linearity set (*matrixP)->linset is the codimension of the polyhedron if it is H-polyhedron, and is the dimension of linearity space if it is V-polyhedron.\n Note that the present version should not be called a canonicalization because it may generate\n two different representations of the same polyhedron. In the future, this function is expected\n to be correctly implemented.\n dd boolean dd MatrixCanonicalizeLinearity(matrixP, impl linset, newpos, err) :\n It does only the first half of dd boolean dd MatrixCanonicalize, namely, it detects all\n-implicit linearities and puts a maximally independent linearities at the top of the matrix. For\n+8\n+\n+\fimplicit linearities and puts a maximally independent linearities at the top of the matrix. For\n example, this function can be used to detect the dimension of an H-polyhedron.\n dd boolean dd MatrixRedundancyRemove(matrixP, redset, newpos, err) :\n It does essentially the second half of dd boolean dd MatrixCanonicalize, namely, it detects\n all redundancies. This function should be used after dd MatrixCanonicalizeLinearity has\n been called.\n dd boolean dd FindRelativeInterior(matrix, impl lin, lin basis, lps, err) :\n Computes a point in the relative interior of an H-polyhedron given by matrix, by solving\n@@ -452,17 +393,15 @@\n br \u2212 Ar x = 0, \u2200r \u2208 R \u222a L\n bs \u2212 As x > 0, \u2200s \u2208 S\n bt \u2212 At x \u2265 0, \u2200t \u2208 T,\n \n where L is the set of linearity rows of matrix, and T represents the set of rows that are not\n in R \u222a L \u222a S. Both R and S are of dd rowset type. The set S is supposed to be disjoint from\n both R and L. If it is not the case, the set S will be considered as S \\ (R \u222a L).\n-9\n-\n-\fThis function ignores matrix->representation, and thus even if it is set to dd Generator\n+This function ignores matrix->representation, and thus even if it is set to dd Generator\n or dd Unspecified, it treats the matrix as if it were inequality representation.\n dd boolean dd ExistsRestrictedFace2(matrix, R, S, lps, err) :\n It is the same as the function dd ExistsRestrictedFace except that it returns also a certificate for the answer. The certificate is a solution to the bounded LP:\n (P) max z\n \n subject to\n \n@@ -480,15 +419,17 @@\n dual unbounded direction) can be considered as a certificate for the NO answer, if the answer\n is NO.\n This function ignores matrix->representation, and thus even if it is set to dd Generator\n or dd Unspecified, it treats the matrix as if it were inequality representation.\n dd SetFamilyPtr dd Matrix2Adjacency(matrix, err) :\n Computes the adjacency list of input rows using the LP solver and without running the\n representation conversion. When the input is H-representation, it gives the facet graph of the\n-polyhedron. For V-representation, it gives the (vertex) graph of the polyhedron. It is required\n+9\n+\n+\fpolyhedron. For V-representation, it gives the (vertex) graph of the polyhedron. It is required\n that the input matrix is a minimal representation. Run redundancy removal functions before\n calling this function, see the sample code adjacency.c.\n dd SetFamilyPtr dd Matrix2WeakAdjacency(matrix, err) :\n Computes the weak adjacency list of input rows using the LP solver and without running\n the representation conversion. When the input is H-representation, it gives the graph where\n its nodes are the facets two nodes are adjacent if and only if the associated facets have some\n intersection. For V-representation, it gives the graph where its nodes are the vertices and two\n@@ -505,17 +446,15 @@\n the extreme rays of the dual linear system. See comments in the code cddproj.c for details.\n This might be a faster way to eliminate variables than the repeated FourierElimination when\n the number of variables to eliminate is large. If the input matrix is V-representation, *err\n returns dd NotAvailForV. This function does not remove redundancy and one might want to\n call redundancy removal functions afterwards. See the sample code projection.c.\n dd rowrange dd RayShooting(matrix, point, vector) :\n Finds the index of a halfspace first left by the ray starting from point toward the direction\n-10\n-\n-\fvector. It resolves tie by a lexicographic perturbation. Those inequalities violated by point\n+vector. It resolves tie by a lexicographic perturbation. Those inequalities violated by point\n will be simply ignored.\n \n 4.3\n 4.3.1\n \n Data Manipulations\n Number Assignments\n@@ -527,15 +466,18 @@\n void dd init(x) :\n This is to initialize a mytype variable x and to set it to zero. This initialization has to be\n called before any mytype variable to be used.\n void dd clear(x) :\n This is to free the space allocated to a mytype variable x.\n void dd set si(x, a) :\n This is to set a mytype variable x to the value of signed long integer a.\n-void dd set si2(x, a, b) :\n+\n+10\n+\n+\fvoid dd set si2(x, a, b) :\n This is to set a mytype variable x to the value of the rational expression a/b, where a is signed\n long and b is unsigned long integers.\n void dd set d(x, b) :\n This is to set a mytype variable x to the value of double b. This is available only when the\n library is compiled without -DGMPRATIONAL compiler option.\n 4.3.2\n \n@@ -548,18 +490,15 @@\n Set x to be the substraction of z from y.\n void dd mul(x, y, z) :\n Set x to be the multiplication of y and z.\n void dd div(x, y, z) :\n Set x to be the division of y over z.\n void dd inv(x, y) :\n Set x to be the reciplocal of y.\n-\n-11\n-\n-\f4.3.3\n+4.3.3\n \n Predefined Constants\n \n There are several mytype constants defined when dd set global constants(void) is called. Some\n constants depend on the double constant dd almostzero which is normally set to 10\u22127 in cdd.h.\n This value can be modified depending on how numerically delicate your problems are but an extra\n caution should be taken.\n@@ -569,15 +508,18 @@\n This represents the largest positive number which should be considered to be zero. In the\n GMPRATIONAL mode, it is equal to dd purezero. In the C double mode, it is set to the\n value of dd almostzero.\n mytype dd minuszero :\n The negative of dd zero.\n mytype dd one :\n This represents the mathematical one 1.\n-4.3.4\n+\n+11\n+\n+\f4.3.4\n \n Sign Evaluation and Comparison for mytype Numbers\n \n Below x, y, z are of type mytype.\n dd boolean dd Positive(x) :\n Returns dd TRUE if x is considered positive, and dd FALSE otherwise. In the GMPRATIONAL\n mode, the positivity recognition is exact. In the C double mode, this means the value is strictly\n@@ -598,32 +540,33 @@\n 4.3.5\n \n Polyhedra Data Manipulation\n \n dd MatrixPtr dd PolyFile2Matrix (f, err) :\n Read a Polyhedra data from stream f and store it in matrixdata and return a pointer to the\n data.\n-12\n-\n-\fdd MatrixPtr dd CopyInequalities(poly) :\n+dd MatrixPtr dd CopyInequalities(poly) :\n Copy the inequality representation pointed by poly to matrixdata and return dd MatrixPtr.\n dd MatrixPtr dd CopyGenerators(poly) :\n Copy the generator representation pointed by poly to matrixdata and return dd MatrixPtr.\n dd SetFamilyPtr dd CopyIncidence(poly) :\n Copy the incidence representation of the computed representation pointed by poly to setfamily\n and return dd SetFamilyPtr. The computed representation is Inequality if the input is\n Generator, and the vice visa.\n dd SetFamilyPtr dd CopyAdjacency(poly) :\n Copy the adjacency representation of the computed representation pointed by poly to setfamily\n and return dd SetFamilyPtr. The computed representation is Inequality if the input is\n Generator, and the vice visa.\n dd SetFamilyPtr dd CopyInputIncidence(poly) :\n Copy the incidence representation of the input representation pointed by poly to setfamily\n and return d SetFamilyPtr.\n-dd SetFamilyPtr dd CopyInputAdjacency(poly) :\n+\n+12\n+\n+\fdd SetFamilyPtr dd CopyInputAdjacency(poly) :\n Copy the adjacency representation of the input representation pointed by poly to setfamily\n and return d SetFamilyPtr.\n void dd FreePolyhedra(poly) :\n Free memory allocated to poly.\n 4.3.6\n \n LP Data Manipulation\n@@ -643,18 +586,15 @@\n Free memory allocated as an LP solution data pointed by lps.\n 4.3.7\n \n Matrix Manipulation\n \n dd MatrixPtr dd CopyMatrix(matrix) :\n Make a copy of matrixdata pointed by matrix and return a pointer to the copy.\n-\n-13\n-\n-\fdd MatrixPtr dd AppendMatrix(matrix1, matrix2) :\n+dd MatrixPtr dd AppendMatrix(matrix1, matrix2) :\n Make a matrixdata by copying *matrix1 and appending the matrix in *matrix2 and return\n a pointer to the data. The colsize must be equal in the two input matrices. It returns a\n NULL pointer if the input matrices are not appropriate. Its rowsize is set to the sum of\n the rowsizes of matrix1 and matrix2. The new matrixdata inherits everything else (i.e.\n numbertype, representation, etc) from the first matrix.\n int dd MatrixAppendTo(& matrix1, matrix2) :\n Same as dd AppendMatrix except that the first matrix is modified to take the result.\n@@ -662,16 +602,17 @@\n Remove the ith row of matrix.\n dd MatrixPtr dd MatrixSubmatrix(matrix, set) :\n Generate the submatrix of matrix by removing the rows indexed by set and return a matrixdata pointer.\n dd SetFamilyPtr dd Matrix2Adjacency(matrix, err) :\n Return the adjacency list of the representation given by matrix. The computation is done by\n the built-in LP solver. The representation should be free of redundancy when this function is\n called. See the function dd rowset dd RedundantRows and the example program adjacency.c.\n+13\n \n-4.4\n+\f4.4\n \n Input/Output Functions\n \n dd MatrixPtr dd PolyFile2Matrix (f, err) :\n Read a Polyhedra data from stream f and store it in matrixdata and return a pointer to the\n data.\n boolean dd DDFile2File(ifile, ofile, err) :\n@@ -688,38 +629,37 @@\n Write error messages given by err to stream f.\n void dd WriteSetFamily(f, setfam) :\n Write the set family pointed by setfam to stream f. For each set, it outputs its index, its\n cardinality, a colon \u201c:\u201d and a ordered list of its elements.\n void dd WriteSetFamilyCompressed(f, setfam) :\n Write the set family pointed by setfam to stream f. For each set, it outputs its index, its\n cardinality or the negative of the cardinality, a colon \u201c:\u201d and the elements in the set or its\n-14\n-\n-\fcomplements whichever is smaller. Whenever it outputs the complements, the cardinality\n+complements whichever is smaller. Whenever it outputs the complements, the cardinality\n is negated so that there is no ambiguity. This will be considered standard for outputing\n incidence (*.icd, *ecd) and adjacency (*.iad, *.ead) data in cddlib. But there is some minor\n incompatibility with cdd/cdd+ standalone codes.\n void dd WriteProgramDescription(f) :\n Write the cddlib version information to stream f.\n void dd WriteDDTimes(f, poly) :\n Write the representation conversion time information on poly to stream f.\n \n 4.5\n \n Obsolete Functions\n \n boolean dd DoubleDescription(poly, err) : (removed in Version 0.90c)\n-The new function dd DDMatrix2Poly(matrix, err) (see Section 4.2) replaces (and actually\n+The new function dd DDMatrix2Poly(matrix, err) (see Section ??) replaces (and actually\n combines) both this and dd Matrix2Poly(matrix, err).\n dd PolyhedraPtr dd Matrix2Poly(matrix, err) : (removed in Version 0.90c)\n See above for the reason for removal.\n dd LPSolutionPtr dd LPSolutionLoad(lp) : (renamed in Version 0.90c)\n This function is now called dd CopyLPSolution(lp).\n+14\n \n-4.6\n+\f4.6\n \n Set Functions in setoper library\n \n The cddlib comes with a simple set operation library setoper. The key type defined is set type.\n A set is represented by a fixed length binary strings. Thus, the maximum length of a set must be\n declared when it is initialized.\n Below the symbols a, b, c are of type set type. The symbols aP is a pointer to type set type,\n@@ -735,18 +675,15 @@\n of b.\n void set addelem(a, t)) :\n Add an element t to a set a. The set a stays unchanged if it contains the element t.\n long set card(a)) :\n Return the cardinality of set a.\n int set member(t, a)) :\n Return 1 if t is a member of set a, and 0 otherwise.\n-\n-15\n-\n-\fvoid set write(a)) :\n+void set write(a)) :\n Print out the elements of set a to stdout. The function void set fwrite(f, a)) output to\n stream f.\n \n 5\n \n An Extension of the CDD Library in GMP mode\n \n@@ -762,15 +699,17 @@\n 6\n \n Examples\n \n See example codes such as testcdd*.c , testlp*.c, redcheck.c, adjacency.c, allfaces,c and simplecdd.c\n in the src and src-gmp subdirectories of the source distribution.\n \n-7\n+15\n+\n+\f7\n \n Numerical Accuracy\n \n A little caution is in order. Many people have observed numerical problems of cddlib when the\n floating version of cddlib is used. As we all know, floating-point computation might not give a\n correct answer, especially when an input data is very sensitive to a small perturbation. When some\n strange behavior is observed, it is always wise to create a rationalization of the input (for example,\n@@ -792,72 +731,73 @@\n magnitude than those in another column, scale one so that they become comparable.\n \n 8\n \n Other Useful Codes\n \n There are several other useful codes available for vertex enumeration and/or convex hull computation such as lrs, qhull, porta and irisa-polylib. The pointers to these codes are available at\n-1. lrs by D. Avis [2] (C implementation of the reverse search algorithm [4]).\n-16\n-\n-\f2. qhull by C.B. Barber [6] (C implementation of the beneath-beyond method, see [10, 20], which\n+1. lrs by D. Avis [?] (C implementation of the reverse search algorithm [?]).\n+2. qhull by C.B. Barber [?] (C implementation of the beneath-beyond method, see [?, ?], which\n is the dual of the dd method).\n-3. porta by T. Christof and A. Lo\u0308bel [8] (C implementation of the Fourier-Motzkin elimination).\n-4. IRISA polyhedral library by D.K. Wilde [23] (C implementation of a variation of the dd\n+3. porta by T. Christof and A. Lo\u0308bel [?] (C implementation of the Fourier-Motzkin elimination).\n+4. IRISA polyhedral library by D.K. Wilde [?] (C implementation of a variation of the dd\n algorithm).\n-5. PPL: the Parma Polyhedra Library [5] by R. Bagnara (C++ implementation of a variation\n+5. PPL: the Parma Polyhedra Library [?] by R. Bagnara (C++ implementation of a variation\n of the dd algorithm).\n-6. pd by A. Marzetta [18] (C implementation of the primal-dual algorithm [7]).\n-7. Geometry Center Software List by N. Amenta [1].\n-8. Computational Geometry Pages by J. Erickson [11].\n-9. Linear Programming FAQ by R. Fourer and J. Gregory [12].\n+6. pd by A. Marzetta [?] (C implementation of the primal-dual algorithm [?]).\n+7. Geometry Center Software List by N. Amenta [?].\n+8. Computational Geometry Pages by J. Erickson [?].\n+9. Linear Programming FAQ by R. Fourer and J. Gregory [?].\n 10. ZIB Berlin polyhedral software list:\n ftp://elib.zib-berlin.de/pub/mathprog/polyth/index.html.\n-11. Polyhedral Computation FAQ [13].\n+11. Polyhedral Computation FAQ [?].\n \n-9\n+16\n+\n+\f9\n \n Codes Using Cddlib\n \n There are quite a few nice programs using some functions of cddlib. Here are some of them.\n-1. LattE [9] computes the number of lattice points in a convex polytope.\n-2. Minksum [22] is a program to compute the V-representation (i.e. the set of vertices) of the\n+1. LattE [?] computes the number of lattice points in a convex polytope.\n+2. Minksum [?] is a program to compute the V-representation (i.e. the set of vertices) of the\n Minkowski addition of several convex polytopes given by their V-representation in Rd . It is an\n-implementation in C++ language of the reverse search algorithm [14] whose time complexity\n+implementation in C++ language of the reverse search algorithm [?] whose time complexity\n is polynomially bounded by the sizes of input and output.\n-3. Gfan [17] is a program to list all reduced Gro\u0308bner bases of a general polynomial ideal given\n-by a set of generating polynomials in n-variables. It is an implementation in C++ language\n-of the reverse search algorithm [15].\n-4. TOPCOM [21] computes the combinatorial structure (the oriented matroid) of a point configuration and enumerates all triangulations of a point set. It detects the regularity of a\n-triangulation using cddlib.\n+3. Gfan [?] is a program to list all reduced Gro\u0308bner bases of a general polynomial ideal given by\n+a set of generating polynomials in n-variables. It is an implementation in C++ language of\n+the reverse search algorithm [?].\n+4. TOPCOM [?] computes the combinatorial structure (the oriented matroid) of a point configuration and enumerates all triangulations of a point set. It detects the regularity of a triangulation using cddlib.\n \n Acknowledgements.\n I am grateful to Tom Liebling who provided me with an ideal opportunity to visit EPFL for\n the academic year 1993-1994. Later, Hans-Jakob Lu\u0308thi (ETHZ) and Emo Welzl (ETHZ) joined\n to support the the development of cdd codes (cdd, cdd+, cddlib). Without their generous and\n continuing support, the present form of this program would not have existed.\n There are many other people who helped me to improve cdd, in particular, I am indebted to\n David Avis, Alexander Bockmayr, David Bremner, Henry Crapo, Istvan Csabai, Francois Margot,\n Marc Pfetsch, Alain Prodon, Jo\u0308rg Rambau, Dima Pasechnik, Shawn Rusaw, Matthew Saltzman,\n Masanori Sato, Anders Jensen, Ruriko Yoshida, Charles Geyer, Michal Kvasnica, Sven Verdoolaege\n (listed in arbitrary order) and those listed in the HISTORY file.\n-17\n \n-\fReferences\n+References\n [1] N. Amenta. Directory of computational geometry. http://www.geom.uiuc.edu/software/cglist/.\n [2] D. Avis. lrs Homepage. http://cgm.cs.mcgill.ca/\u02dcavis/C/lrs.html.\n [3] D. Avis, D. Bremner, and R. Seidel. How good are convex hull algorithms. Computational\n Geometry: Theory and Applications, 7:265\u2013302, 1997.\n [4] D. Avis and K. Fukuda. A pivoting algorithm for convex hulls and vertex enumeration of\n arrangements and polyhedra. Discrete Comput. Geom., 8:295\u2013313, 1992.\n [5] R. Bagnara. Parma polyhedra library homepage, 2004. http://www.cs.unipr.it/ppl/.\n [6] C.B. Barber, D.P. Dobkin, and H. Huhdanpaa. qhull, Version 2003.1, 2003. program and\n report available from http://www.qhull.org/.\n [7] D. Bremner, K. Fukuda, and A. Marzetta. Primal-dual methods for vertex and facet enumeration. In Proc. 13th Annu. ACM Sympos. Comput. Geom., pages 49\u201356, 1997.\n-[8] T. Christof and A. Lo\u0308bel. PORTA: Polyhedron representation transformation algorithm (ver.\n+\n+17\n+\n+\f[8] T. Christof and A. Lo\u0308bel. PORTA: Polyhedron representation transformation algorithm (ver.\n 1.3.1), 1997. http://www.zib.de/Optimization/Software/Porta/.\n [9] J. de Loera, D. Haws, R. Hemmecke, Peter Huggins, J. Tauzer, and R. Yoshida. LattE.\n University of California, Davis, 2005. available from http://www.math.ucdavis.edu/ latte/.\n [10] H. Edelsbrunner. Algorithms in Combinatorial Geometry. Springer-Verlag, 1987.\n [11] J. Erickson.\n Computational geometry pages, list of software libraries and codes.\n http://compgeom.cs.uiuc.edu/\u02dcjeffe/compgeom/.\n@@ -873,24 +813,22 @@\n and I. Manoussakis, editors, Combinatorics and Computer Science, volume 1120 of Lecture Notes in Computer Science, pages 91\u2013111. Springer-Verlag, 1996. ps file available from\n ftp://ftp.ifor.math.ethz.ch/pub/fukuda/reports/ddrev960315.ps.gz.\n [17] A.N. Jensen. Gfan version 0.1: A User\u2019s Manual. Department of Mathematical Sciences,\n University of Aarhus and Institute for Operations Research, ETH Zurich, 2005. available from\n http://home.imf.au.dk/ajensen/software/gfan/gfan.html.\n [18] A. Marzetta. pd \u2013 C-implementation of the primal-dual algoirithm, 1997. code available from\n http://www.cs.unb.ca/profs/bremner/pd/.\n-18\n-\n-\f[19] T.S. Motzkin, H. Raiffa, GL. Thompson, and R.M. Thrall. The double description method.\n+[19] T.S. Motzkin, H. Raiffa, GL. Thompson, and R.M. Thrall. The double description method.\n In H.W. Kuhn and A.W.Tucker, editors, Contributions to theory of games, Vol. 2. Princeton\n University Press, Princeton, RI, 1953.\n [20] K. Mulmuley. Computational Geometry, An Introduction Through Randamized Algorithms.\n Prentice-Hall, 1994.\n [21] J. Rambau. TOPCOM, a package for computing Triangulations Of Point Configurations\n and Oriented Matroids. University of Bayreuth, 2005. available from http://www.unibayreuth.de/departments/wirtschaftsmathematik/rambau/TOPCOM/.\n [22] C. Weibel. Minksum version 1.1. Mathematics Institute, EPF Lausanne, 2005. available from\n http://roso.epfl.ch/cw/poly/public.php.\n [23] D.K. Wilde. A library for doing polyhedral operations. Master\u2019s thesis, Oregon State University, Corvallis, Oregon, Dec 1993. Also published in IRISA technical report PI 785, Rennes,\n France; Dec, 1993.\n \n-19\n+18\n \n \f\n"}]}]}]}]}]}]}