1 /* spxlp.h */ 2 3 /*********************************************************************** 4 * This code is part of GLPK (GNU Linear Programming Kit). 5 * Copyright (C) 2015 Free Software Foundation, Inc. 6 * Written by Andrew Makhorin <mao@gnu.org>. 7 * 8 * GLPK is free software: you can redistribute it and/or modify it 9 * under the terms of the GNU General Public License as published by 10 * the Free Software Foundation, either version 3 of the License, or 11 * (at your option) any later version. 12 * 13 * GLPK is distributed in the hope that it will be useful, but WITHOUT 14 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY 15 * or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public 16 * License for more details. 17 * 18 * You should have received a copy of the GNU General Public License 19 * along with GLPK. If not, see <http://www.gnu.org/licenses/>. 20 ***********************************************************************/ 21 22 #ifndef SPXLP_H 23 #define SPXLP_H 24 25 #include "bfd.h" 26 27 /*********************************************************************** 28 * The structure SPXLP describes LP problem and its current basis. 29 * 30 * It is assumed that LP problem has the following formulation (this is 31 * so called "working format"): 32 * 33 * z = c'* x + c0 -> min (1) 34 * 35 * A * x = b (2) 36 * 37 * l <= x <= u (3) 38 * 39 * where: 40 * 41 * x = (x[k]) is a n-vector of variables; 42 * 43 * z is an objective function; 44 * 45 * c = (c[k]) is a n-vector of objective coefficients; 46 * 47 * c0 is a constant term of the objective function; 48 * 49 * A = (a[i,k]) is a mxn-matrix of constraint coefficients; 50 * 51 * b = (b[i]) is a m-vector of right-hand sides; 52 * 53 * l = (l[k]) is a n-vector of lower bounds of variables; 54 * 55 * u = (u[k]) is a n-vector of upper bounds of variables. 56 * 57 * If variable x[k] has no lower (upper) bound, it is formally assumed 58 * that l[k] = -inf (u[k] = +inf). Variable having no bounds is called 59 * free (unbounded) variable. If l[k] = u[k], variable x[k] is assumed 60 * to be fixed. 61 * 62 * It is also assumed that matrix A has full row rank: rank(A) = m, 63 * i.e. all its rows are linearly independent, so m <= n. 64 * 65 * The (current) basis is defined by an appropriate permutation matrix 66 * P of order n such that: 67 * 68 * ( xB ) 69 * P * x = ( ), (4) 70 * ( xN ) 71 * 72 * where xB = (xB[i]) is a m-vector of basic variables, xN = (xN[j]) is 73 * a (n-m)-vector of non-basic variables. If a non-basic variable xN[j] 74 * has both lower and upper bounds, there is used an additional flag to 75 * indicate which bound is active. 76 * 77 * From (2) and (4) it follows that: 78 * 79 * A * P'* P * x = b <=> B * xB + N * xN = b, (5) 80 * 81 * where P' is a matrix transposed to P, and 82 * 83 * A * P' = (B | N). (6) 84 * 85 * Here B is the basis matrix, which is a square non-singular matrix 86 * of order m composed from columns of matrix A that correspond to 87 * basic variables xB, and N is a mx(n-m) matrix composed from columns 88 * of matrix A that correspond to non-basic variables xN. */ 89 90 typedef struct SPXLP SPXLP; 91 92 struct SPXLP 93 { /* LP problem data and its (current) basis */ 94 int m; 95 /* number of equality constraints, m > 0 */ 96 int n; 97 /* number of variables, n >= m */ 98 int nnz; 99 /* number of non-zeros in constraint matrix A */ 100 /*--------------------------------------------------------------*/ 101 /* mxn-matrix A of constraint coefficients in sparse column-wise 102 * format */ 103 int *A_ptr; /* int A_ptr[1+n+1]; */ 104 /* A_ptr[0] is not used; 105 * A_ptr[k], 1 <= k <= n, is starting position of k-th column in 106 * arrays A_ind and A_val; note that A_ptr[1] is always 1; 107 * A_ptr[n+1] indicates the position after the last element in 108 * arrays A_ind and A_val, i.e. A_ptr[n+1] = nnz+1, where nnz is 109 * the number of non-zero elements in matrix A; 110 * the length of k-th column (the number of non-zero elements in 111 * that column) can be calculated as A_ptr[k+1] - A_ptr[k] */ 112 int *A_ind; /* int A_ind[1+nnz]; */ 113 /* row indices */ 114 double *A_val; /* double A_val[1+nnz]; */ 115 /* non-zero element values (constraint coefficients) */ 116 /*--------------------------------------------------------------*/ 117 /* principal vectors of LP formulation */ 118 double *b; /* double b[1+m]; */ 119 /* b[0] is not used; 120 * b[i], 1 <= i <= m, is the right-hand side of i-th equality 121 * constraint */ 122 double *c; /* double c[1+n]; */ 123 /* c[0] is the constant term of the objective function; 124 * c[k], 1 <= k <= n, is the objective function coefficient at 125 * variable x[k] */ 126 double *l; /* double l[1+n]; */ 127 /* l[0] is not used; 128 * l[k], 1 <= k <= n, is the lower bound of variable x[k]; 129 * if x[k] has no lower bound, l[k] = -DBL_MAX */ 130 double *u; /* double u[1+n]; */ 131 /* u[0] is not used; 132 * u[k], 1 <= k <= n, is the upper bound of variable u[k]; 133 * if x[k] has no upper bound, u[k] = +DBL_MAX; 134 * note that l[k] = u[k] means that x[k] is fixed variable */ 135 /*--------------------------------------------------------------*/ 136 /* LP basis */ 137 int *head; /* int head[1+n]; */ 138 /* basis header, which is permutation matrix P (4): 139 * head[0] is not used; 140 * head[i] = k means that xB[i] = x[k], 1 <= i <= m; 141 * head[m+j] = k, means that xN[j] = x[k], 1 <= j <= n-m */ 142 char *flag; /* char flag[1+n-m]; */ 143 /* flags of non-basic variables: 144 * flag[0] is not used; 145 * flag[j], 1 <= j <= n-m, indicates that non-basic variable 146 * xN[j] is non-fixed and has its upper bound active */ 147 /*--------------------------------------------------------------*/ 148 /* basis matrix B of order m stored in factorized form */ 149 int valid; 150 /* factorization validity flag */ 151 BFD *bfd; 152 /* driver to factorization of the basis matrix */ 153 }; 154 155 #define spx_factorize _glp_spx_factorize 156 int spx_factorize(SPXLP *lp); 157 /* compute factorization of current basis matrix */ 158 159 #define spx_eval_beta _glp_spx_eval_beta 160 void spx_eval_beta(SPXLP *lp, double beta[/*1+m*/]); 161 /* compute values of basic variables */ 162 163 #define spx_eval_obj _glp_spx_eval_obj 164 double spx_eval_obj(SPXLP *lp, const double beta[/*1+m*/]); 165 /* compute value of objective function */ 166 167 #define spx_eval_pi _glp_spx_eval_pi 168 void spx_eval_pi(SPXLP *lp, double pi[/*1+m*/]); 169 /* compute simplex multipliers */ 170 171 #define spx_eval_dj _glp_spx_eval_dj 172 double spx_eval_dj(SPXLP *lp, const double pi[/*1+m*/], int j); 173 /* compute reduced cost of j-th non-basic variable */ 174 175 #define spx_eval_tcol _glp_spx_eval_tcol 176 void spx_eval_tcol(SPXLP *lp, int j, double tcol[/*1+m*/]); 177 /* compute j-th column of simplex table */ 178 179 #define spx_eval_rho _glp_spx_eval_rho 180 void spx_eval_rho(SPXLP *lp, int i, double rho[/*1+m*/]); 181 /* compute i-th row of basis matrix inverse */ 182 183 #if 1 /* 31/III-2016 */ 184 #define spx_eval_rho_s _glp_spx_eval_rho_s 185 void spx_eval_rho_s(SPXLP *lp, int i, FVS *rho); 186 /* sparse version of spx_eval_rho */ 187 #endif 188 189 #define spx_eval_tij _glp_spx_eval_tij 190 double spx_eval_tij(SPXLP *lp, const double rho[/*1+m*/], int j); 191 /* compute element T[i,j] of simplex table */ 192 193 #define spx_eval_trow _glp_spx_eval_trow 194 void spx_eval_trow(SPXLP *lp, const double rho[/*1+m*/], double 195 trow[/*1+n-m*/]); 196 /* compute i-th row of simplex table */ 197 198 #define spx_update_beta _glp_spx_update_beta 199 void spx_update_beta(SPXLP *lp, double beta[/*1+m*/], int p, 200 int p_flag, int q, const double tcol[/*1+m*/]); 201 /* update values of basic variables */ 202 203 #if 1 /* 30/III-2016 */ 204 #define spx_update_beta_s _glp_spx_update_beta_s 205 void spx_update_beta_s(SPXLP *lp, double beta[/*1+m*/], int p, 206 int p_flag, int q, const FVS *tcol); 207 /* sparse version of spx_update_beta */ 208 #endif 209 210 #define spx_update_d _glp_spx_update_d 211 double spx_update_d(SPXLP *lp, double d[/*1+n-m*/], int p, int q, 212 const double trow[/*1+n-m*/], const double tcol[/*1+m*/]); 213 /* update reduced costs of non-basic variables */ 214 215 #if 1 /* 30/III-2016 */ 216 #define spx_update_d_s _glp_spx_update_d_s 217 double spx_update_d_s(SPXLP *lp, double d[/*1+n-m*/], int p, int q, 218 const FVS *trow, const FVS *tcol); 219 /* sparse version of spx_update_d */ 220 #endif 221 222 #define spx_change_basis _glp_spx_change_basis 223 void spx_change_basis(SPXLP *lp, int p, int p_flag, int q); 224 /* change current basis to adjacent one */ 225 226 #define spx_update_invb _glp_spx_update_invb 227 int spx_update_invb(SPXLP *lp, int i, int k); 228 /* update factorization of basis matrix */ 229 230 #endif 231 232 /* eof */ 233