lemon-project-template-glpk

annotate deps/glpk/src/glpfhv.h @ 11:4fc6ad2fb8a6

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