1.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
     1.2 +++ b/deps/glpk/src/glpapi10.c	Sun Nov 06 20:59:10 2011 +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, 2011 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 */