| | | | |
| Offset 2, 19 lines modified | Offset 2, 84 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 | 1 |
| | |
| | 10 | 2·Polyhedra·H-·and·V-Formats·(Version·1999) |
| | |
| | 11 | 2 |
| | |
| | 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 | 6 |
| | 29 | 7 |
| | 30 | 7 |
| | 31 | 10 |
| | 32 | 10 |
| | 33 | 11 |
| | 34 | 11 |
| | 35 | 12 |
| | 36 | 12 |
| | 37 | 13 |
| | 38 | 13 |
| | 39 | 14 |
| | 40 | 14 |
| | 41 | 15 |
| | |
| | 42 | 5·An·Extension·of·the·CDD·Library·in·GMP·mode |
| | |
| | 43 | 15 |
| | |
| | 44 | 6·Examples |
| | |
| | 45 | 15 |
| | |
| | 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), |
| | |
| Offset 32, 18 lines modified | Offset 97, 15 lines modified |
| 32 | this·library·version,·a·large·part·of·the·cdd·source·(Version·0.61)·has·been·rewritten.·This·library | 97 | this·library·version,·a·large·part·of·the·cdd·source·(Version·0.61)·has·been·rewritten.·This·library |
| 33 | version·is·more·flexible·since·it·can·be·called·from·other·programs·in·C/C++.·Unlike·cdd/cdd+, | 98 | version·is·more·flexible·since·it·can·be·called·from·other·programs·in·C/C++.·Unlike·cdd/cdd+, |
| 34 | cddlib·can·handle·any·general·input·and·is·more·general.·Furthermore,·additional·functions·have | 99 | cddlib·can·handle·any·general·input·and·is·more·general.·Furthermore,·additional·functions·have |
| 35 | been·written·to·extend·its·functionality. | 100 | been·written·to·extend·its·functionality. |
| 36 | One·useful·feature·of·cddlib/cdd/cdd+·is·its·capability·of·handling·the·dual·(reverse)·problem | 101 | One·useful·feature·of·cddlib/cdd/cdd+·is·its·capability·of·handling·the·dual·(reverse)·problem |
| 37 | without·any·transformation·of·data.·The·dual·transformation·problem·of·a·V-representation·to | 102 | without·any·transformation·of·data.·The·dual·transformation·problem·of·a·V-representation·to |
| 38 | a·minimal·H-representation·and·is·often·called·the·(convex)·hull·problem.·More·explicitly,·is·to | 103 | a·minimal·H-representation·and·is·often·called·the·(convex)·hull·problem.·More·explicitly,·is·to |
| | |
| 39 | 1 | |
| | |
| 40 | .obtain·a·linear·inequality·representation·of·a·convex·polyhedron·given·as·the·Minkowski·sum·of·the | 104 | obtain·a·linear·inequality·representation·of·a·convex·polyhedron·given·as·the·Minkowski·sum·of·the |
| 41 | convex·hull·of·a·finite·set·of·points·and·the·nonnegative·hull·of·a·finite·set·of·points·in·Rd·: | 105 | convex·hull·of·a·finite·set·of·points·and·the·nonnegative·hull·of·a·finite·set·of·points·in·Rd·: |
| 42 | P·=·conv(v1·,·.·.·.·,·vn·)·+·nonneg(rn+1·,·.·.·.·,·rn+s·), | 106 | P·=·conv(v1·,·.·.·.·,·vn·)·+·nonneg(rn+1·,·.·.·.·,·rn+s·), |
| 43 | where·the·Minkowski·sum·of·two·subsets·S·and·T·of·Rd·is·defined·as | 107 | where·the·Minkowski·sum·of·two·subsets·S·and·T·of·Rd·is·defined·as |
| 44 | S·+·T·=·{s·+·t·|s·∈·S·and·t·∈·T·}. | 108 | S·+·T·=·{s·+·t·|s·∈·S·and·t·∈·T·}. |
| 45 | As·we·see·in·this·manual,·the·computation·can·be·done·in·straightforward·manner.·Unlike·the | 109 | As·we·see·in·this·manual,·the·computation·can·be·done·in·straightforward·manner.·Unlike·the |
| 46 | earlier·versions·of·cdd/cdd+·that·assume·certain·regularity·conditions·for·input,·cddlib·is·designed | 110 | earlier·versions·of·cdd/cdd+·that·assume·certain·regularity·conditions·for·input,·cddlib·is·designed |
| 47 | to·do·a·correct·transformation·for·any·general·input.·The·user·must·be·aware·of·the·fact·that | 111 | 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 |
| 62 | relatively·large·problems,·the·two·methods·are·both·useful·and·perhaps·complementary·to·each | 125 | relatively·large·problems,·the·two·methods·are·both·useful·and·perhaps·complementary·to·each |
| 63 | other.·In·general,·the·program·cddlib·tends·to·be·efficient·for·highly·degenerate·inputs·and·the | 126 | other.·In·general,·the·program·cddlib·tends·to·be·efficient·for·highly·degenerate·inputs·and·the |
| 64 | program·rs·tends·to·be·efficient·for·nondegenerate·or·slightly·degenerate·problems. | 127 | program·rs·tends·to·be·efficient·for·nondegenerate·or·slightly·degenerate·problems. |
| 65 | Although·the·program·can·be·used·for·nondegenerate·inputs,·it·might·not·be·very·efficient. | 128 | Although·the·program·can·be·used·for·nondegenerate·inputs,·it·might·not·be·very·efficient. |
| 66 | For·nondegenerate·inputs,·other·available·programs,·such·as·the·reverse·search·code·lrs·or·qhull | 129 | For·nondegenerate·inputs,·other·available·programs,·such·as·the·reverse·search·code·lrs·or·qhull |
| 67 | (developed·by·the·Geometry·Center),·might·be·more·efficient.·See·Section·??·for·pointers·to·these | 130 | (developed·by·the·Geometry·Center),·might·be·more·efficient.·See·Section·8·for·pointers·to·these |
| 68 | codes.·The·paper·[?]·contains·many·interesting·results·on·polyhedral·computation·and·experimental | 131 | codes.·The·paper·[3]·contains·many·interesting·results·on·polyhedral·computation·and·experimental |
| 69 | results·on·cdd+,·lrs,·qhull·and·porta. | 132 | results·on·cdd+,·lrs,·qhull·and·porta. |
| 70 | This·program·can·be·distributed·freely·under·the·GNU·GENERAL·PUBLIC·LICENSE.·Please | 133 | This·program·can·be·distributed·freely·under·the·GNU·GENERAL·PUBLIC·LICENSE.·Please |
| 71 | read·the·file·COPYING·carefully·before·using. | 134 | read·the·file·COPYING·carefully·before·using. |
|
Max diff block lines reached; 33330/40149 bytes (83.02%) of diff not shown.
|