lemon-project-template-glpk
diff deps/glpk/src/glpfhv.h @ 9:33de93886c88
Import GLPK 4.47
author | Alpar Juttner <alpar@cs.elte.hu> |
---|---|
date | Sun, 06 Nov 2011 20:59:10 +0100 |
parents | |
children |
line diff
1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000 1.2 +++ b/deps/glpk/src/glpfhv.h Sun Nov 06 20:59:10 2011 +0100 1.3 @@ -0,0 +1,170 @@ 1.4 +/* glpfhv.h (LP basis factorization, FHV eta file version) */ 1.5 + 1.6 +/*********************************************************************** 1.7 +* This code is part of GLPK (GNU Linear Programming Kit). 1.8 +* 1.9 +* Copyright (C) 2000, 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008, 1.10 +* 2009, 2010, 2011 Andrew Makhorin, Department for Applied Informatics, 1.11 +* Moscow Aviation Institute, Moscow, Russia. All rights reserved. 1.12 +* E-mail: <mao@gnu.org>. 1.13 +* 1.14 +* GLPK is free software: you can redistribute it and/or modify it 1.15 +* under the terms of the GNU General Public License as published by 1.16 +* the Free Software Foundation, either version 3 of the License, or 1.17 +* (at your option) any later version. 1.18 +* 1.19 +* GLPK is distributed in the hope that it will be useful, but WITHOUT 1.20 +* ANY WARRANTY; without even the implied warranty of MERCHANTABILITY 1.21 +* or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public 1.22 +* License for more details. 1.23 +* 1.24 +* You should have received a copy of the GNU General Public License 1.25 +* along with GLPK. If not, see <http://www.gnu.org/licenses/>. 1.26 +***********************************************************************/ 1.27 + 1.28 +#ifndef GLPFHV_H 1.29 +#define GLPFHV_H 1.30 + 1.31 +#include "glpluf.h" 1.32 + 1.33 +/*********************************************************************** 1.34 +* The structure FHV defines the factorization of the basis mxm-matrix 1.35 +* B, where m is the number of rows in corresponding problem instance. 1.36 +* 1.37 +* This factorization is the following sextet: 1.38 +* 1.39 +* [B] = (F, H, V, P0, P, Q), (1) 1.40 +* 1.41 +* where F, H, and V are such matrices that 1.42 +* 1.43 +* B = F * H * V, (2) 1.44 +* 1.45 +* and P0, P, and Q are such permutation matrices that the matrix 1.46 +* 1.47 +* L = P0 * F * inv(P0) (3) 1.48 +* 1.49 +* is lower triangular with unity diagonal, and the matrix 1.50 +* 1.51 +* U = P * V * Q (4) 1.52 +* 1.53 +* is upper triangular. All the matrices have the same order m, which 1.54 +* is the order of the basis matrix B. 1.55 +* 1.56 +* The matrices F, V, P, and Q are stored in the structure LUF (see the 1.57 +* module GLPLUF), which is a member of the structure FHV. 1.58 +* 1.59 +* The matrix H is stored in the form of eta file using row-like format 1.60 +* as follows: 1.61 +* 1.62 +* H = H[1] * H[2] * ... * H[nfs], (5) 1.63 +* 1.64 +* where H[k], k = 1, 2, ..., nfs, is a row-like factor, which differs 1.65 +* from the unity matrix only by one row, nfs is current number of row- 1.66 +* like factors. After the factorization has been built for some given 1.67 +* basis matrix B the matrix H has no factors and thus it is the unity 1.68 +* matrix. Then each time when the factorization is recomputed for an 1.69 +* adjacent basis matrix, the next factor H[k], k = 1, 2, ... is built 1.70 +* and added to the end of the eta file H. 1.71 +* 1.72 +* Being sparse vectors non-trivial rows of the factors H[k] are stored 1.73 +* in the right part of the sparse vector area (SVA) in the same manner 1.74 +* as rows and columns of the matrix F. 1.75 +* 1.76 +* For more details see the program documentation. */ 1.77 + 1.78 +typedef struct FHV FHV; 1.79 + 1.80 +struct FHV 1.81 +{ /* LP basis factorization */ 1.82 + int m_max; 1.83 + /* maximal value of m (increased automatically, if necessary) */ 1.84 + int m; 1.85 + /* the order of matrices B, F, H, V, P0, P, Q */ 1.86 + int valid; 1.87 + /* the factorization is valid only if this flag is set */ 1.88 + LUF *luf; 1.89 + /* LU-factorization (contains the matrices F, V, P, Q) */ 1.90 + /*--------------------------------------------------------------*/ 1.91 + /* matrix H in the form of eta file */ 1.92 + int hh_max; 1.93 + /* maximal number of row-like factors (which limits the number of 1.94 + updates of the factorization) */ 1.95 + int hh_nfs; 1.96 + /* current number of row-like factors (0 <= hh_nfs <= hh_max) */ 1.97 + int *hh_ind; /* int hh_ind[1+hh_max]; */ 1.98 + /* hh_ind[k], k = 1, ..., nfs, is the number of a non-trivial row 1.99 + of factor H[k] */ 1.100 + int *hh_ptr; /* int hh_ptr[1+hh_max]; */ 1.101 + /* hh_ptr[k], k = 1, ..., nfs, is a pointer to the first element 1.102 + of the non-trivial row of factor H[k] in the SVA */ 1.103 + int *hh_len; /* int hh_len[1+hh_max]; */ 1.104 + /* hh_len[k], k = 1, ..., nfs, is the number of non-zero elements 1.105 + in the non-trivial row of factor H[k] */ 1.106 + /*--------------------------------------------------------------*/ 1.107 + /* matrix P0 */ 1.108 + int *p0_row; /* int p0_row[1+m_max]; */ 1.109 + /* p0_row[i] = j means that p0[i,j] = 1 */ 1.110 + int *p0_col; /* int p0_col[1+m_max]; */ 1.111 + /* p0_col[j] = i means that p0[i,j] = 1 */ 1.112 + /* if i-th row or column of the matrix F corresponds to i'-th row 1.113 + or column of the matrix L = P0*F*inv(P0), then p0_row[i'] = i 1.114 + and p0_col[i] = i' */ 1.115 + /*--------------------------------------------------------------*/ 1.116 + /* working arrays */ 1.117 + int *cc_ind; /* int cc_ind[1+m_max]; */ 1.118 + /* integer working array */ 1.119 + double *cc_val; /* double cc_val[1+m_max]; */ 1.120 + /* floating-point working array */ 1.121 + /*--------------------------------------------------------------*/ 1.122 + /* control parameters */ 1.123 + double upd_tol; 1.124 + /* update tolerance; if after updating the factorization absolute 1.125 + value of some diagonal element u[k,k] of matrix U = P*V*Q is 1.126 + less than upd_tol * max(|u[k,*]|, |u[*,k]|), the factorization 1.127 + is considered as inaccurate */ 1.128 + /*--------------------------------------------------------------*/ 1.129 + /* some statistics */ 1.130 + int nnz_h; 1.131 + /* current number of non-zeros in all factors of matrix H */ 1.132 +}; 1.133 + 1.134 +/* return codes: */ 1.135 +#define FHV_ESING 1 /* singular matrix */ 1.136 +#define FHV_ECOND 2 /* ill-conditioned matrix */ 1.137 +#define FHV_ECHECK 3 /* insufficient accuracy */ 1.138 +#define FHV_ELIMIT 4 /* update limit reached */ 1.139 +#define FHV_EROOM 5 /* SVA overflow */ 1.140 + 1.141 +#define fhv_create_it _glp_fhv_create_it 1.142 +FHV *fhv_create_it(void); 1.143 +/* create LP basis factorization */ 1.144 + 1.145 +#define fhv_factorize _glp_fhv_factorize 1.146 +int fhv_factorize(FHV *fhv, int m, int (*col)(void *info, int j, 1.147 + int ind[], double val[]), void *info); 1.148 +/* compute LP basis factorization */ 1.149 + 1.150 +#define fhv_h_solve _glp_fhv_h_solve 1.151 +void fhv_h_solve(FHV *fhv, int tr, double x[]); 1.152 +/* solve system H*x = b or H'*x = b */ 1.153 + 1.154 +#define fhv_ftran _glp_fhv_ftran 1.155 +void fhv_ftran(FHV *fhv, double x[]); 1.156 +/* perform forward transformation (solve system B*x = b) */ 1.157 + 1.158 +#define fhv_btran _glp_fhv_btran 1.159 +void fhv_btran(FHV *fhv, double x[]); 1.160 +/* perform backward transformation (solve system B'*x = b) */ 1.161 + 1.162 +#define fhv_update_it _glp_fhv_update_it 1.163 +int fhv_update_it(FHV *fhv, int j, int len, const int ind[], 1.164 + const double val[]); 1.165 +/* update LP basis factorization */ 1.166 + 1.167 +#define fhv_delete_it _glp_fhv_delete_it 1.168 +void fhv_delete_it(FHV *fhv); 1.169 +/* delete LP basis factorization */ 1.170 + 1.171 +#endif 1.172 + 1.173 +/* eof */