-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathlp_matrix.h
257 lines (217 loc) · 11.9 KB
/
lp_matrix.h
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
#ifndef HEADER_lp_matrix
#define HEADER_lp_matrix
#include "lp_types.h"
#include "lp_utils.h"
/* Sparse matrix element (ordered columnwise) */
typedef struct _MATitem
{
int rownr;
int colnr;
REAL value;
} MATitem;
/* Constants for matrix product rounding options */
#define MAT_ROUNDNONE 0
#define MAT_ROUNDABS 1
#define MAT_ROUNDREL 2
#define MAT_ROUNDABSREL (MAT_ROUNDABS + MAT_ROUNDREL)
#define MAT_ROUNDRC 4
#define MAT_ROUNDRCMIN 1.0 /* lp->epspivot */
#if 1
#define MAT_ROUNDDEFAULT MAT_ROUNDREL /* Typically increases performance */
#else
#define MAT_ROUNDDEFAULT MAT_ROUNDABS /* Probably gives more precision */
#endif
/* Compiler option development features */
/*#define DebugInv*/ /* Report array values at factorization/inversion */
#define NoLoopUnroll /* Do not do loop unrolling */
#define DirectArrayOF /* Reference lp->obj[] array instead of function call */
/* Matrix column access macros to be able to easily change storage model */
#define CAM_Record 0
#define CAM_Vector 1
#if 0
#define MatrixColAccess CAM_Record
#else
#define MatrixColAccess CAM_Vector
#endif
#if MatrixColAccess==CAM_Record
#define SET_MAT_ijA(item,i,j,A) mat->col_mat[item].rownr = i; \
mat->col_mat[item].colnr = j; \
mat->col_mat[item].value = A
#define COL_MAT_COLNR(item) (mat->col_mat[item].colnr)
#define COL_MAT_ROWNR(item) (mat->col_mat[item].rownr)
#define COL_MAT_VALUE(item) (mat->col_mat[item].value)
#define COL_MAT_COPY(left,right) mat->col_mat[left] = mat->col_mat[right]
#define COL_MAT_MOVE(to,from,rec) MEMMOVE(&(mat->col_mat[to]),&(mat->col_mat[from]),rec)
#define COL_MAT2_COLNR(item) (mat2->col_mat[item].colnr)
#define COL_MAT2_ROWNR(item) (mat2->col_mat[item].rownr)
#define COL_MAT2_VALUE(item) (mat2->col_mat[item].value)
#define matRowColStep (sizeof(MATitem)/sizeof(int))
#define matValueStep (sizeof(MATitem)/sizeof(REAL))
#else /* if MatrixColAccess==CAM_Vector */
#define SET_MAT_ijA(item,i,j,A) mat->col_mat_rownr[item] = i; \
mat->col_mat_colnr[item] = j; \
mat->col_mat_value[item] = A
#define COL_MAT_COLNR(item) (mat->col_mat_colnr[item])
#define COL_MAT_ROWNR(item) (mat->col_mat_rownr[item])
#define COL_MAT_VALUE(item) (mat->col_mat_value[item])
#define COL_MAT_COPY(left,right) COL_MAT_COLNR(left) = COL_MAT_COLNR(right); \
COL_MAT_ROWNR(left) = COL_MAT_ROWNR(right); \
COL_MAT_VALUE(left) = COL_MAT_VALUE(right)
#define COL_MAT_MOVE(to,from,rec) MEMMOVE(&COL_MAT_COLNR(to),&COL_MAT_COLNR(from),rec); \
MEMMOVE(&COL_MAT_ROWNR(to),&COL_MAT_ROWNR(from),rec); \
MEMMOVE(&COL_MAT_VALUE(to),&COL_MAT_VALUE(from),rec)
#define COL_MAT2_COLNR(item) (mat2->col_mat_colnr[item])
#define COL_MAT2_ROWNR(item) (mat2->col_mat_rownr[item])
#define COL_MAT2_VALUE(item) (mat2->col_mat_value[item])
#define matRowColStep 1
#define matValueStep 1
#endif
/* Matrix row access macros to be able to easily change storage model */
#define RAM_Index 0
#define RAM_FullCopy 1
#define MatrixRowAccess RAM_Index
#if MatrixRowAccess==RAM_Index
#define ROW_MAT_COLNR(item) COL_MAT_COLNR(mat->row_mat[item])
#define ROW_MAT_ROWNR(item) COL_MAT_ROWNR(mat->row_mat[item])
#define ROW_MAT_VALUE(item) COL_MAT_VALUE(mat->row_mat[item])
#elif MatrixColAccess==CAM_Record
#define ROW_MAT_COLNR(item) (mat->row_mat[item].colnr)
#define ROW_MAT_ROWNR(item) (mat->row_mat[item].rownr)
#define ROW_MAT_VALUE(item) (mat->row_mat[item].value)
#else /* if MatrixColAccess==CAM_Vector */
#define ROW_MAT_COLNR(item) (mat->row_mat_colnr[item])
#define ROW_MAT_ROWNR(item) (mat->row_mat_rownr[item])
#define ROW_MAT_VALUE(item) (mat->row_mat_value[item])
#endif
typedef struct _MATrec
{
/* Owner reference */
lprec *lp;
/* Active dimensions */
int rows;
int columns;
/* Allocated memory */
int rows_alloc;
int columns_alloc;
int mat_alloc; /* The allocated size for matrix sized structures */
/* Sparse problem matrix storage */
#if MatrixColAccess==CAM_Record
MATitem *col_mat; /* mat_alloc : The sparse data storage */
#else /*MatrixColAccess==CAM_Vector*/
int *col_mat_colnr;
int *col_mat_rownr;
REAL *col_mat_value;
#endif
int *col_end; /* columns_alloc+1 : col_end[i] is the index of the
first element after column i; column[i] is stored
in elements col_end[i-1] to col_end[i]-1 */
int *col_tag; /* user-definable tag associated with each column */
#if MatrixRowAccess==RAM_Index
int *row_mat; /* mat_alloc : From index 0, row_mat contains the
row-ordered index of the elements of col_mat */
#elif MatrixColAccess==CAM_Record
MATitem *row_mat; /* mat_alloc : From index 0, row_mat contains the
row-ordered copy of the elements in col_mat */
#else /*if MatrixColAccess==CAM_Vector*/
int *row_mat_colnr;
int *row_mat_rownr;
REAL *row_mat_value;
#endif
int *row_end; /* rows_alloc+1 : row_end[i] is the index of the
first element in row_mat after row i */
int *row_tag; /* user-definable tag associated with each row */
REAL *colmax; /* Array of maximum values of each column */
REAL *rowmax; /* Array of maximum values of each row */
REAL epsvalue; /* Zero element rejection threshold */
REAL infnorm; /* The largest absolute value in the matrix */
REAL dynrange;
MYBOOL row_end_valid; /* TRUE if row_end & row_mat are valid */
MYBOOL is_roworder; /* TRUE if the current (temporary) matrix order is row-wise */
} MATrec;
typedef struct _DeltaVrec
{
lprec *lp;
int activelevel;
MATrec *tracker;
} DeltaVrec;
#ifdef __cplusplus
__EXTERN_C {
#endif
/* Sparse matrix routines */
STATIC MATrec *mat_create(lprec *lp, int rows, int columns, REAL epsvalue);
STATIC MYBOOL mat_memopt(MATrec *mat, int rowextra, int colextra, int nzextra);
STATIC void mat_free(MATrec **matrix);
STATIC MYBOOL inc_matrow_space(MATrec *mat, int deltarows);
STATIC int mat_mapreplace(MATrec *mat, LLrec *rowmap, LLrec *colmap, MATrec *insmat);
STATIC int mat_matinsert(MATrec *mat, MATrec *insmat);
STATIC int mat_zerocompact(MATrec *mat);
STATIC int mat_rowcompact(MATrec *mat, MYBOOL dozeros);
STATIC int mat_colcompact(MATrec *mat, int prev_rows, int prev_cols);
STATIC MYBOOL inc_matcol_space(MATrec *mat, int deltacols);
STATIC MYBOOL inc_mat_space(MATrec *mat, int mindelta);
STATIC int mat_shiftrows(MATrec *mat, int *bbase, int delta, LLrec *varmap);
STATIC int mat_shiftcols(MATrec *mat, int *bbase, int delta, LLrec *varmap);
STATIC MATrec *mat_extractmat(MATrec *mat, LLrec *rowmap, LLrec *colmap, MYBOOL negated);
STATIC int mat_appendrow(MATrec *mat, int count, REAL *row, int *colno, REAL mult, MYBOOL checkrowmode);
STATIC int mat_appendcol(MATrec *mat, int count, REAL *column, int *rowno, REAL mult, MYBOOL checkrowmode);
MYBOOL mat_get_data(lprec *lp, int matindex, MYBOOL isrow, int **rownr, int **colnr, REAL **value);
MYBOOL mat_set_rowmap(MATrec *mat, int row_mat_index, int rownr, int colnr, int col_mat_index);
STATIC MYBOOL mat_indexrange(MATrec *mat, int index, MYBOOL isrow, int *startpos, int *endpos);
STATIC MYBOOL mat_validate(MATrec *mat);
STATIC MYBOOL mat_equalRows(MATrec *mat, int baserow, int comprow);
STATIC int mat_findelm(MATrec *mat, int row, int column);
STATIC int mat_findins(MATrec *mat, int row, int column, int *insertpos, MYBOOL validate);
STATIC void mat_multcol(MATrec *mat, int col_nr, REAL mult, MYBOOL DoObj);
STATIC REAL mat_getitem(MATrec *mat, int row, int column);
STATIC MYBOOL mat_setitem(MATrec *mat, int row, int column, REAL value);
STATIC MYBOOL mat_additem(MATrec *mat, int row, int column, REAL delta);
STATIC MYBOOL mat_setvalue(MATrec *mat, int Row, int Column, REAL Value, MYBOOL doscale);
STATIC int mat_nonzeros(MATrec *mat);
STATIC int mat_collength(MATrec *mat, int colnr);
STATIC int mat_rowlength(MATrec *mat, int rownr);
STATIC void mat_multrow(MATrec *mat, int row_nr, REAL mult);
STATIC void mat_multadd(MATrec *mat, REAL *lhsvector, int varnr, REAL mult);
STATIC MYBOOL mat_setrow(MATrec *mat, int rowno, int count, REAL *row, int *colno, MYBOOL doscale, MYBOOL checkrowmode);
STATIC MYBOOL mat_setcol(MATrec *mat, int colno, int count, REAL *column, int *rowno, MYBOOL doscale, MYBOOL checkrowmode);
STATIC MYBOOL mat_mergemat(MATrec *target, MATrec *source, MYBOOL usecolmap);
STATIC int mat_checkcounts(MATrec *mat, int *rownum, int *colnum, MYBOOL freeonexit);
STATIC int mat_expandcolumn(MATrec *mat, int colnr, REAL *column, int *nzlist, MYBOOL signedA);
STATIC MYBOOL mat_computemax(MATrec *mat);
STATIC MYBOOL mat_transpose(MATrec *mat);
/* Refactorization and recomputation routine */
MYBOOL __WINAPI invert(lprec *lp, MYBOOL shiftbounds, MYBOOL final);
/* Vector compression and expansion routines */
STATIC MYBOOL vec_compress(REAL *densevector, int startpos, int endpos, REAL epsilon, REAL *nzvector, int *nzindex);
STATIC MYBOOL vec_expand(REAL *nzvector, int *nzindex, REAL *densevector, int startpos, int endpos);
/* Sparse matrix products */
STATIC MYBOOL get_colIndexA(lprec *lp, int varset, int *colindex, MYBOOL append);
STATIC int prod_Ax(lprec *lp, int *coltarget, REAL *input, int *nzinput, REAL roundzero, REAL ofscalar, REAL *output, int *nzoutput, int roundmode);
STATIC int prod_xA(lprec *lp, int *coltarget, REAL *input, int *nzinput, REAL roundzero, REAL ofscalar, REAL *output, int *nzoutput, int roundmode);
STATIC MYBOOL prod_xA2(lprec *lp, int *coltarget, REAL *prow, REAL proundzero, int *pnzprow,
REAL *drow, REAL droundzero, int *dnzdrow, REAL ofscalar, int roundmode);
/* Equation solution */
STATIC MYBOOL fimprove(lprec *lp, REAL *pcol, int *nzidx, REAL roundzero);
STATIC void ftran(lprec *lp, REAL *rhsvector, int *nzidx, REAL roundzero);
STATIC MYBOOL bimprove(lprec *lp, REAL *rhsvector, int *nzidx, REAL roundzero);
STATIC void btran(lprec *lp, REAL *rhsvector, int *nzidx, REAL roundzero);
/* Combined equation solution and matrix product for simplex operations */
STATIC MYBOOL fsolve(lprec *lp, int varin, REAL *pcol, int *nzidx, REAL roundzero, REAL ofscalar, MYBOOL prepareupdate);
STATIC MYBOOL bsolve(lprec *lp, int row_nr, REAL *rhsvector, int *nzidx, REAL roundzero, REAL ofscalar);
STATIC void bsolve_xA2(lprec *lp, int* coltarget,
int row_nr1, REAL *vector1, REAL roundzero1, int *nzvector1,
int row_nr2, REAL *vector2, REAL roundzero2, int *nzvector2, int roundmode);
/* Change-tracking routines (primarily for B&B and presolve) */
STATIC DeltaVrec *createUndoLadder(lprec *lp, int levelitems, int maxlevels);
STATIC int incrementUndoLadder(DeltaVrec *DV);
STATIC MYBOOL modifyUndoLadder(DeltaVrec *DV, int itemno, REAL target[], REAL newvalue);
STATIC int countsUndoLadder(DeltaVrec *DV);
STATIC int restoreUndoLadder(DeltaVrec *DV, REAL target[]);
STATIC int decrementUndoLadder(DeltaVrec *DV);
STATIC MYBOOL freeUndoLadder(DeltaVrec **DV);
/* Specialized presolve undo functions */
STATIC MYBOOL appendUndoPresolve(lprec *lp, MYBOOL isprimal, REAL beta, int colnrDep);
STATIC MYBOOL addUndoPresolve(lprec *lp, MYBOOL isprimal, int colnrElim, REAL alpha, REAL beta, int colnrDep);
#ifdef __cplusplus
}
#endif
#endif /* HEADER_lp_matrix */