|
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 */ |