Sandia Home Sandia Home
Main Page | Publications | Downloads | Configuration | Running the Code | Solver Parameters | FAQ | Namespace List | Class Hierarchy | Class List | File List | Namespace Members | Class Members | File Members | Related Pages

cddtypes.h

Go to the documentation of this file.
00001 
00043 #ifndef DOXYGEN_SHOULD_SKIP_THIS
00044 
00045 /* cddtypes.h: Header file for cddlib.c 
00046    written by Komei Fukuda, fukuda@ifor.math.ethz.ch
00047    Version 0.94b, Aug. 24, 2005
00048 */
00049 
00050 /* cddlib.c : C-Implementation of the double description method for
00051    computing all vertices and extreme rays of the polyhedron 
00052    P= {x :  b - A x >= 0}.  
00053    Please read COPYING (GNU General Public Licence) and
00054    the manual cddlibman.tex for detail.
00055 */
00056 
00057 #ifndef  __CDDTYPES_H
00058 #define  __CDDTYPES_H
00059 #endif  /* __CDDTYPES_H */
00060 
00061 #define dd_COPYRIGHT   "Copyright (C) 1996, Komei Fukuda, fukuda@ifor.math.ethz.ch"
00062 #define dd_DDVERSION   "Version 0.94b (August 25, 2005)"
00063 #include <time.h>
00064 
00065 #define dd_wordlenmax     127
00066 #define dd_linelenmax     255
00067 #define dd_datawidth       10
00068 #define dd_filenamelen    255
00069 
00070 #define dd_FALSE 0
00071 #define dd_TRUE 1
00072 
00073 typedef int dd_boolean;
00074 
00075 typedef long dd_rowrange;
00076 typedef long dd_colrange;
00077 typedef long dd_bigrange;
00078 
00079 typedef set_type dd_rowset;
00080 typedef set_type dd_colset;
00081 typedef long *dd_rowindex;   
00082 typedef int *dd_rowflag;   
00083 typedef long *dd_colindex;
00084 typedef mytype **dd_Amatrix;
00085 typedef mytype *dd_Arow;
00086 typedef set_type *dd_SetVector;
00087 typedef mytype **dd_Bmatrix;
00088 typedef set_type *dd_Aincidence;
00089 
00090 /* typedef char dd_FilenameType[dd_filenamelen]; deleted 000505*/
00091 typedef char dd_DataFileType[dd_filenamelen];
00092 typedef char dd_LineType[dd_linelenmax];
00093 typedef char dd_WordType[dd_wordlenmax];
00094 
00095 typedef struct dd_raydata *dd_RayPtr;
00096 
00097 typedef struct dd_raydata {
00098   mytype *Ray;
00099   dd_rowset ZeroSet;
00100   dd_rowrange FirstInfeasIndex;  /* the first inequality the ray violates */
00101   dd_boolean feasible;  /* flag to store the feasibility */
00102   mytype ARay;   /* temporary area to store some row of A*Ray */
00103   dd_RayPtr Next;
00104 } dd_RayType;
00105 
00106 typedef struct dd_adjacencydata *dd_AdjacencyPtr;
00107 typedef struct dd_adjacencydata {
00108   dd_RayPtr Ray1, Ray2;
00109   dd_AdjacencyPtr Next;
00110 } dd_AdjacencyType;
00111 
00112 typedef enum {
00113   dd_Combinatorial, dd_Algebraic
00114 } dd_AdjacencyTestType;
00115 
00116 typedef enum {
00117   dd_MaxIndex, dd_MinIndex, dd_MinCutoff, dd_MaxCutoff, dd_MixCutoff,
00118    dd_LexMin, dd_LexMax, dd_RandomRow
00119 } dd_RowOrderType;
00120 
00121 typedef enum {
00122   dd_Unknown=0, dd_Real, dd_Rational, dd_Integer
00123 } dd_NumberType;
00124 
00125 typedef enum {
00126   dd_Unspecified=0, dd_Inequality, dd_Generator
00127 } dd_RepresentationType;
00128 
00129 typedef enum {
00130   dd_IneToGen, dd_GenToIne, dd_LPMax, dd_LPMin, dd_InteriorFind
00131 } dd_ConversionType;
00132 
00133 typedef enum {
00134   dd_IncOff=0, dd_IncCardinality, dd_IncSet
00135 } dd_IncidenceOutputType;
00136 
00137 typedef enum {
00138   dd_AdjOff=0, dd_AdjacencyList,  dd_AdjacencyDegree
00139 } dd_AdjacencyOutputType;
00140 
00141 typedef enum {
00142   dd_Auto, dd_SemiAuto, dd_Manual
00143 } dd_FileInputModeType;   
00144    /* Auto if a input filename is specified by command arguments */
00145 
00146 typedef enum {
00147   dd_DimensionTooLarge, dd_ImproperInputFormat, 
00148   dd_NegativeMatrixSize, dd_EmptyVrepresentation, dd_EmptyHrepresentation, dd_EmptyRepresentation,
00149   dd_IFileNotFound, dd_OFileNotOpen, dd_NoLPObjective, dd_NoRealNumberSupport,
00150   dd_NotAvailForH, dd_NotAvailForV, dd_CannotHandleLinearity,
00151   dd_RowIndexOutOfRange, dd_ColIndexOutOfRange,
00152   dd_LPCycling, dd_NumericallyInconsistent,
00153   dd_NoError
00154 } dd_ErrorType;
00155 
00156 typedef enum {
00157   dd_InProgress, dd_AllFound, dd_RegionEmpty
00158 } dd_CompStatusType;
00159 
00160 /* --- LP types ---- */
00161 
00162 typedef enum {
00163   dd_LPnone=0, dd_LPmax, dd_LPmin
00164 } dd_LPObjectiveType;
00165 
00166 typedef enum {
00167   dd_CrissCross, dd_DualSimplex
00168 } dd_LPSolverType;
00169 
00170 typedef enum {
00171   dd_LPSundecided, dd_Optimal, dd_Inconsistent, dd_DualInconsistent,
00172   dd_StrucInconsistent, dd_StrucDualInconsistent,
00173   dd_Unbounded, dd_DualUnbounded
00174 } dd_LPStatusType;
00175 
00176 typedef struct dd_lpsolution *dd_LPSolutionPtr;
00177 typedef struct dd_lpsolution {
00178   dd_DataFileType filename;
00179   dd_LPObjectiveType objective;
00180   dd_LPSolverType solver; 
00181   dd_rowrange m;
00182   dd_colrange d;
00183   dd_NumberType numbtype;
00184 
00185   dd_LPStatusType LPS;  /* the current solution status */
00186   mytype optvalue;  /* optimal value */
00187   dd_Arow sol;   /* primal solution */
00188   dd_Arow dsol;  /* dual solution */
00189   dd_colindex nbindex;  /* current basis represented by nonbasic indices */
00190   dd_rowrange re;  /* row index as a certificate in the case of inconsistency */
00191   dd_colrange se;  /* col index as a certificate in the case of dual inconsistency */
00192   long pivots[5]; 
00193    /* pivots[0]=setup (to find a basis), pivots[1]=PhaseI or Criss-Cross,
00194       pivots[2]=Phase II, pivots[3]=Anticycling, pivots[4]=GMP postopt. */
00195   long total_pivots;
00196 } dd_LPSolutionType;
00197 
00198 
00199 typedef struct dd_lpdata *dd_LPPtr;
00200 typedef struct dd_lpdata {
00201   dd_DataFileType filename;
00202   dd_LPObjectiveType objective;
00203   dd_LPSolverType solver; 
00204   dd_boolean Homogeneous;  
00205      /* The first column except for the obj row is all zeros. */
00206   dd_rowrange m;
00207   dd_colrange d;
00208   dd_Amatrix A;
00209   dd_Bmatrix B;
00210   dd_rowrange objrow;
00211   dd_colrange rhscol;
00212   dd_NumberType numbtype;
00213   dd_rowrange eqnumber;  /* the number of equalities */
00214   dd_rowset equalityset;  
00215 
00216   dd_boolean redcheck_extensive;  /* Apply the extensive redundancy check. */
00217   dd_rowrange ired; /* the row index for the redundancy checking */
00218   dd_rowset redset_extra;  /* a set of rows that are newly recognized redundan by the extensive search. */
00219   dd_rowset redset_accum;  /* the accumulated set of rows that are recognized redundant */
00220   dd_rowset posset_extra;  /* a set of rows that are recognized non-linearity */
00221 
00222   dd_boolean lexicopivot;  /* flag to use the lexicogrphic pivot rule (symbolic perturbation). */
00223 
00224   dd_LPStatusType LPS;  /* the current solution status */
00225   dd_rowrange m_alloc; /* the allocated row size of matrix A */
00226   dd_colrange d_alloc; /* the allocated col size of matrix A */
00227   mytype optvalue;  /* optimal value */
00228   dd_Arow sol;   /* primal solution */
00229   dd_Arow dsol;  /* dual solution */
00230   dd_colindex nbindex;  /* current basis represented by nonbasic indices */
00231   dd_rowrange re;  /* row index as a certificate in the case of inconsistency */
00232   dd_colrange se;  /* col index as a certificate in the case of dual inconsistency */
00233   long pivots[5]; 
00234    /* pivots[0]=setup (to find a basis), pivots[1]=PhaseI or Criss-Cross,
00235       pivots[2]=Phase II, pivots[3]=Anticycling, pivots[4]=GMP postopt. */
00236   long total_pivots;
00237   int use_given_basis;  /* switch to indicate the use of the given basis */
00238   dd_colindex given_nbindex;  /* given basis represented by nonbasic indices */
00239   time_t starttime;
00240   time_t endtime;
00241 } dd_LPType;
00242 
00243 
00244 /*----  end of LP Types ----- */
00245 
00246 
00247 typedef struct  dd_matrixdata *dd_MatrixPtr;
00248 typedef struct  dd_matrixdata {
00249   dd_rowrange rowsize;
00250   dd_rowset linset; 
00251     /*  a subset of rows of linearity (ie, generators of
00252         linearity space for V-representation, and equations
00253         for H-representation. */
00254   dd_colrange colsize;
00255   dd_RepresentationType representation;
00256   dd_NumberType numbtype;
00257   dd_Amatrix matrix;
00258   dd_LPObjectiveType objective;
00259   dd_Arow rowvec;
00260 } dd_MatrixType;
00261 
00262 typedef struct dd_setfamily *dd_SetFamilyPtr;
00263 typedef struct dd_setfamily {
00264   dd_bigrange famsize;
00265   dd_bigrange setsize;
00266   dd_SetVector set;  
00267 } dd_SetFamilyType;
00268 
00269 
00270 typedef struct dd_nodedata *dd_NodePtr;
00271 typedef struct dd_nodedata {dd_bigrange key; dd_NodePtr next;} dd_NodeType;
00272 
00273 typedef struct dd_graphdata *dd_GraphPtr;
00274 typedef struct dd_graphdata {
00275   dd_bigrange vsize;
00276   dd_NodePtr *adjlist;  /* should be initialized to have vsize components */
00277 } dd_GraphType;
00278 
00279 
00280 typedef struct dd_polyhedradata *dd_PolyhedraPtr;
00281 typedef struct dd_conedata *dd_ConePtr;
00282 
00283 typedef struct dd_polyhedradata {
00284   dd_RepresentationType representation;  /* given representation */
00285   dd_boolean homogeneous;
00286   dd_colrange d;
00287   dd_rowrange m;
00288   dd_Amatrix A;   /* Inequality System:  m times d matrix */
00289   dd_NumberType numbtype;
00290   dd_ConePtr child;  /* pointing to the homogenized cone data */
00291   dd_rowrange m_alloc; /* allocated row size of matrix A */
00292   dd_colrange d_alloc; /* allocated col size of matrix A */
00293   dd_Arow c;           /* cost vector */
00294 
00295   dd_rowflag EqualityIndex;  
00296     /* ith component is 1 if it is equality, -1 if it is strict inequality, 0 otherwise. */
00297 
00298   dd_boolean IsEmpty;  /* This is to tell whether the set is empty or not */
00299   
00300   dd_boolean NondegAssumed;
00301   dd_boolean InitBasisAtBottom;
00302   dd_boolean RestrictedEnumeration;
00303   dd_boolean RelaxedEnumeration;
00304 
00305   dd_rowrange m1; 
00306     /* = m or m+1 (when representation=Inequality && !homogeneous)
00307        This data is written after dd_ConeDataLoad is called.  This
00308        determines the size of Ainc. */
00309   dd_boolean AincGenerated;
00310     /* Indicates whether Ainc, Ared, Adom are all computed.
00311        All the variables below are valid only when this is TRUE */
00312   dd_colrange ldim;   /* linearity dimension */
00313   dd_bigrange n; 
00314     /* the size of output = total number of rays 
00315        in the computed cone + linearity dimension */
00316   dd_Aincidence Ainc;
00317     /* incidence of input and output */
00318   dd_rowset Ared;  
00319     /* redundant set of rows whose removal results in a minimal system */
00320   dd_rowset Adom;  
00321     /* dominant set of rows (those containing all rays). */
00322 
00323 } dd_PolyhedraType;
00324 
00325 
00326 typedef struct dd_conedata {
00327   dd_RepresentationType representation;
00328   dd_rowrange m;
00329   dd_colrange d;
00330   dd_Amatrix A;
00331   dd_NumberType numbtype;
00332   dd_PolyhedraPtr parent;  /* pointing to the original polyhedra data */
00333   dd_rowrange m_alloc; /* allocated row size of matrix A */
00334   dd_colrange d_alloc; /* allocated col size of matrix A */
00335 
00336 /* CONTROL: variables to control computation */
00337   dd_rowrange Iteration;
00338   dd_RowOrderType HalfspaceOrder;
00339   dd_RayPtr FirstRay, LastRay, ArtificialRay; /* The second description: Generator */
00340   dd_RayPtr PosHead, ZeroHead, NegHead, PosLast, ZeroLast, NegLast;
00341   dd_AdjacencyType **Edges;  /* adjacency relation storage for iteration k */
00342   unsigned int rseed;  /* random seed for random row permutation */
00343 
00344   dd_boolean ColReduced;  /* flag to indicate that a column basis is computed and reduced */
00345   dd_bigrange LinearityDim;   
00346            /*  the dimension of the linearity space (when input is H), and
00347                the size of a minimal system of equations to determine the space (when V). */
00348   dd_colrange d_orig;  /* the size d of the original matrix A */
00349   dd_colindex newcol;  /* the size d of the original matrix A */
00350   
00351   dd_colindex InitialRayIndex;   /* InitialRayIndex[s] (s>=1) stores the corr. row index */
00352   dd_rowindex OrderVector;
00353   dd_boolean RecomputeRowOrder;
00354   dd_boolean PreOrderedRun;
00355   dd_rowset GroundSet, EqualitySet, NonequalitySet, 
00356        AddedHalfspaces, WeaklyAddedHalfspaces, InitialHalfspaces;
00357   long RayCount, FeasibleRayCount, WeaklyFeasibleRayCount,
00358        TotalRayCount, ZeroRayCount;
00359   long EdgeCount, TotalEdgeCount;
00360   long count_int,count_int_good,count_int_bad; /* no. of intersection operations */
00361 
00362   dd_Bmatrix B;
00363   dd_Bmatrix Bsave;  /* a copy of the dual basis inverse used to reduce the matrix A */
00364 
00365 /* STATES: variables to represent current state. */
00366   dd_ErrorType Error;
00367   dd_CompStatusType CompStatus;  /* Computation Status */
00368   time_t starttime, endtime;
00369 } dd_ConeType;
00370 
00371 /* Global Variables */
00372 extern dd_boolean dd_debug;
00373 extern dd_boolean dd_log;
00374 
00375 /* end of cddtypes.h */
00378 #endif

 

© Sandia Corporation | Site Contact | Privacy and Security

Generated on Fri Feb 16 10:33:35 2007 for APPSPACK 5.0.1 by doxygen 1.3.9.1 written by Dimitri van Heesch, © 1997-2002