lemon-project-template-glpk
view deps/glpk/src/glpfhv.h @ 11:4fc6ad2fb8a6
Test GLPK in src/main.cc
| author | Alpar Juttner <alpar@cs.elte.hu> |
|---|---|
| date | Sun, 06 Nov 2011 21:43:29 +0100 |
| parents | |
| children |
line source
1 /* glpfhv.h (LP basis factorization, FHV eta file version) */
3 /***********************************************************************
4 * This code is part of GLPK (GNU Linear Programming Kit).
5 *
6 * Copyright (C) 2000, 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008,
7 * 2009, 2010, 2011 Andrew Makhorin, Department for Applied Informatics,
8 * Moscow Aviation Institute, Moscow, Russia. All rights reserved.
9 * E-mail: <mao@gnu.org>.
10 *
11 * GLPK is free software: you can redistribute it and/or modify it
12 * under the terms of the GNU General Public License as published by
13 * the Free Software Foundation, either version 3 of the License, or
14 * (at your option) any later version.
15 *
16 * GLPK is distributed in the hope that it will be useful, but WITHOUT
17 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
18 * or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public
19 * License for more details.
20 *
21 * You should have received a copy of the GNU General Public License
22 * along with GLPK. If not, see <http://www.gnu.org/licenses/>.
23 ***********************************************************************/
25 #ifndef GLPFHV_H
26 #define GLPFHV_H
28 #include "glpluf.h"
30 /***********************************************************************
31 * The structure FHV defines the factorization of the basis mxm-matrix
32 * B, where m is the number of rows in corresponding problem instance.
33 *
34 * This factorization is the following sextet:
35 *
36 * [B] = (F, H, V, P0, P, Q), (1)
37 *
38 * where F, H, and V are such matrices that
39 *
40 * B = F * H * V, (2)
41 *
42 * and P0, P, and Q are such permutation matrices that the matrix
43 *
44 * L = P0 * F * inv(P0) (3)
45 *
46 * is lower triangular with unity diagonal, and the matrix
47 *
48 * U = P * V * Q (4)
49 *
50 * is upper triangular. All the matrices have the same order m, which
51 * is the order of the basis matrix B.
52 *
53 * The matrices F, V, P, and Q are stored in the structure LUF (see the
54 * module GLPLUF), which is a member of the structure FHV.
55 *
56 * The matrix H is stored in the form of eta file using row-like format
57 * as follows:
58 *
59 * H = H[1] * H[2] * ... * H[nfs], (5)
60 *
61 * where H[k], k = 1, 2, ..., nfs, is a row-like factor, which differs
62 * from the unity matrix only by one row, nfs is current number of row-
63 * like factors. After the factorization has been built for some given
64 * basis matrix B the matrix H has no factors and thus it is the unity
65 * matrix. Then each time when the factorization is recomputed for an
66 * adjacent basis matrix, the next factor H[k], k = 1, 2, ... is built
67 * and added to the end of the eta file H.
68 *
69 * Being sparse vectors non-trivial rows of the factors H[k] are stored
70 * in the right part of the sparse vector area (SVA) in the same manner
71 * as rows and columns of the matrix F.
72 *
73 * For more details see the program documentation. */
75 typedef struct FHV FHV;
77 struct FHV
78 { /* LP basis factorization */
79 int m_max;
80 /* maximal value of m (increased automatically, if necessary) */
81 int m;
82 /* the order of matrices B, F, H, V, P0, P, Q */
83 int valid;
84 /* the factorization is valid only if this flag is set */
85 LUF *luf;
86 /* LU-factorization (contains the matrices F, V, P, Q) */
87 /*--------------------------------------------------------------*/
88 /* matrix H in the form of eta file */
89 int hh_max;
90 /* maximal number of row-like factors (which limits the number of
91 updates of the factorization) */
92 int hh_nfs;
93 /* current number of row-like factors (0 <= hh_nfs <= hh_max) */
94 int *hh_ind; /* int hh_ind[1+hh_max]; */
95 /* hh_ind[k], k = 1, ..., nfs, is the number of a non-trivial row
96 of factor H[k] */
97 int *hh_ptr; /* int hh_ptr[1+hh_max]; */
98 /* hh_ptr[k], k = 1, ..., nfs, is a pointer to the first element
99 of the non-trivial row of factor H[k] in the SVA */
100 int *hh_len; /* int hh_len[1+hh_max]; */
101 /* hh_len[k], k = 1, ..., nfs, is the number of non-zero elements
102 in the non-trivial row of factor H[k] */
103 /*--------------------------------------------------------------*/
104 /* matrix P0 */
105 int *p0_row; /* int p0_row[1+m_max]; */
106 /* p0_row[i] = j means that p0[i,j] = 1 */
107 int *p0_col; /* int p0_col[1+m_max]; */
108 /* p0_col[j] = i means that p0[i,j] = 1 */
109 /* if i-th row or column of the matrix F corresponds to i'-th row
110 or column of the matrix L = P0*F*inv(P0), then p0_row[i'] = i
111 and p0_col[i] = i' */
112 /*--------------------------------------------------------------*/
113 /* working arrays */
114 int *cc_ind; /* int cc_ind[1+m_max]; */
115 /* integer working array */
116 double *cc_val; /* double cc_val[1+m_max]; */
117 /* floating-point working array */
118 /*--------------------------------------------------------------*/
119 /* control parameters */
120 double upd_tol;
121 /* update tolerance; if after updating the factorization absolute
122 value of some diagonal element u[k,k] of matrix U = P*V*Q is
123 less than upd_tol * max(|u[k,*]|, |u[*,k]|), the factorization
124 is considered as inaccurate */
125 /*--------------------------------------------------------------*/
126 /* some statistics */
127 int nnz_h;
128 /* current number of non-zeros in all factors of matrix H */
129 };
131 /* return codes: */
132 #define FHV_ESING 1 /* singular matrix */
133 #define FHV_ECOND 2 /* ill-conditioned matrix */
134 #define FHV_ECHECK 3 /* insufficient accuracy */
135 #define FHV_ELIMIT 4 /* update limit reached */
136 #define FHV_EROOM 5 /* SVA overflow */
138 #define fhv_create_it _glp_fhv_create_it
139 FHV *fhv_create_it(void);
140 /* create LP basis factorization */
142 #define fhv_factorize _glp_fhv_factorize
143 int fhv_factorize(FHV *fhv, int m, int (*col)(void *info, int j,
144 int ind[], double val[]), void *info);
145 /* compute LP basis factorization */
147 #define fhv_h_solve _glp_fhv_h_solve
148 void fhv_h_solve(FHV *fhv, int tr, double x[]);
149 /* solve system H*x = b or H'*x = b */
151 #define fhv_ftran _glp_fhv_ftran
152 void fhv_ftran(FHV *fhv, double x[]);
153 /* perform forward transformation (solve system B*x = b) */
155 #define fhv_btran _glp_fhv_btran
156 void fhv_btran(FHV *fhv, double x[]);
157 /* perform backward transformation (solve system B'*x = b) */
159 #define fhv_update_it _glp_fhv_update_it
160 int fhv_update_it(FHV *fhv, int j, int len, const int ind[],
161 const double val[]);
162 /* update LP basis factorization */
164 #define fhv_delete_it _glp_fhv_delete_it
165 void fhv_delete_it(FHV *fhv);
166 /* delete LP basis factorization */
168 #endif
170 /* eof */