COIN-OR::LEMON - Graph Library

source: glpk-cmake/src/glpfhv.h @ 1:c445c931472f

Last change on this file since 1:c445c931472f was 1:c445c931472f, checked in by Alpar Juttner <alpar@…>, 10 years ago

Import glpk-4.45

  • Generated files and doc/notes are removed
File size: 6.6 KB
Line 
1/* glpfhv.h (LP basis factorization, FHV eta file version) */
2
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 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***********************************************************************/
24
25#ifndef GLPFHV_H
26#define GLPFHV_H
27
28#include "glpluf.h"
29
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. */
74
75typedef struct FHV FHV;
76
77struct 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};
130
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 */
137
138#define fhv_create_it _glp_fhv_create_it
139FHV *fhv_create_it(void);
140/* create LP basis factorization */
141
142#define fhv_factorize _glp_fhv_factorize
143int fhv_factorize(FHV *fhv, int m, int (*col)(void *info, int j,
144      int ind[], double val[]), void *info);
145/* compute LP basis factorization */
146
147#define fhv_h_solve _glp_fhv_h_solve
148void fhv_h_solve(FHV *fhv, int tr, double x[]);
149/* solve system H*x = b or H'*x = b */
150
151#define fhv_ftran _glp_fhv_ftran
152void fhv_ftran(FHV *fhv, double x[]);
153/* perform forward transformation (solve system B*x = b) */
154
155#define fhv_btran _glp_fhv_btran
156void fhv_btran(FHV *fhv, double x[]);
157/* perform backward transformation (solve system B'*x = b) */
158
159#define fhv_update_it _glp_fhv_update_it
160int fhv_update_it(FHV *fhv, int j, int len, const int ind[],
161      const double val[]);
162/* update LP basis factorization */
163
164#define fhv_delete_it _glp_fhv_delete_it
165void fhv_delete_it(FHV *fhv);
166/* delete LP basis factorization */
167
168#endif
169
170/* eof */
Note: See TracBrowser for help on using the repository browser.