==========================================================================
Help file for CDDMEX
CDDMEX is a Matlab MEX file interface (authors: Mato Baotic, Fabio Torrisi),
obtained by linking CDD library CDDLIB-093 (author: Komei Fukuda), which
allows calls to some of CDD functions from within MATLAB.
CDD is a software package written by K. Fukuda which boasts a wide array
of efficient algorithms for many polytope manipulations as well as a fast
LP solver. The full CDD library is free and availible from:
http://www.cs.mcgill.ca/~fukuda/soft/cdd_home/cdd.html
Version: cddmex v1.0
cddlib v0.93
See the bottom of this file for more details.
==========================================================================
Syntax: outstruct=cddmex(action,instruct)
action: 'hull' Convex hull of a V polyhedron
'extreme' Vertex/ray enumeration of an H polyhedron
'reduce_h' Minimal H representation (of an H polyhedron)
'reduce_v' Minimal V representation (of a V polyhedron)
'solve_lp' Solve a Linear Program using Criss-Cross method
'solve_lp_DS' Solve a Linear Program using Dual-Simplex method
'version' Version of the mex function
Further info: see CDDMEX.C
Not documented functions:
'copy_v' Simple copy of an H polyhedron
'copy_h' Simple copy of a V polyhedron
'v_hull_extreme' ???
'adj_extreme' Extreme points and adjecancy list of an H polyhedron
'find_interior' Interior point of an H polyhedron
Not compiled functions:
'adjecancy' Adjacency list of a V polyhedron
Note that V has to be in a minimal representation!
Example: Find the extreme points/rays of P={x: A1*x=B1, A2*x<=B1}
A1=[1 1 1];B1=[1];
A2=[eye(3);-eye(3)];B2=[1;1;1;2;2;2];
H=struct('A',[A1;A2],'B',[B1;B2],'lin',(1:size(B1,1))');
% H.lin=indices of equality constraints
V=cddmex('extreme',H);
% The rows of V.V are the extreme points of P
Example: Find the convex hull of v1,v2,v3
V=struct('V',[v1';v2';v3']);
H=cddmex('hull',V);
Example: Find minimal H representation
A1=[-1 0; 0 -1; 1 0; 0 1; 1 1];B1=[0;0;1;1;1];
H1=struct('A',A1,'B',B1);
[Hred]=cddmex('reduce_h',H1);
% Hred.A * x <= Hred.B is a minimal H representation
[Hred,ind_redrows]=cddmex('reduce_h',H1);
% ind_redrows are the indices of redundant rows
% Note: if H1 is empty polyhedron, then Hred
% containes irreducibly incosistent set (IIS)
Example: Find minimal V representation
V1=[0 0; 0 1; 1 0; 1 1; 0.2 0.8; 0.7 0.3];
V1=struct('V',V1);
% each row of V1.V is a vertex
[Vred]=cddmex('reduce_v',V1);
% Vred.V is a minimal V representation
[Vred,ind_redvert]=cddmex('reduce_v',V1);
% ind_redvert are the indices of redundant vertices
Example: Solve a Linear Program
Syntax
OUT=cddmex('solve_lp',IN)
solves problem
min IN.obj*x
x
s.t. IN.A*x <= IN.B
IN.A(IN.lin,:) x == IN.B(IN.lin)
where
IN - input structure
IN.A - constraints matrix
IN.B - constraints matrix
IN.obj - objective function
IN.lin - indices of equality constraints
OUT - structure with solution (similiar to lpsolve)
OUT.xopt - primal solution
OUT.lambda - dual solution
OUT.how - Fukuda's code for LP solution status
0 = dd_LPSundecided,
1 = dd_Optimal
2 = dd_Incosistent
3 = dd_DualIncosistent
4 = dd_StrucIncosistent
5 = dd_StrucDualIncosistent
6 = dd_Unbounded
7 = dd_DualUnbounded
OUT.objlp - optimal value
Note: CrissCross algorithm is used when solving LP.
Example
objective=[-1 1];
A1=[1 1; -1 0; 0 -1];
B1=[1; 0; 0];
IN=struct('obj',objective,'A',A1,'B',B1);
OUT = cddmex('solve_lp',IN);
OUT =
xopt: [1 0]
lambda: [-1 0 -2]
how: 1
objlp: -1
Note: the projection function is only available in CDDMEX.M. A projection
can be obtained here by (1) vertex enumeration, (2) projection of vertices,
(3) hull of projected vertices. Example:
H=struct('A',A1,'B',B1);
V=cddmex('extreme',H);
Vproj.V=V.V(:,1:2); % Project over the first two coordinates
Hproj=cddmex('hull',Vproj); % Get the projection
==============================================================================
/* The cdd library cddlib-093a was written by
Komei Fukuda, fukuda@ifor.math.ethz.ch
Version 0.93, August 11, 2003
Standard ftp site: ftp.ifor.math.ethz.ch, Directory: pub/fukuda/cdd
*/
/* cddlib.c : C-Implementation of the double description method for
computing all vertices and extreme rays of the polyhedron
P= {x : b - A x >= 0}.
Please read COPYING (GNU General Public Licence) and
the manual cddlibman.tex for detail.
*/
/* This program is free software; you can redistribute it and/or modify
it under the terms of the GNU General Public License as published by
the Free Software Foundation; either version 2 of the License, or
(at your option) any later version.
This program is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
GNU General Public License for more details.
You should have received a copy of the GNU General Public License
along with this program; if not, write to the Free Software
Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
*/
===============================================================================
History:
cddmex.c v0.1, An initial Matlab MEX wrapper for cdd library written by
Fabio Torrisi (torrisi@control.ee.ethz.ch) and
Mato Baotic (baotic@control.ee.ethz.ch),
Zurich, December 2002.
cddmex.c v1.0, Revision update by Mato Baotic, Zurich, October 2003.0001 %========================================================================== 0002 % Help file for CDDMEX 0003 % 0004 % CDDMEX is a Matlab MEX file interface (authors: Mato Baotic, Fabio Torrisi), 0005 % obtained by linking CDD library CDDLIB-093 (author: Komei Fukuda), which 0006 % allows calls to some of CDD functions from within MATLAB. 0007 % 0008 % CDD is a software package written by K. Fukuda which boasts a wide array 0009 % of efficient algorithms for many polytope manipulations as well as a fast 0010 % LP solver. The full CDD library is free and availible from: 0011 % http://www.cs.mcgill.ca/~fukuda/soft/cdd_home/cdd.html 0012 % 0013 % Version: cddmex v1.0 0014 % cddlib v0.93 0015 % 0016 % See the bottom of this file for more details. 0017 %========================================================================== 0018 % 0019 % Syntax: outstruct=cddmex(action,instruct) 0020 % 0021 % action: 'hull' Convex hull of a V polyhedron 0022 % 'extreme' Vertex/ray enumeration of an H polyhedron 0023 % 'reduce_h' Minimal H representation (of an H polyhedron) 0024 % 'reduce_v' Minimal V representation (of a V polyhedron) 0025 % 'solve_lp' Solve a Linear Program using Criss-Cross method 0026 % 'solve_lp_DS' Solve a Linear Program using Dual-Simplex method 0027 % 'version' Version of the mex function 0028 % 0029 % Further info: see CDDMEX.C 0030 % 0031 % Not documented functions: 0032 % 'copy_v' Simple copy of an H polyhedron 0033 % 'copy_h' Simple copy of a V polyhedron 0034 % 'v_hull_extreme' ??? 0035 % 'adj_extreme' Extreme points and adjecancy list of an H polyhedron 0036 % 'find_interior' Interior point of an H polyhedron 0037 % 0038 % Not compiled functions: 0039 % 'adjecancy' Adjacency list of a V polyhedron 0040 % Note that V has to be in a minimal representation! 0041 % 0042 % 0043 % Example: Find the extreme points/rays of P={x: A1*x=B1, A2*x<=B1} 0044 % 0045 % A1=[1 1 1];B1=[1]; 0046 % A2=[eye(3);-eye(3)];B2=[1;1;1;2;2;2]; 0047 % H=struct('A',[A1;A2],'B',[B1;B2],'lin',(1:size(B1,1))'); 0048 % % H.lin=indices of equality constraints 0049 % V=cddmex('extreme',H); 0050 % % The rows of V.V are the extreme points of P 0051 % 0052 % Example: Find the convex hull of v1,v2,v3 0053 % 0054 % V=struct('V',[v1';v2';v3']); 0055 % H=cddmex('hull',V); 0056 % 0057 % Example: Find minimal H representation 0058 % 0059 % A1=[-1 0; 0 -1; 1 0; 0 1; 1 1];B1=[0;0;1;1;1]; 0060 % H1=struct('A',A1,'B',B1); 0061 % [Hred]=cddmex('reduce_h',H1); 0062 % % Hred.A * x <= Hred.B is a minimal H representation 0063 % [Hred,ind_redrows]=cddmex('reduce_h',H1); 0064 % % ind_redrows are the indices of redundant rows 0065 % % Note: if H1 is empty polyhedron, then Hred 0066 % % containes irreducibly incosistent set (IIS) 0067 % 0068 % Example: Find minimal V representation 0069 % 0070 % V1=[0 0; 0 1; 1 0; 1 1; 0.2 0.8; 0.7 0.3]; 0071 % V1=struct('V',V1); 0072 % % each row of V1.V is a vertex 0073 % [Vred]=cddmex('reduce_v',V1); 0074 % % Vred.V is a minimal V representation 0075 % [Vred,ind_redvert]=cddmex('reduce_v',V1); 0076 % % ind_redvert are the indices of redundant vertices 0077 % 0078 % 0079 % Example: Solve a Linear Program 0080 % Syntax 0081 % OUT=cddmex('solve_lp',IN) 0082 % 0083 % solves problem 0084 % min IN.obj*x 0085 % x 0086 % s.t. IN.A*x <= IN.B 0087 % IN.A(IN.lin,:) x == IN.B(IN.lin) 0088 % 0089 % where 0090 % IN - input structure 0091 % IN.A - constraints matrix 0092 % IN.B - constraints matrix 0093 % IN.obj - objective function 0094 % IN.lin - indices of equality constraints 0095 % 0096 % OUT - structure with solution (similiar to lpsolve) 0097 % OUT.xopt - primal solution 0098 % OUT.lambda - dual solution 0099 % OUT.how - Fukuda's code for LP solution status 0100 % 0 = dd_LPSundecided, 0101 % 1 = dd_Optimal 0102 % 2 = dd_Incosistent 0103 % 3 = dd_DualIncosistent 0104 % 4 = dd_StrucIncosistent 0105 % 5 = dd_StrucDualIncosistent 0106 % 6 = dd_Unbounded 0107 % 7 = dd_DualUnbounded 0108 % OUT.objlp - optimal value 0109 % 0110 % Note: CrissCross algorithm is used when solving LP. 0111 % 0112 % Example 0113 % objective=[-1 1]; 0114 % A1=[1 1; -1 0; 0 -1]; 0115 % B1=[1; 0; 0]; 0116 % IN=struct('obj',objective,'A',A1,'B',B1); 0117 % 0118 % OUT = cddmex('solve_lp',IN); 0119 % 0120 % OUT = 0121 % xopt: [1 0] 0122 % lambda: [-1 0 -2] 0123 % how: 1 0124 % objlp: -1 0125 % 0126 % 0127 % Note: the projection function is only available in CDDMEX.M. A projection 0128 % can be obtained here by (1) vertex enumeration, (2) projection of vertices, 0129 % (3) hull of projected vertices. Example: 0130 % 0131 % H=struct('A',A1,'B',B1); 0132 % V=cddmex('extreme',H); 0133 % Vproj.V=V.V(:,1:2); % Project over the first two coordinates 0134 % Hproj=cddmex('hull',Vproj); % Get the projection 0135 % 0136 % 0137 %============================================================================== 0138 % 0139 % /* The cdd library cddlib-093a was written by 0140 % Komei Fukuda, fukuda@ifor.math.ethz.ch 0141 % Version 0.93, August 11, 2003 0142 % Standard ftp site: ftp.ifor.math.ethz.ch, Directory: pub/fukuda/cdd 0143 % */ 0144 % 0145 % /* cddlib.c : C-Implementation of the double description method for 0146 % computing all vertices and extreme rays of the polyhedron 0147 % P= {x : b - A x >= 0}. 0148 % Please read COPYING (GNU General Public Licence) and 0149 % the manual cddlibman.tex for detail. 0150 % */ 0151 % 0152 % /* This program is free software; you can redistribute it and/or modify 0153 % it under the terms of the GNU General Public License as published by 0154 % the Free Software Foundation; either version 2 of the License, or 0155 % (at your option) any later version. 0156 % 0157 % This program is distributed in the hope that it will be useful, 0158 % but WITHOUT ANY WARRANTY; without even the implied warranty of 0159 % MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 0160 % GNU General Public License for more details. 0161 % 0162 % You should have received a copy of the GNU General Public License 0163 % along with this program; if not, write to the Free Software 0164 % Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA. 0165 % */ 0166 %=============================================================================== 0167 % 0168 % History: 0169 % cddmex.c v0.1, An initial Matlab MEX wrapper for cdd library written by 0170 % Fabio Torrisi (torrisi@control.ee.ethz.ch) and 0171 % Mato Baotic (baotic@control.ee.ethz.ch), 0172 % Zurich, December 2002. 0173 % 0174 % cddmex.c v1.0, Revision update by Mato Baotic, Zurich, October 2003. 0175 0176