cddmex.m

CheckMate is a MATLAB-based tool for modeling, simulating and investigating properties of hybrid dyn

%==========================================================================
% 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
%          '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, [e-mail]
%    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 ([e-mail]) and
% 		 Mato Baotic ([e-mail]),
%		 Zurich, December 2002.
%
% cddmex.c v1.0, Revision update by Mato Baotic, Zurich, October 2003.