lemon-project-template-glpk

annotate deps/glpk/src/glplpx02.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 /* glplpx02.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 /***********************************************************************
alpar@9 28 * NAME
alpar@9 29 *
alpar@9 30 * lpx_put_solution - store basic solution components
alpar@9 31 *
alpar@9 32 * SYNOPSIS
alpar@9 33 *
alpar@9 34 * void lpx_put_solution(glp_prob *lp, int inval, const int *p_stat,
alpar@9 35 * const int *d_stat, const double *obj_val, const int r_stat[],
alpar@9 36 * const double r_prim[], const double r_dual[], const int c_stat[],
alpar@9 37 * const double c_prim[], const double c_dual[])
alpar@9 38 *
alpar@9 39 * DESCRIPTION
alpar@9 40 *
alpar@9 41 * The routine lpx_put_solution stores basic solution components to the
alpar@9 42 * specified problem object.
alpar@9 43 *
alpar@9 44 * The parameter inval is the basis factorization invalidity flag.
alpar@9 45 * If this flag is clear, the current status of the basis factorization
alpar@9 46 * remains unchanged. If this flag is set, the routine invalidates the
alpar@9 47 * basis factorization.
alpar@9 48 *
alpar@9 49 * The parameter p_stat is a pointer to the status of primal basic
alpar@9 50 * solution, which should be specified as follows:
alpar@9 51 *
alpar@9 52 * GLP_UNDEF - primal solution is undefined;
alpar@9 53 * GLP_FEAS - primal solution is feasible;
alpar@9 54 * GLP_INFEAS - primal solution is infeasible;
alpar@9 55 * GLP_NOFEAS - no primal feasible solution exists.
alpar@9 56 *
alpar@9 57 * If the parameter p_stat is NULL, the current status of primal basic
alpar@9 58 * solution remains unchanged.
alpar@9 59 *
alpar@9 60 * The parameter d_stat is a pointer to the status of dual basic
alpar@9 61 * solution, which should be specified as follows:
alpar@9 62 *
alpar@9 63 * GLP_UNDEF - dual solution is undefined;
alpar@9 64 * GLP_FEAS - dual solution is feasible;
alpar@9 65 * GLP_INFEAS - dual solution is infeasible;
alpar@9 66 * GLP_NOFEAS - no dual feasible solution exists.
alpar@9 67 *
alpar@9 68 * If the parameter d_stat is NULL, the current status of dual basic
alpar@9 69 * solution remains unchanged.
alpar@9 70 *
alpar@9 71 * The parameter obj_val is a pointer to the objective function value.
alpar@9 72 * If it is NULL, the current value of the objective function remains
alpar@9 73 * unchanged.
alpar@9 74 *
alpar@9 75 * The array element r_stat[i], 1 <= i <= m (where m is the number of
alpar@9 76 * rows in the problem object), specifies the status of i-th auxiliary
alpar@9 77 * variable, which should be specified as follows:
alpar@9 78 *
alpar@9 79 * GLP_BS - basic variable;
alpar@9 80 * GLP_NL - non-basic variable on lower bound;
alpar@9 81 * GLP_NU - non-basic variable on upper bound;
alpar@9 82 * GLP_NF - non-basic free variable;
alpar@9 83 * GLP_NS - non-basic fixed variable.
alpar@9 84 *
alpar@9 85 * If the parameter r_stat is NULL, the current statuses of auxiliary
alpar@9 86 * variables remain unchanged.
alpar@9 87 *
alpar@9 88 * The array element r_prim[i], 1 <= i <= m (where m is the number of
alpar@9 89 * rows in the problem object), specifies a primal value of i-th
alpar@9 90 * auxiliary variable. If the parameter r_prim is NULL, the current
alpar@9 91 * primal values of auxiliary variables remain unchanged.
alpar@9 92 *
alpar@9 93 * The array element r_dual[i], 1 <= i <= m (where m is the number of
alpar@9 94 * rows in the problem object), specifies a dual value (reduced cost)
alpar@9 95 * of i-th auxiliary variable. If the parameter r_dual is NULL, the
alpar@9 96 * current dual values of auxiliary variables remain unchanged.
alpar@9 97 *
alpar@9 98 * The array element c_stat[j], 1 <= j <= n (where n is the number of
alpar@9 99 * columns in the problem object), specifies the status of j-th
alpar@9 100 * structural variable, which should be specified as follows:
alpar@9 101 *
alpar@9 102 * GLP_BS - basic variable;
alpar@9 103 * GLP_NL - non-basic variable on lower bound;
alpar@9 104 * GLP_NU - non-basic variable on upper bound;
alpar@9 105 * GLP_NF - non-basic free variable;
alpar@9 106 * GLP_NS - non-basic fixed variable.
alpar@9 107 *
alpar@9 108 * If the parameter c_stat is NULL, the current statuses of structural
alpar@9 109 * variables remain unchanged.
alpar@9 110 *
alpar@9 111 * The array element c_prim[j], 1 <= j <= n (where n is the number of
alpar@9 112 * columns in the problem object), specifies a primal value of j-th
alpar@9 113 * structural variable. If the parameter c_prim is NULL, the current
alpar@9 114 * primal values of structural variables remain unchanged.
alpar@9 115 *
alpar@9 116 * The array element c_dual[j], 1 <= j <= n (where n is the number of
alpar@9 117 * columns in the problem object), specifies a dual value (reduced cost)
alpar@9 118 * of j-th structural variable. If the parameter c_dual is NULL, the
alpar@9 119 * current dual values of structural variables remain unchanged. */
alpar@9 120
alpar@9 121 void lpx_put_solution(glp_prob *lp, int inval, const int *p_stat,
alpar@9 122 const int *d_stat, const double *obj_val, const int r_stat[],
alpar@9 123 const double r_prim[], const double r_dual[], const int c_stat[],
alpar@9 124 const double c_prim[], const double c_dual[])
alpar@9 125 { GLPROW *row;
alpar@9 126 GLPCOL *col;
alpar@9 127 int i, j;
alpar@9 128 /* invalidate the basis factorization, if required */
alpar@9 129 if (inval) lp->valid = 0;
alpar@9 130 /* store primal status */
alpar@9 131 if (p_stat != NULL)
alpar@9 132 { if (!(*p_stat == GLP_UNDEF || *p_stat == GLP_FEAS ||
alpar@9 133 *p_stat == GLP_INFEAS || *p_stat == GLP_NOFEAS))
alpar@9 134 xerror("lpx_put_solution: p_stat = %d; invalid primal statu"
alpar@9 135 "s\n", *p_stat);
alpar@9 136 lp->pbs_stat = *p_stat;
alpar@9 137 }
alpar@9 138 /* store dual status */
alpar@9 139 if (d_stat != NULL)
alpar@9 140 { if (!(*d_stat == GLP_UNDEF || *d_stat == GLP_FEAS ||
alpar@9 141 *d_stat == GLP_INFEAS || *d_stat == GLP_NOFEAS))
alpar@9 142 xerror("lpx_put_solution: d_stat = %d; invalid dual status "
alpar@9 143 "\n", *d_stat);
alpar@9 144 lp->dbs_stat = *d_stat;
alpar@9 145 }
alpar@9 146 /* store objective function value */
alpar@9 147 if (obj_val != NULL) lp->obj_val = *obj_val;
alpar@9 148 /* store row solution components */
alpar@9 149 for (i = 1; i <= lp->m; i++)
alpar@9 150 { row = lp->row[i];
alpar@9 151 if (r_stat != NULL)
alpar@9 152 { if (!(r_stat[i] == GLP_BS ||
alpar@9 153 row->type == GLP_FR && r_stat[i] == GLP_NF ||
alpar@9 154 row->type == GLP_LO && r_stat[i] == GLP_NL ||
alpar@9 155 row->type == GLP_UP && r_stat[i] == GLP_NU ||
alpar@9 156 row->type == GLP_DB && r_stat[i] == GLP_NL ||
alpar@9 157 row->type == GLP_DB && r_stat[i] == GLP_NU ||
alpar@9 158 row->type == GLP_FX && r_stat[i] == GLP_NS))
alpar@9 159 xerror("lpx_put_solution: r_stat[%d] = %d; invalid row s"
alpar@9 160 "tatus\n", i, r_stat[i]);
alpar@9 161 row->stat = r_stat[i];
alpar@9 162 }
alpar@9 163 if (r_prim != NULL) row->prim = r_prim[i];
alpar@9 164 if (r_dual != NULL) row->dual = r_dual[i];
alpar@9 165 }
alpar@9 166 /* store column solution components */
alpar@9 167 for (j = 1; j <= lp->n; j++)
alpar@9 168 { col = lp->col[j];
alpar@9 169 if (c_stat != NULL)
alpar@9 170 { if (!(c_stat[j] == GLP_BS ||
alpar@9 171 col->type == GLP_FR && c_stat[j] == GLP_NF ||
alpar@9 172 col->type == GLP_LO && c_stat[j] == GLP_NL ||
alpar@9 173 col->type == GLP_UP && c_stat[j] == GLP_NU ||
alpar@9 174 col->type == GLP_DB && c_stat[j] == GLP_NL ||
alpar@9 175 col->type == GLP_DB && c_stat[j] == GLP_NU ||
alpar@9 176 col->type == GLP_FX && c_stat[j] == GLP_NS))
alpar@9 177 xerror("lpx_put_solution: c_stat[%d] = %d; invalid colum"
alpar@9 178 "n status\n", j, c_stat[j]);
alpar@9 179 col->stat = c_stat[j];
alpar@9 180 }
alpar@9 181 if (c_prim != NULL) col->prim = c_prim[j];
alpar@9 182 if (c_dual != NULL) col->dual = c_dual[j];
alpar@9 183 }
alpar@9 184 return;
alpar@9 185 }
alpar@9 186
alpar@9 187 /*----------------------------------------------------------------------
alpar@9 188 -- lpx_put_mip_soln - store mixed integer solution components.
alpar@9 189 --
alpar@9 190 -- *Synopsis*
alpar@9 191 --
alpar@9 192 -- #include "glplpx.h"
alpar@9 193 -- void lpx_put_mip_soln(glp_prob *lp, int i_stat, double row_mipx[],
alpar@9 194 -- double col_mipx[]);
alpar@9 195 --
alpar@9 196 -- *Description*
alpar@9 197 --
alpar@9 198 -- The routine lpx_put_mip_soln stores solution components obtained by
alpar@9 199 -- branch-and-bound solver into the specified problem object.
alpar@9 200 --
alpar@9 201 -- NOTE: This routine is intended for internal use only. */
alpar@9 202
alpar@9 203 void lpx_put_mip_soln(glp_prob *lp, int i_stat, double row_mipx[],
alpar@9 204 double col_mipx[])
alpar@9 205 { GLPROW *row;
alpar@9 206 GLPCOL *col;
alpar@9 207 int i, j;
alpar@9 208 double sum;
alpar@9 209 /* store mixed integer status */
alpar@9 210 #if 0
alpar@9 211 if (!(i_stat == LPX_I_UNDEF || i_stat == LPX_I_OPT ||
alpar@9 212 i_stat == LPX_I_FEAS || i_stat == LPX_I_NOFEAS))
alpar@9 213 fault("lpx_put_mip_soln: i_stat = %d; invalid mixed integer st"
alpar@9 214 "atus", i_stat);
alpar@9 215 lp->i_stat = i_stat;
alpar@9 216 #else
alpar@9 217 switch (i_stat)
alpar@9 218 { case LPX_I_UNDEF:
alpar@9 219 lp->mip_stat = GLP_UNDEF; break;
alpar@9 220 case LPX_I_OPT:
alpar@9 221 lp->mip_stat = GLP_OPT; break;
alpar@9 222 case LPX_I_FEAS:
alpar@9 223 lp->mip_stat = GLP_FEAS; break;
alpar@9 224 case LPX_I_NOFEAS:
alpar@9 225 lp->mip_stat = GLP_NOFEAS; break;
alpar@9 226 default:
alpar@9 227 xerror("lpx_put_mip_soln: i_stat = %d; invalid mixed intege"
alpar@9 228 "r status\n", i_stat);
alpar@9 229 }
alpar@9 230 #endif
alpar@9 231 /* store row solution components */
alpar@9 232 if (row_mipx != NULL)
alpar@9 233 { for (i = 1; i <= lp->m; i++)
alpar@9 234 { row = lp->row[i];
alpar@9 235 row->mipx = row_mipx[i];
alpar@9 236 }
alpar@9 237 }
alpar@9 238 /* store column solution components */
alpar@9 239 if (col_mipx != NULL)
alpar@9 240 { for (j = 1; j <= lp->n; j++)
alpar@9 241 { col = lp->col[j];
alpar@9 242 col->mipx = col_mipx[j];
alpar@9 243 }
alpar@9 244 }
alpar@9 245 /* if the solution is claimed to be integer feasible, check it */
alpar@9 246 if (lp->mip_stat == GLP_OPT || lp->mip_stat == GLP_FEAS)
alpar@9 247 { for (j = 1; j <= lp->n; j++)
alpar@9 248 { col = lp->col[j];
alpar@9 249 if (col->kind == GLP_IV && col->mipx != floor(col->mipx))
alpar@9 250 xerror("lpx_put_mip_soln: col_mipx[%d] = %.*g; must be i"
alpar@9 251 "ntegral\n", j, DBL_DIG, col->mipx);
alpar@9 252 }
alpar@9 253 }
alpar@9 254 /* compute the objective function value */
alpar@9 255 sum = lp->c0;
alpar@9 256 for (j = 1; j <= lp->n; j++)
alpar@9 257 { col = lp->col[j];
alpar@9 258 sum += col->coef * col->mipx;
alpar@9 259 }
alpar@9 260 lp->mip_obj = sum;
alpar@9 261 return;
alpar@9 262 }
alpar@9 263
alpar@9 264 /* eof */