1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/src/glpapi10.c Mon Dec 06 13:09:21 2010 +0100
1.3 @@ -0,0 +1,282 @@
1.4 +/* glpapi10.c (solution checking routines) */
1.5 +
1.6 +/***********************************************************************
1.7 +* This code is part of GLPK (GNU Linear Programming Kit).
1.8 +*
1.9 +* Copyright (C) 2000, 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008,
1.10 +* 2009, 2010 Andrew Makhorin, Department for Applied Informatics,
1.11 +* Moscow Aviation Institute, Moscow, Russia. All rights reserved.
1.12 +* E-mail: <mao@gnu.org>.
1.13 +*
1.14 +* GLPK is free software: you can redistribute it and/or modify it
1.15 +* under the terms of the GNU General Public License as published by
1.16 +* the Free Software Foundation, either version 3 of the License, or
1.17 +* (at your option) any later version.
1.18 +*
1.19 +* GLPK is distributed in the hope that it will be useful, but WITHOUT
1.20 +* ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
1.21 +* or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public
1.22 +* License for more details.
1.23 +*
1.24 +* You should have received a copy of the GNU General Public License
1.25 +* along with GLPK. If not, see <http://www.gnu.org/licenses/>.
1.26 +***********************************************************************/
1.27 +
1.28 +#include "glpapi.h"
1.29 +
1.30 +void _glp_check_kkt(glp_prob *P, int sol, int cond, double *_ae_max,
1.31 + int *_ae_ind, double *_re_max, int *_re_ind)
1.32 +{ /* check feasibility and optimality conditions */
1.33 + int m = P->m;
1.34 + int n = P->n;
1.35 + GLPROW *row;
1.36 + GLPCOL *col;
1.37 + GLPAIJ *aij;
1.38 + int i, j, ae_ind, re_ind;
1.39 + double e, sp, sn, t, ae_max, re_max;
1.40 + if (!(sol == GLP_SOL || sol == GLP_IPT || sol == GLP_MIP))
1.41 + xerror("glp_check_kkt: sol = %d; invalid solution indicator\n",
1.42 + sol);
1.43 + if (!(cond == GLP_KKT_PE || cond == GLP_KKT_PB ||
1.44 + cond == GLP_KKT_DE || cond == GLP_KKT_DB ||
1.45 + cond == GLP_KKT_CS))
1.46 + xerror("glp_check_kkt: cond = %d; invalid condition indicator "
1.47 + "\n", cond);
1.48 + ae_max = re_max = 0.0;
1.49 + ae_ind = re_ind = 0;
1.50 + if (cond == GLP_KKT_PE)
1.51 + { /* xR - A * xS = 0 */
1.52 + for (i = 1; i <= m; i++)
1.53 + { row = P->row[i];
1.54 + sp = sn = 0.0;
1.55 + /* t := xR[i] */
1.56 + if (sol == GLP_SOL)
1.57 + t = row->prim;
1.58 + else if (sol == GLP_IPT)
1.59 + t = row->pval;
1.60 + else if (sol == GLP_MIP)
1.61 + t = row->mipx;
1.62 + else
1.63 + xassert(sol != sol);
1.64 + if (t >= 0.0) sp += t; else sn -= t;
1.65 + for (aij = row->ptr; aij != NULL; aij = aij->r_next)
1.66 + { col = aij->col;
1.67 + /* t := - a[i,j] * xS[j] */
1.68 + if (sol == GLP_SOL)
1.69 + t = - aij->val * col->prim;
1.70 + else if (sol == GLP_IPT)
1.71 + t = - aij->val * col->pval;
1.72 + else if (sol == GLP_MIP)
1.73 + t = - aij->val * col->mipx;
1.74 + else
1.75 + xassert(sol != sol);
1.76 + if (t >= 0.0) sp += t; else sn -= t;
1.77 + }
1.78 + /* absolute error */
1.79 + e = fabs(sp - sn);
1.80 + if (ae_max < e)
1.81 + ae_max = e, ae_ind = i;
1.82 + /* relative error */
1.83 + e /= (1.0 + sp + sn);
1.84 + if (re_max < e)
1.85 + re_max = e, re_ind = i;
1.86 + }
1.87 + }
1.88 + else if (cond == GLP_KKT_PB)
1.89 + { /* lR <= xR <= uR */
1.90 + for (i = 1; i <= m; i++)
1.91 + { row = P->row[i];
1.92 + /* t := xR[i] */
1.93 + if (sol == GLP_SOL)
1.94 + t = row->prim;
1.95 + else if (sol == GLP_IPT)
1.96 + t = row->pval;
1.97 + else if (sol == GLP_MIP)
1.98 + t = row->mipx;
1.99 + else
1.100 + xassert(sol != sol);
1.101 + /* check lower bound */
1.102 + if (row->type == GLP_LO || row->type == GLP_DB ||
1.103 + row->type == GLP_FX)
1.104 + { if (t < row->lb)
1.105 + { /* absolute error */
1.106 + e = row->lb - t;
1.107 + if (ae_max < e)
1.108 + ae_max = e, ae_ind = i;
1.109 + /* relative error */
1.110 + e /= (1.0 + fabs(row->lb));
1.111 + if (re_max < e)
1.112 + re_max = e, re_ind = i;
1.113 + }
1.114 + }
1.115 + /* check upper bound */
1.116 + if (row->type == GLP_UP || row->type == GLP_DB ||
1.117 + row->type == GLP_FX)
1.118 + { if (t > row->ub)
1.119 + { /* absolute error */
1.120 + e = t - row->ub;
1.121 + if (ae_max < e)
1.122 + ae_max = e, ae_ind = i;
1.123 + /* relative error */
1.124 + e /= (1.0 + fabs(row->ub));
1.125 + if (re_max < e)
1.126 + re_max = e, re_ind = i;
1.127 + }
1.128 + }
1.129 + }
1.130 + /* lS <= xS <= uS */
1.131 + for (j = 1; j <= n; j++)
1.132 + { col = P->col[j];
1.133 + /* t := xS[j] */
1.134 + if (sol == GLP_SOL)
1.135 + t = col->prim;
1.136 + else if (sol == GLP_IPT)
1.137 + t = col->pval;
1.138 + else if (sol == GLP_MIP)
1.139 + t = col->mipx;
1.140 + else
1.141 + xassert(sol != sol);
1.142 + /* check lower bound */
1.143 + if (col->type == GLP_LO || col->type == GLP_DB ||
1.144 + col->type == GLP_FX)
1.145 + { if (t < col->lb)
1.146 + { /* absolute error */
1.147 + e = col->lb - t;
1.148 + if (ae_max < e)
1.149 + ae_max = e, ae_ind = m+j;
1.150 + /* relative error */
1.151 + e /= (1.0 + fabs(col->lb));
1.152 + if (re_max < e)
1.153 + re_max = e, re_ind = m+j;
1.154 + }
1.155 + }
1.156 + /* check upper bound */
1.157 + if (col->type == GLP_UP || col->type == GLP_DB ||
1.158 + col->type == GLP_FX)
1.159 + { if (t > col->ub)
1.160 + { /* absolute error */
1.161 + e = t - col->ub;
1.162 + if (ae_max < e)
1.163 + ae_max = e, ae_ind = m+j;
1.164 + /* relative error */
1.165 + e /= (1.0 + fabs(col->ub));
1.166 + if (re_max < e)
1.167 + re_max = e, re_ind = m+j;
1.168 + }
1.169 + }
1.170 + }
1.171 + }
1.172 + else if (cond == GLP_KKT_DE)
1.173 + { /* A' * (lambdaR - cR) + (lambdaS - cS) = 0 */
1.174 + for (j = 1; j <= n; j++)
1.175 + { col = P->col[j];
1.176 + sp = sn = 0.0;
1.177 + /* t := lambdaS[j] - cS[j] */
1.178 + if (sol == GLP_SOL)
1.179 + t = col->dual - col->coef;
1.180 + else if (sol == GLP_IPT)
1.181 + t = col->dval - col->coef;
1.182 + else
1.183 + xassert(sol != sol);
1.184 + if (t >= 0.0) sp += t; else sn -= t;
1.185 + for (aij = col->ptr; aij != NULL; aij = aij->c_next)
1.186 + { row = aij->row;
1.187 + /* t := a[i,j] * (lambdaR[i] - cR[i]) */
1.188 + if (sol == GLP_SOL)
1.189 + t = aij->val * row->dual;
1.190 + else if (sol == GLP_IPT)
1.191 + t = aij->val * row->dval;
1.192 + else
1.193 + xassert(sol != sol);
1.194 + if (t >= 0.0) sp += t; else sn -= t;
1.195 + }
1.196 + /* absolute error */
1.197 + e = fabs(sp - sn);
1.198 + if (ae_max < e)
1.199 + ae_max = e, ae_ind = m+j;
1.200 + /* relative error */
1.201 + e /= (1.0 + sp + sn);
1.202 + if (re_max < e)
1.203 + re_max = e, re_ind = m+j;
1.204 + }
1.205 + }
1.206 + else if (cond == GLP_KKT_DB)
1.207 + { /* check lambdaR */
1.208 + for (i = 1; i <= m; i++)
1.209 + { row = P->row[i];
1.210 + /* t := lambdaR[i] */
1.211 + if (sol == GLP_SOL)
1.212 + t = row->dual;
1.213 + else if (sol == GLP_IPT)
1.214 + t = row->dval;
1.215 + else
1.216 + xassert(sol != sol);
1.217 + /* correct sign */
1.218 + if (P->dir == GLP_MIN)
1.219 + t = + t;
1.220 + else if (P->dir == GLP_MAX)
1.221 + t = - t;
1.222 + else
1.223 + xassert(P != P);
1.224 + /* check for positivity */
1.225 + if (row->type == GLP_FR || row->type == GLP_LO)
1.226 + { if (t < 0.0)
1.227 + { e = - t;
1.228 + if (ae_max < e)
1.229 + ae_max = re_max = e, ae_ind = re_ind = i;
1.230 + }
1.231 + }
1.232 + /* check for negativity */
1.233 + if (row->type == GLP_FR || row->type == GLP_UP)
1.234 + { if (t > 0.0)
1.235 + { e = + t;
1.236 + if (ae_max < e)
1.237 + ae_max = re_max = e, ae_ind = re_ind = i;
1.238 + }
1.239 + }
1.240 + }
1.241 + /* check lambdaS */
1.242 + for (j = 1; j <= n; j++)
1.243 + { col = P->col[j];
1.244 + /* t := lambdaS[j] */
1.245 + if (sol == GLP_SOL)
1.246 + t = col->dual;
1.247 + else if (sol == GLP_IPT)
1.248 + t = col->dval;
1.249 + else
1.250 + xassert(sol != sol);
1.251 + /* correct sign */
1.252 + if (P->dir == GLP_MIN)
1.253 + t = + t;
1.254 + else if (P->dir == GLP_MAX)
1.255 + t = - t;
1.256 + else
1.257 + xassert(P != P);
1.258 + /* check for positivity */
1.259 + if (col->type == GLP_FR || col->type == GLP_LO)
1.260 + { if (t < 0.0)
1.261 + { e = - t;
1.262 + if (ae_max < e)
1.263 + ae_max = re_max = e, ae_ind = re_ind = m+j;
1.264 + }
1.265 + }
1.266 + /* check for negativity */
1.267 + if (col->type == GLP_FR || col->type == GLP_UP)
1.268 + { if (t > 0.0)
1.269 + { e = + t;
1.270 + if (ae_max < e)
1.271 + ae_max = re_max = e, ae_ind = re_ind = m+j;
1.272 + }
1.273 + }
1.274 + }
1.275 + }
1.276 + else
1.277 + xassert(cond != cond);
1.278 + if (_ae_max != NULL) *_ae_max = ae_max;
1.279 + if (_ae_ind != NULL) *_ae_ind = ae_ind;
1.280 + if (_re_max != NULL) *_re_max = re_max;
1.281 + if (_re_ind != NULL) *_re_ind = re_ind;
1.282 + return;
1.283 +}
1.284 +
1.285 +/* eof */