numeric-lib/slack_matrix.h
```00001 /*
00002  * slack_matrix.h
00003  *
00004  *  Created on: Dec 8, 2008
00005  *      Author: isil
00006  *
00007  *  Implements a slack matrix used in the Simplex algorithm.
00008  */
00009
00010 #ifndef SLACK_MATRIX_H_
00011 #define SLACK_MATRIX_H_
00012
00013 #include "matrix.h"
00014 #include <set>
00015 #include <map>
00016 #include <unordered_set>
00017 using namespace std;
00018 #include "Equation.h"
00019 #include "Matrix.h"
00020
00021 typedef unordered_set<Equation*, hash<Equation*>, equation_eq> eq_set;
00022
00023 class slack_matrix {
00024 private:
00025         matrix* sm;
00026
00027         vector<string> & orig_vars;
00028
00029         /*
00030          * Total number of variables
00031          */
00032         int num_vars;
00033
00034         /*
00035          * Number of slack variables
00036          */
00037         int num_slack_vars;
00038
00039         /*
00040          * Mapping from variable indices in the original matrix
00041          * to their indices in the slack matrix
00042          */
00043         int *index_mapping;
00044
00045         /*
00046          * Number of rows, including objective function
00047          */
00048         int num_rows;
00049
00050         /*
00051          * Mapping from indices in the slack matrix to their index
00052          * in the original matrix
00053          */
00054         int* reverse_index_mapping;
00055
00056         /*
00057          * Variable indices (in the original matrix) that have greater
00058          * than or equal to zero constraints.
00059          */
00060         bool* geqz_constraints;
00061
00062
00063
00064
00065 public:
00066         slack_matrix(Matrix & m);
00067         slack_matrix(slack_matrix & m);
00068
00069         inline bignum get(int r, int c)
00070         {
00071                 return sm->get(r, c);
00072         }
00073
00074         inline bignum get_objective_coefficient(int c)
00075         {
00076                 return sm->get(num_rows-1, c);
00077         }
00078
00079         inline bignum get_objective_constant()
00080         {
00081                 return sm->get(num_rows-1, num_vars);
00082         }
00083
00084         inline void set_objective_coefficient(int c, bignum val)
00085         {
00086                 sm->set(num_rows-1, c, val);
00087         }
00088
00089         inline vector<string>& get_orig_vars()
00090         {
00091                 return orig_vars;
00092         }
00093
00094
00095         inline void set(int r, int c, bignum e)
00096         {
00097                 sm->set(r, c, e);
00098         }
00099
00100         inline int num_constraints()
00101         {
00102                 return num_rows-1;
00103         }
00104
00105         inline int num_variables()
00106         {
00107                 return num_vars;
00108         }
00109
00110         inline int num_actual_vars()
00111         {
00112                 return orig_vars.size();
00113         }
00114
00115         inline int get_actual_index(int slack_index)
00116         {
00117                 return reverse_index_mapping[slack_index];
00118         }
00119         inline int get_slack_index(int actual_index)
00120         {
00121                 return index_mapping[actual_index];
00122         }
00123
00124         inline bool is_actual_var(int index)
00125         {
00126                 return reverse_index_mapping[index]!=-1;
00127         }
00128
00129         inline bool is_slack_var(int index)
00130         {
00131                 return index<num_slack_vars;
00132         }
00133         inline bool is_primed_var(int index)
00134         {
00135                 return !is_slack_var(index) && !is_actual_var(index);
00136         }
00137         inline int get_principal_var(int index)
00138         {
00139                 if(is_slack_var(index)) return -1;
00140                 if(is_actual_var(index)) return index;
00141                 return  index-1;
00142
00143         }
00144
00145         inline bignum get_constant(int r)
00146         {
00147                 return sm->get_constant(r);
00148         }
00149         inline void set_constant(int r, int val)
00150         {
00151                 sm->set_constant(r, val);
00152         }
00153
00154         inline int get_pivot(int r)
00155         {
00156                 return sm->get_pivot(r);
00157         }
00158         inline void set_pivot(int r, int pivot)
00159         {
00160                 sm->set_pivot(r, pivot);
00161         }
00162         inline void multiply_row(int r, bignum factor)
00163         {
00164                 sm->multiply_row(r, factor);
00165         }
00166
00167         inline void pivot(int r, int c)
00168         {
00169                 sm->pivot(r, c, true);
00170         }
00171
00172         string get_name(int c);
00173         string to_string();
00174
00175
00176         inline int get_first_positive_index_obj_fun_row()
00177         {
00178                 return sm->get_first_positive_index(num_rows-1);
00179         }
00180
00181
00182
00183
00184         friend ostream& operator <<(ostream &os,const slack_matrix &obj);
00185
00186         ~slack_matrix();
00187
00188
00189
00190
00191 private:
00192         void populate_slack_matrix(Matrix& m);
00193         void construct_index_mapping(Matrix& m);
00194         void init_geqz_constraints(Matrix& m);
00195         void append(long int i, string & s);
00196         string int_to_string(long int i);
00197 };
00198
00199 #endif /* SLACK_MATRIX_H_ */
```