HDK
UT_LinearProgram.h
Go to the documentation of this file.
1 /*
2  * PROPRIETARY INFORMATION. This software is proprietary to
3  * Side Effects Software Inc., and is not to be reproduced,
4  * transmitted, or disclosed in any way without written permission.
5  *
6  */
7
8 #ifndef __UT_LinearProgram_h__
9 #define __UT_LinearProgram_h__
10
11 #include "UT_API.h"
12 typedef enum {
18
19 #include "UT_Vector.h"
20 #include "UT_Matrix.h"
21
22 // This class implements a linear program solver using the simplex method.
23 // The solver algorithm is from "Numerical Recipes in C, Second Edition"
24 // by W.H. Press, S.A. Teukolsky, W.T. Vetterling, and B.P. Flannery.
25
27 public:
29  virtual ~UT_LinearProgram();
30
31  // Set up the linear programming problem. Input number of constraints
32  // or <= type, >= type, and = type, and the number of values in the
33  // result. Input matrix has resultSize+1 columns and total num rules + 1
34  // rows. First column is equation constants, subsequent columns are
35  // coefficients in constraint equations. The first row is the objective
36  // function, followed by rows that express the <= constraints, then >=
37  // constraints, then = constraints. Input matrix should start at (1,1).
38  // Returns 0 if there was some problem with the input (matrix wrong size),
39  // otherwise returns 1.
40  int setupProblem( int leRules, int geRules,
41  int equalRules, int resultSize,
42  UT_MatrixF *input, fpreal tolerance );
43
44  // Solve the problem set up in setupProblem. Returns UT_LPERROR if no
45  // problem has been set up, or if any of the constants (first column)
46  // in the matrix are negative. Modifies the input matrix.
47  UT_LPSolutionType minimize();
48  UT_LPSolutionType maximize();
49
50  // Fills result with the solution vector. Returns 0 if there has been
51  // no problem set up, or the problem hasn't been solved, or did not
52  // produce an optimal solution (output would be meaningless). Otherwise
53  // it returns 1. This function is required because after calling solve(),
54  // the input matrix requires some small massaging to get the output vector.
55  int getSolution( UT_Vector *result );
56
57 private:
58  // Performs the solution for both minimize and maximize
60
61  void destroyWorkingVectors();
62  void createWorkingVectors();
63  void findPivotCol( float *factors, int *indices,
64  int maxIndex, int abs, int findMax,
65  int &pivotCol, float &factor );
66  void findPivotRow( int &pivotRow, int pivotCol );
67  void doPivot( int doAux, int row, int col );
68
69  int myMaximize;
70  int myNumLERules; // Number of rules of each
71  int myNumGERules; // type. Less than, greater
72  int myNumEqualRules; // than, and equality.
73  int myNumRules; // Total number of rules
74  int myResultSize; // Size of result vector
75  int mySolved; // Set to 1 when solve() called
76  float myTolerance; // Tolerance value
77  UT_MatrixF *myInput; // Input array
78  float *myAuxObj; // Auxiliary objective function
79  int *myL1, *myL3; // Temp vectors
80  int *myRowIndices; // Row number of each variable
81  int *myColumnIndices; // Column number of each var
82 };
83
84 #endif
GLsizei GLenum const void * indices
Definition: glcorearb.h:405
#define UT_API
Definition: UT_API.h:13