258 lines
12 KiB
C
258 lines
12 KiB
C
#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);
|
|
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 */
|
|
|