lemon-project-template-glpk

annotate deps/glpk/src/glpini02.c @ 9:33de93886c88

find changesets by author, revision, files, or words in the commit message
Import GLPK 4.47
author Alpar Juttner <alpar@cs.elte.hu>
date Sun, 06 Nov 2011 20:59:10 +0100
parents
children
rev   line source
alpar@9 1 /* glpini02.c */
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 #include "glpapi.h"
alpar@9 26
alpar@9 27 struct var
alpar@9 28 { /* structural variable */
alpar@9 29 int j;
alpar@9 30 /* ordinal number */
alpar@9 31 double q;
alpar@9 32 /* penalty value */
alpar@9 33 };
alpar@9 34
alpar@9 35 static int fcmp(const void *ptr1, const void *ptr2)
alpar@9 36 { /* this routine is passed to the qsort() function */
alpar@9 37 struct var *col1 = (void *)ptr1, *col2 = (void *)ptr2;
alpar@9 38 if (col1->q < col2->q) return -1;
alpar@9 39 if (col1->q > col2->q) return +1;
alpar@9 40 return 0;
alpar@9 41 }
alpar@9 42
alpar@9 43 static int get_column(glp_prob *lp, int j, int ind[], double val[])
alpar@9 44 { /* Bixby's algorithm assumes that the constraint matrix is scaled
alpar@9 45 such that the maximum absolute value in every non-zero row and
alpar@9 46 column is 1 */
alpar@9 47 int k, len;
alpar@9 48 double big;
alpar@9 49 len = glp_get_mat_col(lp, j, ind, val);
alpar@9 50 big = 0.0;
alpar@9 51 for (k = 1; k <= len; k++)
alpar@9 52 if (big < fabs(val[k])) big = fabs(val[k]);
alpar@9 53 if (big == 0.0) big = 1.0;
alpar@9 54 for (k = 1; k <= len; k++) val[k] /= big;
alpar@9 55 return len;
alpar@9 56 }
alpar@9 57
alpar@9 58 static void cpx_basis(glp_prob *lp)
alpar@9 59 { /* main routine */
alpar@9 60 struct var *C, *C2, *C3, *C4;
alpar@9 61 int m, n, i, j, jk, k, l, ll, t, n2, n3, n4, type, len, *I, *r,
alpar@9 62 *ind;
alpar@9 63 double alpha, gamma, cmax, temp, *v, *val;
alpar@9 64 xprintf("Constructing initial basis...\n");
alpar@9 65 /* determine the number of rows and columns */
alpar@9 66 m = glp_get_num_rows(lp);
alpar@9 67 n = glp_get_num_cols(lp);
alpar@9 68 /* allocate working arrays */
alpar@9 69 C = xcalloc(1+n, sizeof(struct var));
alpar@9 70 I = xcalloc(1+m, sizeof(int));
alpar@9 71 r = xcalloc(1+m, sizeof(int));
alpar@9 72 v = xcalloc(1+m, sizeof(double));
alpar@9 73 ind = xcalloc(1+m, sizeof(int));
alpar@9 74 val = xcalloc(1+m, sizeof(double));
alpar@9 75 /* make all auxiliary variables non-basic */
alpar@9 76 for (i = 1; i <= m; i++)
alpar@9 77 { if (glp_get_row_type(lp, i) != GLP_DB)
alpar@9 78 glp_set_row_stat(lp, i, GLP_NS);
alpar@9 79 else if (fabs(glp_get_row_lb(lp, i)) <=
alpar@9 80 fabs(glp_get_row_ub(lp, i)))
alpar@9 81 glp_set_row_stat(lp, i, GLP_NL);
alpar@9 82 else
alpar@9 83 glp_set_row_stat(lp, i, GLP_NU);
alpar@9 84 }
alpar@9 85 /* make all structural variables non-basic */
alpar@9 86 for (j = 1; j <= n; j++)
alpar@9 87 { if (glp_get_col_type(lp, j) != GLP_DB)
alpar@9 88 glp_set_col_stat(lp, j, GLP_NS);
alpar@9 89 else if (fabs(glp_get_col_lb(lp, j)) <=
alpar@9 90 fabs(glp_get_col_ub(lp, j)))
alpar@9 91 glp_set_col_stat(lp, j, GLP_NL);
alpar@9 92 else
alpar@9 93 glp_set_col_stat(lp, j, GLP_NU);
alpar@9 94 }
alpar@9 95 /* C2 is a set of free structural variables */
alpar@9 96 n2 = 0, C2 = C + 0;
alpar@9 97 for (j = 1; j <= n; j++)
alpar@9 98 { type = glp_get_col_type(lp, j);
alpar@9 99 if (type == GLP_FR)
alpar@9 100 { n2++;
alpar@9 101 C2[n2].j = j;
alpar@9 102 C2[n2].q = 0.0;
alpar@9 103 }
alpar@9 104 }
alpar@9 105 /* C3 is a set of structural variables having excatly one (lower
alpar@9 106 or upper) bound */
alpar@9 107 n3 = 0, C3 = C2 + n2;
alpar@9 108 for (j = 1; j <= n; j++)
alpar@9 109 { type = glp_get_col_type(lp, j);
alpar@9 110 if (type == GLP_LO)
alpar@9 111 { n3++;
alpar@9 112 C3[n3].j = j;
alpar@9 113 C3[n3].q = + glp_get_col_lb(lp, j);
alpar@9 114 }
alpar@9 115 else if (type == GLP_UP)
alpar@9 116 { n3++;
alpar@9 117 C3[n3].j = j;
alpar@9 118 C3[n3].q = - glp_get_col_ub(lp, j);
alpar@9 119 }
alpar@9 120 }
alpar@9 121 /* C4 is a set of structural variables having both (lower and
alpar@9 122 upper) bounds */
alpar@9 123 n4 = 0, C4 = C3 + n3;
alpar@9 124 for (j = 1; j <= n; j++)
alpar@9 125 { type = glp_get_col_type(lp, j);
alpar@9 126 if (type == GLP_DB)
alpar@9 127 { n4++;
alpar@9 128 C4[n4].j = j;
alpar@9 129 C4[n4].q = glp_get_col_lb(lp, j) - glp_get_col_ub(lp, j);
alpar@9 130 }
alpar@9 131 }
alpar@9 132 /* compute gamma = max{|c[j]|: 1 <= j <= n} */
alpar@9 133 gamma = 0.0;
alpar@9 134 for (j = 1; j <= n; j++)
alpar@9 135 { temp = fabs(glp_get_obj_coef(lp, j));
alpar@9 136 if (gamma < temp) gamma = temp;
alpar@9 137 }
alpar@9 138 /* compute cmax */
alpar@9 139 cmax = (gamma == 0.0 ? 1.0 : 1000.0 * gamma);
alpar@9 140 /* compute final penalty for all structural variables within sets
alpar@9 141 C2, C3, and C4 */
alpar@9 142 switch (glp_get_obj_dir(lp))
alpar@9 143 { case GLP_MIN: temp = +1.0; break;
alpar@9 144 case GLP_MAX: temp = -1.0; break;
alpar@9 145 default: xassert(lp != lp);
alpar@9 146 }
alpar@9 147 for (k = 1; k <= n2+n3+n4; k++)
alpar@9 148 { j = C[k].j;
alpar@9 149 C[k].q += (temp * glp_get_obj_coef(lp, j)) / cmax;
alpar@9 150 }
alpar@9 151 /* sort structural variables within C2, C3, and C4 in ascending
alpar@9 152 order of penalty value */
alpar@9 153 qsort(C2+1, n2, sizeof(struct var), fcmp);
alpar@9 154 for (k = 1; k < n2; k++) xassert(C2[k].q <= C2[k+1].q);
alpar@9 155 qsort(C3+1, n3, sizeof(struct var), fcmp);
alpar@9 156 for (k = 1; k < n3; k++) xassert(C3[k].q <= C3[k+1].q);
alpar@9 157 qsort(C4+1, n4, sizeof(struct var), fcmp);
alpar@9 158 for (k = 1; k < n4; k++) xassert(C4[k].q <= C4[k+1].q);
alpar@9 159 /*** STEP 1 ***/
alpar@9 160 for (i = 1; i <= m; i++)
alpar@9 161 { type = glp_get_row_type(lp, i);
alpar@9 162 if (type != GLP_FX)
alpar@9 163 { /* row i is either free or inequality constraint */
alpar@9 164 glp_set_row_stat(lp, i, GLP_BS);
alpar@9 165 I[i] = 1;
alpar@9 166 r[i] = 1;
alpar@9 167 }
alpar@9 168 else
alpar@9 169 { /* row i is equality constraint */
alpar@9 170 I[i] = 0;
alpar@9 171 r[i] = 0;
alpar@9 172 }
alpar@9 173 v[i] = +DBL_MAX;
alpar@9 174 }
alpar@9 175 /*** STEP 2 ***/
alpar@9 176 for (k = 1; k <= n2+n3+n4; k++)
alpar@9 177 { jk = C[k].j;
alpar@9 178 len = get_column(lp, jk, ind, val);
alpar@9 179 /* let alpha = max{|A[l,jk]|: r[l] = 0} and let l' be such
alpar@9 180 that alpha = |A[l',jk]| */
alpar@9 181 alpha = 0.0, ll = 0;
alpar@9 182 for (t = 1; t <= len; t++)
alpar@9 183 { l = ind[t];
alpar@9 184 if (r[l] == 0 && alpha < fabs(val[t]))
alpar@9 185 alpha = fabs(val[t]), ll = l;
alpar@9 186 }
alpar@9 187 if (alpha >= 0.99)
alpar@9 188 { /* B := B union {jk} */
alpar@9 189 glp_set_col_stat(lp, jk, GLP_BS);
alpar@9 190 I[ll] = 1;
alpar@9 191 v[ll] = alpha;
alpar@9 192 /* r[l] := r[l] + 1 for all l such that |A[l,jk]| != 0 */
alpar@9 193 for (t = 1; t <= len; t++)
alpar@9 194 { l = ind[t];
alpar@9 195 if (val[t] != 0.0) r[l]++;
alpar@9 196 }
alpar@9 197 /* continue to the next k */
alpar@9 198 continue;
alpar@9 199 }
alpar@9 200 /* if |A[l,jk]| > 0.01 * v[l] for some l, continue to the
alpar@9 201 next k */
alpar@9 202 for (t = 1; t <= len; t++)
alpar@9 203 { l = ind[t];
alpar@9 204 if (fabs(val[t]) > 0.01 * v[l]) break;
alpar@9 205 }
alpar@9 206 if (t <= len) continue;
alpar@9 207 /* otherwise, let alpha = max{|A[l,jk]|: I[l] = 0} and let l'
alpar@9 208 be such that alpha = |A[l',jk]| */
alpar@9 209 alpha = 0.0, ll = 0;
alpar@9 210 for (t = 1; t <= len; t++)
alpar@9 211 { l = ind[t];
alpar@9 212 if (I[l] == 0 && alpha < fabs(val[t]))
alpar@9 213 alpha = fabs(val[t]), ll = l;
alpar@9 214 }
alpar@9 215 /* if alpha = 0, continue to the next k */
alpar@9 216 if (alpha == 0.0) continue;
alpar@9 217 /* B := B union {jk} */
alpar@9 218 glp_set_col_stat(lp, jk, GLP_BS);
alpar@9 219 I[ll] = 1;
alpar@9 220 v[ll] = alpha;
alpar@9 221 /* r[l] := r[l] + 1 for all l such that |A[l,jk]| != 0 */
alpar@9 222 for (t = 1; t <= len; t++)
alpar@9 223 { l = ind[t];
alpar@9 224 if (val[t] != 0.0) r[l]++;
alpar@9 225 }
alpar@9 226 }
alpar@9 227 /*** STEP 3 ***/
alpar@9 228 /* add an artificial variable (auxiliary variable for equality
alpar@9 229 constraint) to cover each remaining uncovered row */
alpar@9 230 for (i = 1; i <= m; i++)
alpar@9 231 if (I[i] == 0) glp_set_row_stat(lp, i, GLP_BS);
alpar@9 232 /* free working arrays */
alpar@9 233 xfree(C);
alpar@9 234 xfree(I);
alpar@9 235 xfree(r);
alpar@9 236 xfree(v);
alpar@9 237 xfree(ind);
alpar@9 238 xfree(val);
alpar@9 239 return;
alpar@9 240 }
alpar@9 241
alpar@9 242 /***********************************************************************
alpar@9 243 * NAME
alpar@9 244 *
alpar@9 245 * glp_cpx_basis - construct Bixby's initial LP basis
alpar@9 246 *
alpar@9 247 * SYNOPSIS
alpar@9 248 *
alpar@9 249 * void glp_cpx_basis(glp_prob *lp);
alpar@9 250 *
alpar@9 251 * DESCRIPTION
alpar@9 252 *
alpar@9 253 * The routine glp_cpx_basis constructs an advanced initial basis for
alpar@9 254 * the specified problem object.
alpar@9 255 *
alpar@9 256 * The routine is based on Bixby's algorithm described in the paper:
alpar@9 257 *
alpar@9 258 * Robert E. Bixby. Implementing the Simplex Method: The Initial Basis.
alpar@9 259 * ORSA Journal on Computing, Vol. 4, No. 3, 1992, pp. 267-84. */
alpar@9 260
alpar@9 261 void glp_cpx_basis(glp_prob *lp)
alpar@9 262 { if (lp->m == 0 || lp->n == 0)
alpar@9 263 glp_std_basis(lp);
alpar@9 264 else
alpar@9 265 cpx_basis(lp);
alpar@9 266 return;
alpar@9 267 }
alpar@9 268
alpar@9 269 /* eof */