| | | | |
| Offset 2, 48 lines modified | Offset 2, 110 lines modified |
| 2 | Komei·Fukuda | 2 | Komei·Fukuda |
| 3 | Institute·for·Operations·Research | 3 | Institute·for·Operations·Research |
| 4 | and·Institute·of·Theoretical·Computer·Science | 4 | and·Institute·of·Theoretical·Computer·Science |
| 5 | ETH·Zentrum,·CH-8092·Zurich,·Switzerland | 5 | ETH·Zentrum,·CH-8092·Zurich,·Switzerland |
| 6 | (cddlib·ver.·0.94,·manual·ver.·February·7,·2008) | 6 | (cddlib·ver.·0.94,·manual·ver.·February·7,·2008) |
| | |
| 7 | Contents | 7 | Contents |
| | 8 | 1·Introduction |
| | |
| | 9 | 2 |
| | |
| | 10 | 2·Polyhedra·H-·and·V-Formats·(Version·1999) |
| | |
| | 11 | 3 |
| | |
| | 12 | 3·Basic·Object·Types·(Structures)·in·cddlib |
| | |
| | 13 | 4 |
| | |
| | 14 | 4·Library·Functions |
| | 15 | 4.1·Library·Initialization·.·.·.·.·.·.·.·.·.·.·.·.·.·.·.·.·.·.·.·.·.·.·.·.·.·.·.·.·.·.·.·.·.·.·.·. |
| | 16 | 4.2·Core·Functions·.·.·.·.·.·.·.·.·.·.·.·.·.·.·.·.·.·.·.·.·.·.·.·.·.·.·.·.·.·.·.·.·.·.·.·.·.·.·. |
| | 17 | 4.3·Data·Manipulations·.·.·.·.·.·.·.·.·.·.·.·.·.·.·.·.·.·.·.·.·.·.·.·.·.·.·.·.·.·.·.·.·.·.·.·. |
| | 18 | 4.3.1·Number·Assignments·.·.·.·.·.·.·.·.·.·.·.·.·.·.·.·.·.·.·.·.·.·.·.·.·.·.·.·.·.·.·.·. |
| | 19 | 4.3.2·Arithmetic·Operations·for·mytype·Numbers·.·.·.·.·.·.·.·.·.·.·.·.·.·.·.·.·.·.·. |
| | 20 | 4.3.3·Predefined·Constants·.·.·.·.·.·.·.·.·.·.·.·.·.·.·.·.·.·.·.·.·.·.·.·.·.·.·.·.·.·.·. |
| | 21 | 4.3.4·Sign·Evaluation·and·Comparison·for·mytype·Numbers·.·.·.·.·.·.·.·.·.·.·.·.·. |
| | 22 | 4.3.5·Polyhedra·Data·Manipulation·.·.·.·.·.·.·.·.·.·.·.·.·.·.·.·.·.·.·.·.·.·.·.·.·.·.·. |
| | 23 | 4.3.6·LP·Data·Manipulation·.·.·.·.·.·.·.·.·.·.·.·.·.·.·.·.·.·.·.·.·.·.·.·.·.·.·.·.·.·.·. |
| | 24 | 4.3.7·Matrix·Manipulation·.·.·.·.·.·.·.·.·.·.·.·.·.·.·.·.·.·.·.·.·.·.·.·.·.·.·.·.·.·.·.·. |
| | 25 | 4.4·Input/Output·Functions·.·.·.·.·.·.·.·.·.·.·.·.·.·.·.·.·.·.·.·.·.·.·.·.·.·.·.·.·.·.·.·.·.·. |
| | 26 | 4.5·Obsolete·Functions·.·.·.·.·.·.·.·.·.·.·.·.·.·.·.·.·.·.·.·.·.·.·.·.·.·.·.·.·.·.·.·.·.·.·.·.·. |
| | 27 | 4.6·Set·Functions·in·setoper·library·.·.·.·.·.·.·.·.·.·.·.·.·.·.·.·.·.·.·.·.·.·.·.·.·.·.·.·.·. |
| | |
| | 28 | 7 |
| | 29 | 7 |
| | 30 | 7 |
| | 31 | 11 |
| | 32 | 11 |
| | 33 | 11 |
| | 34 | 12 |
| | 35 | 12 |
| | 36 | 12 |
| | 37 | 13 |
| | 38 | 13 |
| | 39 | 14 |
| | 40 | 15 |
| | 41 | 15 |
| | |
| | 42 | 5·An·Extension·of·the·CDD·Library·in·GMP·mode |
| | |
| | 43 | 16 |
| | |
| | 44 | 6·Examples |
| | |
| | 45 | 16 |
| | |
| | 46 | 7·Numerical·Accuracy |
| | |
| | 47 | 16 |
| | |
| | 48 | 8·Other·Useful·Codes |
| | |
| | 49 | 16 |
| | |
| | 50 | 9·Codes·Using·Cddlib |
| | |
| | 51 | 17 |
| 8 | Abstract | 52 | Abstract |
| | |
| 9 | This·is·a·reference·manual·for·cddlib-094.·The·manual·describes·the·library·functions·and | 53 | This·is·a·reference·manual·for·cddlib-094.·The·manual·describes·the·library·functions·and |
| 10 | data·types·implemented·in·the·cddlib·C-library·which·is·to·perform·fundamental·polyhedral | 54 | data·types·implemented·in·the·cddlib·C-library·which·is·to·perform·fundamental·polyhedral |
| 11 | computations·such·as·representation·conversions·and·linear·programming·in·both·floating-point | 55 | computations·such·as·representation·conversions·and·linear·programming·in·both·floating-point |
| | |
| | 56 | 1 |
| | |
| 12 | and·GMP·rational·exact·arithmetic.·Please·read·the·accompanying·README·file·and·test | 57 | .and·GMP·rational·exact·arithmetic.·Please·read·the·accompanying·README·file·and·test |
| 13 | programs·to·complement·the·manual. | 58 | programs·to·complement·the·manual. |
| 14 | 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 | 59 | 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 |
| 15 | point·of·an·H-polyhedron,·and·dd·ExistsRestrictedFace·(Farkas-type·alternative·theorem | 60 | point·of·an·H-polyhedron,·and·dd·ExistsRestrictedFace·(Farkas-type·alternative·theorem |
| 16 | verifier)·to·check·the·existence·of·a·point·satisfying·a·specified·system·of·linear·inequalities | 61 | verifier)·to·check·the·existence·of·a·point·satisfying·a·specified·system·of·linear·inequalities |
| 17 | possibly·including·multiple·strict·inequalities. | 62 | possibly·including·multiple·strict·inequalities. |
| 18 | The·new·functions·are·particularly·important·for·the·development·of·related·software·packages·MinkSum·(by·Ch.·Weibel)·and·Gfan·(by·Anders·Jensen), | 63 | The·new·functions·are·particularly·important·for·the·development·of·related·software·packages·MinkSum·(by·Ch.·Weibel)·and·Gfan·(by·Anders·Jensen), |
| | |
| 19 | 1 | 64 | 1 |
| | |
| 20 | Introduction | 65 | Introduction |
| | |
| 21 | The·program·cddlib·is·an·efficient·implementation·[?]·of·the·double·description·Method·[?]·for | 66 | The·program·cddlib·is·an·efficient·implementation·[16]·of·the·double·description·Method·[19]·for |
| 22 | generating·all·vertices·(i.e.·extreme·points)·and·extreme·rays·of·a·general·convex·polyhedron·given | 67 | generating·all·vertices·(i.e.·extreme·points)·and·extreme·rays·of·a·general·convex·polyhedron·given |
| 23 | by·a·system·of·linear·inequalities: | 68 | by·a·system·of·linear·inequalities: |
| 24 | P·=·{x·=·(x1·,·x2·,·.·.·.·,·xd·)T·∈·Rd·:·b·−·Ax·≥·0} | 69 | P·=·{x·=·(x1·,·x2·,·.·.·.·,·xd·)T·∈·Rd·:·b·−·Ax·≥·0} |
| 25 | where·A·is·a·given·m·×·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 | 70 | where·A·is·a·given·m·×·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 |
| 26 | V-representation. | 71 | V-representation. |
| 27 | cddlib·is·a·C-library·version·of·the·previously·released·C-code·cdd/cdd+.·In·order·to·make | 72 | cddlib·is·a·C-library·version·of·the·previously·released·C-code·cdd/cdd+.·In·order·to·make |
| 28 | this·library·version,·a·large·part·of·the·cdd·source·(Version·0.61)·has·been·rewritten.·This·library | 73 | this·library·version,·a·large·part·of·the·cdd·source·(Version·0.61)·has·been·rewritten.·This·library |
| 29 | version·is·more·flexible·since·it·can·be·called·from·other·programs·in·C/C++.·Unlike·cdd/cdd+, | 74 | version·is·more·flexible·since·it·can·be·called·from·other·programs·in·C/C++.·Unlike·cdd/cdd+, |
| 30 | cddlib·can·handle·any·general·input·and·is·more·general.·Furthermore,·additional·functions·have | 75 | cddlib·can·handle·any·general·input·and·is·more·general.·Furthermore,·additional·functions·have |
| 31 | been·written·to·extend·its·functionality. | 76 | been·written·to·extend·its·functionality. |
| 32 | One·useful·feature·of·cddlib/cdd/cdd+·is·its·capability·of·handling·the·dual·(reverse)·problem | 77 | One·useful·feature·of·cddlib/cdd/cdd+·is·its·capability·of·handling·the·dual·(reverse)·problem |
| 33 | without·any·transformation·of·data.·The·dual·transformation·problem·of·a·V-representation·to | 78 | without·any·transformation·of·data.·The·dual·transformation·problem·of·a·V-representation·to |
| 34 | a·minimal·H-representation·and·is·often·called·the·(convex)·hull·problem.·More·explicitly,·is·to | 79 | a·minimal·H-representation·and·is·often·called·the·(convex)·hull·problem.·More·explicitly,·is·to |
| | |
| 35 | 1 | |
| | |
| 36 | .obtain·a·linear·inequality·representation·of·a·convex·polyhedron·given·as·the·Minkowski·sum·of·the | 80 | obtain·a·linear·inequality·representation·of·a·convex·polyhedron·given·as·the·Minkowski·sum·of·the |
| 37 | convex·hull·of·a·finite·set·of·points·and·the·nonnegative·hull·of·a·finite·set·of·points·in·Rd·: | 81 | convex·hull·of·a·finite·set·of·points·and·the·nonnegative·hull·of·a·finite·set·of·points·in·Rd·: |
| 38 | P·=·conv(v1·,·.·.·.·,·vn·)·+·nonneg(rn+1·,·.·.·.·,·rn+s·), | 82 | P·=·conv(v1·,·.·.·.·,·vn·)·+·nonneg(rn+1·,·.·.·.·,·rn+s·), |
| 39 | where·the·Minkowski·sum·of·two·subsets·S·and·T·of·Rd·is·defined·as | 83 | where·the·Minkowski·sum·of·two·subsets·S·and·T·of·Rd·is·defined·as |
| 40 | S·+·T·=·{s·+·t·|s·∈·S·and·t·∈·T·}. | 84 | S·+·T·=·{s·+·t·|s·∈·S·and·t·∈·T·}. |
| 41 | As·we·see·in·this·manual,·the·computation·can·be·done·in·straightforward·manner.·Unlike·the | 85 | As·we·see·in·this·manual,·the·computation·can·be·done·in·straightforward·manner.·Unlike·the |
| 42 | earlier·versions·of·cdd/cdd+·that·assume·certain·regularity·conditions·for·input,·cddlib·is·designed | 86 | earlier·versions·of·cdd/cdd+·that·assume·certain·regularity·conditions·for·input,·cddlib·is·designed |
| 43 | to·do·a·correct·transformation·for·any·general·input.·The·user·must·be·aware·of·the·fact·that | 87 | to·do·a·correct·transformation·for·any·general·input.·The·user·must·be·aware·of·the·fact·that |
| Offset 51, 25 lines modified | Offset 113, 27 lines modified |
| 51 | representations.·For·example,·a·line·segment·(1-dimensional·polytope)·in·R3·has·infinitely·many | 113 | representations.·For·example,·a·line·segment·(1-dimensional·polytope)·in·R3·has·infinitely·many |
| 52 | minimal·H-representations,·and·a·halfspace·in·the·same·space·has·infinitely·many·minimal·Vrepresentations.·cddlib·generates·merely·one·minimal·representation. | 114 | minimal·H-representations,·and·a·halfspace·in·the·same·space·has·infinitely·many·minimal·Vrepresentations.·cddlib·generates·merely·one·minimal·representation. |
| 53 | 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’s | 115 | 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’s |
| 54 | with·large·m·(say,·up·to·few·hundred·thousands)·and·small·d·(say,·up·to·100).·It·implements·a | 116 | with·large·m·(say,·up·to·few·hundred·thousands)·and·small·d·(say,·up·to·100).·It·implements·a |
| 55 | revised·dual·simplex·method·that·updates·(d·+·1)·×·(d·+·1)·matrix·for·a·pivot·operation. | 117 | revised·dual·simplex·method·that·updates·(d·+·1)·×·(d·+·1)·matrix·for·a·pivot·operation. |
| 56 | The·program·cddlib·has·an·I/O·routines·that·read·and·write·files·in·Polyhedra·format·which | 118 | The·program·cddlib·has·an·I/O·routines·that·read·and·write·files·in·Polyhedra·format·which |
| 57 | was·defined·by·David·Avis·and·the·author·in·1993,·and·has·been·updated·in·1997·and·1999.·The | 119 | was·defined·by·David·Avis·and·the·author·in·1993,·and·has·been·updated·in·1997·and·1999.·The |
| | 120 | 2 |
| | |
| 58 | program·called·lrs·and·lrslib·[?]·developed·by·David·Avis·is·a·C-implementation·of·the·reverse | 121 | .program·called·lrs·and·lrslib·[2]·developed·by·David·Avis·is·a·C-implementation·of·the·reverse |
| 59 | search·algorithm·[?]·for·the·same·enumeration·purpose,·and·it·conforms·to·Polyhedra·format·as | 122 | search·algorithm·[4]·for·the·same·enumeration·purpose,·and·it·conforms·to·Polyhedra·format·as |
| 60 | well.·Hopefully,·this·compatibility·of·the·two·programs·enables·users·to·use·both·programs·for·the | 123 | well.·Hopefully,·this·compatibility·of·the·two·programs·enables·users·to·use·both·programs·for·the |
| 61 | same·input·files·and·to·choose·whichever·is·useful·for·their·purposes.·From·our·experiences·with | 124 | same·input·files·and·to·choose·whichever·is·useful·for·their·purposes.·From·our·experiences·with |
|
Max diff block lines reached; 35156/41625 bytes (84.46%) of diff not shown.
|