Added cddlib-094h from http://www.inf.ethz.ch/personal/fukudak/cdd_home/
Change-Id: I64519509269e434b1b9ea87c3fe0805e711c0ac9
diff --git a/third_party/cddlib/src/testlp1.c b/third_party/cddlib/src/testlp1.c
new file mode 100644
index 0000000..d962bfb
--- /dev/null
+++ b/third_party/cddlib/src/testlp1.c
@@ -0,0 +1,132 @@
+/* testlp1.c: Main test program to call the cdd lp library
+ written by Komei Fukuda, fukuda@ifor.math.ethz.ch
+ Version 0.94, August 4, 2005
+ Standard ftp site: ftp.ifor.math.ethz.ch, Directory: pub/fukuda/cdd
+*/
+
+/* 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.
+*/
+
+#include "setoper.h"
+#include "cdd.h"
+#include <stdio.h>
+#include <stdlib.h>
+#include <time.h>
+#include <math.h>
+#include <string.h>
+
+FILE *reading, *writing;
+
+int main(int argc, char *argv[])
+{
+ /* The original LP data m x n matrix
+ = | b -A |
+ | c0 c^T |,
+
+ where the LP to be solved is to
+ maximize c^T x + c0
+ subj. to
+ A x <= b.
+ */
+
+ dd_ErrorType error=dd_NoError;
+ dd_MatrixPtr M,G;
+ dd_LPSolverType solver=dd_DualSimplex; /* either DualSimplex or CrissCross */
+ dd_LPPtr lp; /* pointer to LP data structure that is not visible by user. */
+ dd_LPSolutionPtr lps1;
+ dd_colrange j;
+ dd_rowset ImL, Lbasis;
+
+ dd_PolyhedraPtr poly;
+ dd_DataFileType inputfile;
+ int ans;
+
+ dd_set_global_constants(); /* First, this must be called once to use cddlib. */
+
+ printf("Welcome to cddlib %s\n",dd_DDVERSION);
+
+ while (error==dd_NoError) {
+
+/* Input an LP using the cdd library */
+ dd_SetInputFile(&reading,inputfile,&error);
+ if (error!=dd_NoError) goto _L99;
+ M=dd_PolyFile2Matrix(reading, &error);
+ if (error!=dd_NoError) goto _L99;
+ /* dd_WriteMatrix(stdout, M); */
+ lp=dd_Matrix2LP(M, &error);
+ if (error!=dd_NoError) goto _L99;
+
+
+/* Solve the LP by cdd LP solver. */
+ printf("\n--- Running dd_LPSolve ---\n");
+ dd_LPSolve(lp,solver,&error);
+ if (error!=dd_NoError) goto _L99;
+
+ /* Write the LP solutions by cdd LP reporter. */
+ dd_WriteLPResult(stdout, lp, error);
+
+/* Generate all vertices of the feasible reagion */
+ printf("\nDo you want to compute the generator representation (y/n)? ");
+ ans=getchar();
+ if (ans=='y' || ans=='Y'){
+ poly=dd_DDMatrix2Poly(M, &error);
+ G=dd_CopyGenerators(poly);
+ printf("\nGenerators (All the vertices of the feasible region if bounded.)\n");
+ dd_WriteMatrix(stdout,G);
+
+ /* Free allocated spaces. */
+ dd_FreeMatrix(G);
+ dd_FreePolyhedra(poly);
+ }
+
+/* Find an interior point with cdd LP library. */
+ printf("\nDo you want to find a relative interior point (y/n)? ");
+ ans=getchar(); ans=getchar();
+ if (ans=='y' || ans=='Y'){
+ printf("\n--- Running dd_FindRelativeInteriorPoint ---\n");
+ dd_FindRelativeInterior(M, &ImL, &Lbasis, &lps1, &error);
+ if (error!=dd_NoError) goto _L99;
+
+ /* Write an interior point. */
+ if (dd_Positive(lps1->optvalue)){
+ printf("A relative interior point found: (");
+ for (j=1; j <(lps1->d)-1; j++) {
+ dd_WriteNumber(stdout,lps1->sol[j]);
+ }
+ printf(")\nThe dimension of the region = ");
+ printf("%ld\n",M->colsize-set_card(Lbasis)-1);
+ if (set_card(ImL)>0) {
+ printf("Implicit equations: "); set_write(ImL); printf("\n");
+ }
+ } else {
+ printf("The feasible region is empty.\n");
+ }
+ dd_FreeLPSolution(lps1);
+ set_free(ImL);
+ set_free(Lbasis);
+ }
+
+/* Free allocated spaces. */
+ dd_FreeMatrix(M);
+ dd_FreeLPData(lp);
+ }
+_L99:;
+ fclose(reading);
+ if (error!=dd_NoError) dd_WriteErrorMessages(stdout, error);
+ dd_free_global_constants(); /* At the end, this should be called. */
+ return 0;
+}
+
+/* end of testlp1.c */