1 /* glpapi05.c (LP basis constructing routines) */ 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 #include "glpapi.h" 26 27 /*********************************************************************** 28 * NAME 29 * 30 * glp_set_row_stat - set (change) row status 31 * 32 * SYNOPSIS 33 * 34 * void glp_set_row_stat(glp_prob *lp, int i, int stat); 35 * 36 * DESCRIPTION 37 * 38 * The routine glp_set_row_stat sets (changes) status of the auxiliary 39 * variable associated with i-th row. 40 * 41 * The new status of the auxiliary variable should be specified by the 42 * parameter stat as follows: 43 * 44 * GLP_BS - basic variable; 45 * GLP_NL - non-basic variable; 46 * GLP_NU - non-basic variable on its upper bound; if the variable is 47 * not double-bounded, this means the same as GLP_NL (only in 48 * case of this routine); 49 * GLP_NF - the same as GLP_NL (only in case of this routine); 50 * GLP_NS - the same as GLP_NL (only in case of this routine). */ 51 52 void glp_set_row_stat(glp_prob *lp, int i, int stat) 53 { GLPROW *row; 54 if (!(1 <= i && i <= lp->m)) 55 xerror("glp_set_row_stat: i = %d; row number out of range\n", 56 i); 57 if (!(stat == GLP_BS || stat == GLP_NL || stat == GLP_NU || 58 stat == GLP_NF || stat == GLP_NS)) 59 xerror("glp_set_row_stat: i = %d; stat = %d; invalid status\n", 60 i, stat); 61 row = lp->row[i]; 62 if (stat != GLP_BS) 63 { switch (row->type) 64 { case GLP_FR: stat = GLP_NF; break; 65 case GLP_LO: stat = GLP_NL; break; 66 case GLP_UP: stat = GLP_NU; break; 67 case GLP_DB: if (stat != GLP_NU) stat = GLP_NL; break; 68 case GLP_FX: stat = GLP_NS; break; 69 default: xassert(row != row); 70 } 71 } 72 if (row->stat == GLP_BS && stat != GLP_BS || 73 row->stat != GLP_BS && stat == GLP_BS) 74 { /* invalidate the basis factorization */ 75 lp->valid = 0; 76 } 77 row->stat = stat; 78 return; 79 } 80 81 /*********************************************************************** 82 * NAME 83 * 84 * glp_set_col_stat - set (change) column status 85 * 86 * SYNOPSIS 87 * 88 * void glp_set_col_stat(glp_prob *lp, int j, int stat); 89 * 90 * DESCRIPTION 91 * 92 * The routine glp_set_col_stat sets (changes) status of the structural 93 * variable associated with j-th column. 94 * 95 * The new status of the structural variable should be specified by the 96 * parameter stat as follows: 97 * 98 * GLP_BS - basic variable; 99 * GLP_NL - non-basic variable; 100 * GLP_NU - non-basic variable on its upper bound; if the variable is 101 * not double-bounded, this means the same as GLP_NL (only in 102 * case of this routine); 103 * GLP_NF - the same as GLP_NL (only in case of this routine); 104 * GLP_NS - the same as GLP_NL (only in case of this routine). */ 105 106 void glp_set_col_stat(glp_prob *lp, int j, int stat) 107 { GLPCOL *col; 108 if (!(1 <= j && j <= lp->n)) 109 xerror("glp_set_col_stat: j = %d; column number out of range\n" 110 , j); 111 if (!(stat == GLP_BS || stat == GLP_NL || stat == GLP_NU || 112 stat == GLP_NF || stat == GLP_NS)) 113 xerror("glp_set_col_stat: j = %d; stat = %d; invalid status\n", 114 j, stat); 115 col = lp->col[j]; 116 if (stat != GLP_BS) 117 { switch (col->type) 118 { case GLP_FR: stat = GLP_NF; break; 119 case GLP_LO: stat = GLP_NL; break; 120 case GLP_UP: stat = GLP_NU; break; 121 case GLP_DB: if (stat != GLP_NU) stat = GLP_NL; break; 122 case GLP_FX: stat = GLP_NS; break; 123 default: xassert(col != col); 124 } 125 } 126 if (col->stat == GLP_BS && stat != GLP_BS || 127 col->stat != GLP_BS && stat == GLP_BS) 128 { /* invalidate the basis factorization */ 129 lp->valid = 0; 130 } 131 col->stat = stat; 132 return; 133 } 134 135 /*********************************************************************** 136 * NAME 137 * 138 * glp_std_basis - construct standard initial LP basis 139 * 140 * SYNOPSIS 141 * 142 * void glp_std_basis(glp_prob *lp); 143 * 144 * DESCRIPTION 145 * 146 * The routine glp_std_basis builds the "standard" (trivial) initial 147 * basis for the specified problem object. 148 * 149 * In the "standard" basis all auxiliary variables are basic, and all 150 * structural variables are non-basic. */ 151 152 void glp_std_basis(glp_prob *lp) 153 { int i, j; 154 /* make all auxiliary variables basic */ 155 for (i = 1; i <= lp->m; i++) 156 glp_set_row_stat(lp, i, GLP_BS); 157 /* make all structural variables non-basic */ 158 for (j = 1; j <= lp->n; j++) 159 { GLPCOL *col = lp->col[j]; 160 if (col->type == GLP_DB && fabs(col->lb) > fabs(col->ub)) 161 glp_set_col_stat(lp, j, GLP_NU); 162 else 163 glp_set_col_stat(lp, j, GLP_NL); 164 } 165 return; 166 } 167 168 /* eof */ 169