| | | | |
| Offset 2, 84 lines modified | Offset 2, 19 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 | |
| 52 | Abstract | 8 | Abstract |
| | |
| 53 | This·is·a·reference·manual·for·cddlib-094.·The·manual·describes·the·library·functions·and | 9 | This·is·a·reference·manual·for·cddlib-094.·The·manual·describes·the·library·functions·and |
| 54 | data·types·implemented·in·the·cddlib·C-library·which·is·to·perform·fundamental·polyhedral | 10 | data·types·implemented·in·the·cddlib·C-library·which·is·to·perform·fundamental·polyhedral |
| 55 | computations·such·as·representation·conversions·and·linear·programming·in·both·floating-point | 11 | computations·such·as·representation·conversions·and·linear·programming·in·both·floating-point |
| | |
| 56 | 1 | |
| | |
| 57 | .and·GMP·rational·exact·arithmetic.·Please·read·the·accompanying·README·file·and·test | 12 | and·GMP·rational·exact·arithmetic.·Please·read·the·accompanying·README·file·and·test |
| 58 | programs·to·complement·the·manual. | 13 | programs·to·complement·the·manual. |
| 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 | 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 |
| 60 | point·of·an·H-polyhedron,·and·dd·ExistsRestrictedFace·(Farkas-type·alternative·theorem | 15 | point·of·an·H-polyhedron,·and·dd·ExistsRestrictedFace·(Farkas-type·alternative·theorem |
| 61 | verifier)·to·check·the·existence·of·a·point·satisfying·a·specified·system·of·linear·inequalities | 16 | verifier)·to·check·the·existence·of·a·point·satisfying·a·specified·system·of·linear·inequalities |
| 62 | possibly·including·multiple·strict·inequalities. | 17 | possibly·including·multiple·strict·inequalities. |
| 63 | The·new·functions·are·particularly·important·for·the·development·of·related·software·packages·MinkSum·(by·Ch.·Weibel)·and·Gfan·(by·Anders·Jensen), | 18 | The·new·functions·are·particularly·important·for·the·development·of·related·software·packages·MinkSum·(by·Ch.·Weibel)·and·Gfan·(by·Anders·Jensen), |
| | |
| Offset 97, 15 lines modified | Offset 32, 18 lines modified |
| 97 | this·library·version,·a·large·part·of·the·cdd·source·(Version·0.61)·has·been·rewritten.·This·library | 32 | this·library·version,·a·large·part·of·the·cdd·source·(Version·0.61)·has·been·rewritten.·This·library |
| 98 | version·is·more·flexible·since·it·can·be·called·from·other·programs·in·C/C++.·Unlike·cdd/cdd+, | 33 | version·is·more·flexible·since·it·can·be·called·from·other·programs·in·C/C++.·Unlike·cdd/cdd+, |
| 99 | cddlib·can·handle·any·general·input·and·is·more·general.·Furthermore,·additional·functions·have | 34 | cddlib·can·handle·any·general·input·and·is·more·general.·Furthermore,·additional·functions·have |
| 100 | been·written·to·extend·its·functionality. | 35 | been·written·to·extend·its·functionality. |
| 101 | One·useful·feature·of·cddlib/cdd/cdd+·is·its·capability·of·handling·the·dual·(reverse)·problem | 36 | One·useful·feature·of·cddlib/cdd/cdd+·is·its·capability·of·handling·the·dual·(reverse)·problem |
| 102 | without·any·transformation·of·data.·The·dual·transformation·problem·of·a·V-representation·to | 37 | without·any·transformation·of·data.·The·dual·transformation·problem·of·a·V-representation·to |
| 103 | a·minimal·H-representation·and·is·often·called·the·(convex)·hull·problem.·More·explicitly,·is·to | 38 | a·minimal·H-representation·and·is·often·called·the·(convex)·hull·problem.·More·explicitly,·is·to |
| | |
| | 39 | 1 |
| | |
| 104 | obtain·a·linear·inequality·representation·of·a·convex·polyhedron·given·as·the·Minkowski·sum·of·the | 40 | .obtain·a·linear·inequality·representation·of·a·convex·polyhedron·given·as·the·Minkowski·sum·of·the |
| 105 | convex·hull·of·a·finite·set·of·points·and·the·nonnegative·hull·of·a·finite·set·of·points·in·Rd·: | 41 | convex·hull·of·a·finite·set·of·points·and·the·nonnegative·hull·of·a·finite·set·of·points·in·Rd·: |
| 106 | P·=·conv(v1·,·.·.·.·,·vn·)·+·nonneg(rn+1·,·.·.·.·,·rn+s·), | 42 | P·=·conv(v1·,·.·.·.·,·vn·)·+·nonneg(rn+1·,·.·.·.·,·rn+s·), |
| 107 | where·the·Minkowski·sum·of·two·subsets·S·and·T·of·Rd·is·defined·as | 43 | where·the·Minkowski·sum·of·two·subsets·S·and·T·of·Rd·is·defined·as |
| 108 | S·+·T·=·{s·+·t·|s·∈·S·and·t·∈·T·}. | 44 | S·+·T·=·{s·+·t·|s·∈·S·and·t·∈·T·}. |
| 109 | As·we·see·in·this·manual,·the·computation·can·be·done·in·straightforward·manner.·Unlike·the | 45 | As·we·see·in·this·manual,·the·computation·can·be·done·in·straightforward·manner.·Unlike·the |
| 110 | earlier·versions·of·cdd/cdd+·that·assume·certain·regularity·conditions·for·input,·cddlib·is·designed | 46 | earlier·versions·of·cdd/cdd+·that·assume·certain·regularity·conditions·for·input,·cddlib·is·designed |
| 111 | to·do·a·correct·transformation·for·any·general·input.·The·user·must·be·aware·of·the·fact·that | 47 | to·do·a·correct·transformation·for·any·general·input.·The·user·must·be·aware·of·the·fact·that |
| Offset 113, 17 lines modified | Offset 51, 15 lines modified |
| 113 | representations.·For·example,·a·line·segment·(1-dimensional·polytope)·in·R3·has·infinitely·many | 51 | representations.·For·example,·a·line·segment·(1-dimensional·polytope)·in·R3·has·infinitely·many |
| 114 | minimal·H-representations,·and·a·halfspace·in·the·same·space·has·infinitely·many·minimal·Vrepresentations.·cddlib·generates·merely·one·minimal·representation. | 52 | minimal·H-representations,·and·a·halfspace·in·the·same·space·has·infinitely·many·minimal·Vrepresentations.·cddlib·generates·merely·one·minimal·representation. |
| 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 | 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 |
| 116 | with·large·m·(say,·up·to·few·hundred·thousands)·and·small·d·(say,·up·to·100).·It·implements·a | 54 | with·large·m·(say,·up·to·few·hundred·thousands)·and·small·d·(say,·up·to·100).·It·implements·a |
| 117 | revised·dual·simplex·method·that·updates·(d·+·1)·×·(d·+·1)·matrix·for·a·pivot·operation. | 55 | revised·dual·simplex·method·that·updates·(d·+·1)·×·(d·+·1)·matrix·for·a·pivot·operation. |
| 118 | The·program·cddlib·has·an·I/O·routines·that·read·and·write·files·in·Polyhedra·format·which | 56 | The·program·cddlib·has·an·I/O·routines·that·read·and·write·files·in·Polyhedra·format·which |
| 119 | was·defined·by·David·Avis·and·the·author·in·1993,·and·has·been·updated·in·1997·and·1999.·The | 57 | was·defined·by·David·Avis·and·the·author·in·1993,·and·has·been·updated·in·1997·and·1999.·The |
| 120 | 2 | |
| | |
| 121 | .program·called·lrs·and·lrslib·[?]·developed·by·David·Avis·is·a·C-implementation·of·the·reverse | 58 | program·called·lrs·and·lrslib·[?]·developed·by·David·Avis·is·a·C-implementation·of·the·reverse |
| 122 | search·algorithm·[?]·for·the·same·enumeration·purpose,·and·it·conforms·to·Polyhedra·format·as | 59 | search·algorithm·[?]·for·the·same·enumeration·purpose,·and·it·conforms·to·Polyhedra·format·as |
| 123 | well.·Hopefully,·this·compatibility·of·the·two·programs·enables·users·to·use·both·programs·for·the | 60 | well.·Hopefully,·this·compatibility·of·the·two·programs·enables·users·to·use·both·programs·for·the |
| 124 | same·input·files·and·to·choose·whichever·is·useful·for·their·purposes.·From·our·experiences·with | 61 | same·input·files·and·to·choose·whichever·is·useful·for·their·purposes.·From·our·experiences·with |
| 125 | relatively·large·problems,·the·two·methods·are·both·useful·and·perhaps·complementary·to·each | 62 | relatively·large·problems,·the·two·methods·are·both·useful·and·perhaps·complementary·to·each |
| 126 | other.·In·general,·the·program·cddlib·tends·to·be·efficient·for·highly·degenerate·inputs·and·the | 63 | other.·In·general,·the·program·cddlib·tends·to·be·efficient·for·highly·degenerate·inputs·and·the |
| 127 | program·rs·tends·to·be·efficient·for·nondegenerate·or·slightly·degenerate·problems. | 64 | program·rs·tends·to·be·efficient·for·nondegenerate·or·slightly·degenerate·problems. |
| 128 | Although·the·program·can·be·used·for·nondegenerate·inputs,·it·might·not·be·very·efficient. | 65 | Although·the·program·can·be·used·for·nondegenerate·inputs,·it·might·not·be·very·efficient. |
| Offset 144, 15 lines modified | Offset 80, 17 lines modified |
| 144 | Polyhedra·H-·and·V-Formats·(Version·1999) | 80 | Polyhedra·H-·and·V-Formats·(Version·1999) |
| | |
| 145 | Every·convex·polyhedron·has·two·representations,·one·as·the·intersection·of·finite·halfspaces·and | 81 | Every·convex·polyhedron·has·two·representations,·one·as·the·intersection·of·finite·halfspaces·and |
| 146 | the·other·as·Minkowski·sum·of·the·convex·hull·of·finite·points·and·the·nonnegative·hull·of·finite | 82 | the·other·as·Minkowski·sum·of·the·convex·hull·of·finite·points·and·the·nonnegative·hull·of·finite |
| 147 | directions.·These·are·called·H-representation·and·V-representation,·respectively. | 83 | directions.·These·are·called·H-representation·and·V-representation,·respectively. |
|
Max diff block lines reached; 30410/36812 bytes (82.61%) of diff not shown.
|