1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/src/glpapi01.c Mon Dec 06 13:09:21 2010 +0100
1.3 @@ -0,0 +1,1570 @@
1.4 +/* glpapi01.c (problem creating and modifying 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 "glpios.h"
1.29 +
1.30 +/* CAUTION: DO NOT CHANGE THE LIMITS BELOW */
1.31 +
1.32 +#define M_MAX 100000000 /* = 100*10^6 */
1.33 +/* maximal number of rows in the problem object */
1.34 +
1.35 +#define N_MAX 100000000 /* = 100*10^6 */
1.36 +/* maximal number of columns in the problem object */
1.37 +
1.38 +#define NNZ_MAX 500000000 /* = 500*10^6 */
1.39 +/* maximal number of constraint coefficients in the problem object */
1.40 +
1.41 +/***********************************************************************
1.42 +* NAME
1.43 +*
1.44 +* glp_create_prob - create problem object
1.45 +*
1.46 +* SYNOPSIS
1.47 +*
1.48 +* glp_prob *glp_create_prob(void);
1.49 +*
1.50 +* DESCRIPTION
1.51 +*
1.52 +* The routine glp_create_prob creates a new problem object, which is
1.53 +* initially "empty", i.e. has no rows and columns.
1.54 +*
1.55 +* RETURNS
1.56 +*
1.57 +* The routine returns a pointer to the object created, which should be
1.58 +* used in any subsequent operations on this object. */
1.59 +
1.60 +static void create_prob(glp_prob *lp)
1.61 +{ lp->magic = GLP_PROB_MAGIC;
1.62 + lp->pool = dmp_create_pool();
1.63 +#if 0 /* 17/XI-2009 */
1.64 + lp->cps = xmalloc(sizeof(struct LPXCPS));
1.65 + lpx_reset_parms(lp);
1.66 +#else
1.67 + lp->parms = NULL;
1.68 +#endif
1.69 + lp->tree = NULL;
1.70 +#if 0
1.71 + lp->lwa = 0;
1.72 + lp->cwa = NULL;
1.73 +#endif
1.74 + /* LP/MIP data */
1.75 + lp->name = NULL;
1.76 + lp->obj = NULL;
1.77 + lp->dir = GLP_MIN;
1.78 + lp->c0 = 0.0;
1.79 + lp->m_max = 100;
1.80 + lp->n_max = 200;
1.81 + lp->m = lp->n = 0;
1.82 + lp->nnz = 0;
1.83 + lp->row = xcalloc(1+lp->m_max, sizeof(GLPROW *));
1.84 + lp->col = xcalloc(1+lp->n_max, sizeof(GLPCOL *));
1.85 + lp->r_tree = lp->c_tree = NULL;
1.86 + /* basis factorization */
1.87 + lp->valid = 0;
1.88 + lp->head = xcalloc(1+lp->m_max, sizeof(int));
1.89 + lp->bfcp = NULL;
1.90 + lp->bfd = NULL;
1.91 + /* basic solution (LP) */
1.92 + lp->pbs_stat = lp->dbs_stat = GLP_UNDEF;
1.93 + lp->obj_val = 0.0;
1.94 + lp->it_cnt = 0;
1.95 + lp->some = 0;
1.96 + /* interior-point solution (LP) */
1.97 + lp->ipt_stat = GLP_UNDEF;
1.98 + lp->ipt_obj = 0.0;
1.99 + /* integer solution (MIP) */
1.100 + lp->mip_stat = GLP_UNDEF;
1.101 + lp->mip_obj = 0.0;
1.102 + return;
1.103 +}
1.104 +
1.105 +glp_prob *glp_create_prob(void)
1.106 +{ glp_prob *lp;
1.107 + lp = xmalloc(sizeof(glp_prob));
1.108 + create_prob(lp);
1.109 + return lp;
1.110 +}
1.111 +
1.112 +/***********************************************************************
1.113 +* NAME
1.114 +*
1.115 +* glp_set_prob_name - assign (change) problem name
1.116 +*
1.117 +* SYNOPSIS
1.118 +*
1.119 +* void glp_set_prob_name(glp_prob *lp, const char *name);
1.120 +*
1.121 +* DESCRIPTION
1.122 +*
1.123 +* The routine glp_set_prob_name assigns a given symbolic name (1 up to
1.124 +* 255 characters) to the specified problem object.
1.125 +*
1.126 +* If the parameter name is NULL or empty string, the routine erases an
1.127 +* existing symbolic name of the problem object. */
1.128 +
1.129 +void glp_set_prob_name(glp_prob *lp, const char *name)
1.130 +{ glp_tree *tree = lp->tree;
1.131 + if (tree != NULL && tree->reason != 0)
1.132 + xerror("glp_set_prob_name: operation not allowed\n");
1.133 + if (lp->name != NULL)
1.134 + { dmp_free_atom(lp->pool, lp->name, strlen(lp->name)+1);
1.135 + lp->name = NULL;
1.136 + }
1.137 + if (!(name == NULL || name[0] == '\0'))
1.138 + { int k;
1.139 + for (k = 0; name[k] != '\0'; k++)
1.140 + { if (k == 256)
1.141 + xerror("glp_set_prob_name: problem name too long\n");
1.142 + if (iscntrl((unsigned char)name[k]))
1.143 + xerror("glp_set_prob_name: problem name contains invalid"
1.144 + " character(s)\n");
1.145 + }
1.146 + lp->name = dmp_get_atom(lp->pool, strlen(name)+1);
1.147 + strcpy(lp->name, name);
1.148 + }
1.149 + return;
1.150 +}
1.151 +
1.152 +/***********************************************************************
1.153 +* NAME
1.154 +*
1.155 +* glp_set_obj_name - assign (change) objective function name
1.156 +*
1.157 +* SYNOPSIS
1.158 +*
1.159 +* void glp_set_obj_name(glp_prob *lp, const char *name);
1.160 +*
1.161 +* DESCRIPTION
1.162 +*
1.163 +* The routine glp_set_obj_name assigns a given symbolic name (1 up to
1.164 +* 255 characters) to the objective function of the specified problem
1.165 +* object.
1.166 +*
1.167 +* If the parameter name is NULL or empty string, the routine erases an
1.168 +* existing name of the objective function. */
1.169 +
1.170 +void glp_set_obj_name(glp_prob *lp, const char *name)
1.171 +{ glp_tree *tree = lp->tree;
1.172 + if (tree != NULL && tree->reason != 0)
1.173 + xerror("glp_set_obj_name: operation not allowed\n");
1.174 + if (lp->obj != NULL)
1.175 + { dmp_free_atom(lp->pool, lp->obj, strlen(lp->obj)+1);
1.176 + lp->obj = NULL;
1.177 + }
1.178 + if (!(name == NULL || name[0] == '\0'))
1.179 + { int k;
1.180 + for (k = 0; name[k] != '\0'; k++)
1.181 + { if (k == 256)
1.182 + xerror("glp_set_obj_name: objective name too long\n");
1.183 + if (iscntrl((unsigned char)name[k]))
1.184 + xerror("glp_set_obj_name: objective name contains invali"
1.185 + "d character(s)\n");
1.186 + }
1.187 + lp->obj = dmp_get_atom(lp->pool, strlen(name)+1);
1.188 + strcpy(lp->obj, name);
1.189 + }
1.190 + return;
1.191 +}
1.192 +
1.193 +/***********************************************************************
1.194 +* NAME
1.195 +*
1.196 +* glp_set_obj_dir - set (change) optimization direction flag
1.197 +*
1.198 +* SYNOPSIS
1.199 +*
1.200 +* void glp_set_obj_dir(glp_prob *lp, int dir);
1.201 +*
1.202 +* DESCRIPTION
1.203 +*
1.204 +* The routine glp_set_obj_dir sets (changes) optimization direction
1.205 +* flag (i.e. "sense" of the objective function) as specified by the
1.206 +* parameter dir:
1.207 +*
1.208 +* GLP_MIN - minimization;
1.209 +* GLP_MAX - maximization. */
1.210 +
1.211 +void glp_set_obj_dir(glp_prob *lp, int dir)
1.212 +{ glp_tree *tree = lp->tree;
1.213 + if (tree != NULL && tree->reason != 0)
1.214 + xerror("glp_set_obj_dir: operation not allowed\n");
1.215 + if (!(dir == GLP_MIN || dir == GLP_MAX))
1.216 + xerror("glp_set_obj_dir: dir = %d; invalid direction flag\n",
1.217 + dir);
1.218 + lp->dir = dir;
1.219 + return;
1.220 +}
1.221 +
1.222 +/***********************************************************************
1.223 +* NAME
1.224 +*
1.225 +* glp_add_rows - add new rows to problem object
1.226 +*
1.227 +* SYNOPSIS
1.228 +*
1.229 +* int glp_add_rows(glp_prob *lp, int nrs);
1.230 +*
1.231 +* DESCRIPTION
1.232 +*
1.233 +* The routine glp_add_rows adds nrs rows (constraints) to the specified
1.234 +* problem object. New rows are always added to the end of the row list,
1.235 +* so the ordinal numbers of existing rows remain unchanged.
1.236 +*
1.237 +* Being added each new row is initially free (unbounded) and has empty
1.238 +* list of the constraint coefficients.
1.239 +*
1.240 +* RETURNS
1.241 +*
1.242 +* The routine glp_add_rows returns the ordinal number of the first new
1.243 +* row added to the problem object. */
1.244 +
1.245 +int glp_add_rows(glp_prob *lp, int nrs)
1.246 +{ glp_tree *tree = lp->tree;
1.247 + GLPROW *row;
1.248 + int m_new, i;
1.249 + /* determine new number of rows */
1.250 + if (nrs < 1)
1.251 + xerror("glp_add_rows: nrs = %d; invalid number of rows\n",
1.252 + nrs);
1.253 + if (nrs > M_MAX - lp->m)
1.254 + xerror("glp_add_rows: nrs = %d; too many rows\n", nrs);
1.255 + m_new = lp->m + nrs;
1.256 + /* increase the room, if necessary */
1.257 + if (lp->m_max < m_new)
1.258 + { GLPROW **save = lp->row;
1.259 + while (lp->m_max < m_new)
1.260 + { lp->m_max += lp->m_max;
1.261 + xassert(lp->m_max > 0);
1.262 + }
1.263 + lp->row = xcalloc(1+lp->m_max, sizeof(GLPROW *));
1.264 + memcpy(&lp->row[1], &save[1], lp->m * sizeof(GLPROW *));
1.265 + xfree(save);
1.266 + /* do not forget about the basis header */
1.267 + xfree(lp->head);
1.268 + lp->head = xcalloc(1+lp->m_max, sizeof(int));
1.269 + }
1.270 + /* add new rows to the end of the row list */
1.271 + for (i = lp->m+1; i <= m_new; i++)
1.272 + { /* create row descriptor */
1.273 + lp->row[i] = row = dmp_get_atom(lp->pool, sizeof(GLPROW));
1.274 + row->i = i;
1.275 + row->name = NULL;
1.276 + row->node = NULL;
1.277 +#if 1 /* 20/IX-2008 */
1.278 + row->level = 0;
1.279 + row->origin = 0;
1.280 + row->klass = 0;
1.281 + if (tree != NULL)
1.282 + { switch (tree->reason)
1.283 + { case 0:
1.284 + break;
1.285 + case GLP_IROWGEN:
1.286 + xassert(tree->curr != NULL);
1.287 + row->level = tree->curr->level;
1.288 + row->origin = GLP_RF_LAZY;
1.289 + break;
1.290 + case GLP_ICUTGEN:
1.291 + xassert(tree->curr != NULL);
1.292 + row->level = tree->curr->level;
1.293 + row->origin = GLP_RF_CUT;
1.294 + break;
1.295 + default:
1.296 + xassert(tree != tree);
1.297 + }
1.298 + }
1.299 +#endif
1.300 + row->type = GLP_FR;
1.301 + row->lb = row->ub = 0.0;
1.302 + row->ptr = NULL;
1.303 + row->rii = 1.0;
1.304 + row->stat = GLP_BS;
1.305 +#if 0
1.306 + row->bind = -1;
1.307 +#else
1.308 + row->bind = 0;
1.309 +#endif
1.310 + row->prim = row->dual = 0.0;
1.311 + row->pval = row->dval = 0.0;
1.312 + row->mipx = 0.0;
1.313 + }
1.314 + /* set new number of rows */
1.315 + lp->m = m_new;
1.316 + /* invalidate the basis factorization */
1.317 + lp->valid = 0;
1.318 +#if 1
1.319 + if (tree != NULL && tree->reason != 0) tree->reopt = 1;
1.320 +#endif
1.321 + /* return the ordinal number of the first row added */
1.322 + return m_new - nrs + 1;
1.323 +}
1.324 +
1.325 +/***********************************************************************
1.326 +* NAME
1.327 +*
1.328 +* glp_add_cols - add new columns to problem object
1.329 +*
1.330 +* SYNOPSIS
1.331 +*
1.332 +* int glp_add_cols(glp_prob *lp, int ncs);
1.333 +*
1.334 +* DESCRIPTION
1.335 +*
1.336 +* The routine glp_add_cols adds ncs columns (structural variables) to
1.337 +* the specified problem object. New columns are always added to the end
1.338 +* of the column list, so the ordinal numbers of existing columns remain
1.339 +* unchanged.
1.340 +*
1.341 +* Being added each new column is initially fixed at zero and has empty
1.342 +* list of the constraint coefficients.
1.343 +*
1.344 +* RETURNS
1.345 +*
1.346 +* The routine glp_add_cols returns the ordinal number of the first new
1.347 +* column added to the problem object. */
1.348 +
1.349 +int glp_add_cols(glp_prob *lp, int ncs)
1.350 +{ glp_tree *tree = lp->tree;
1.351 + GLPCOL *col;
1.352 + int n_new, j;
1.353 + if (tree != NULL && tree->reason != 0)
1.354 + xerror("glp_add_cols: operation not allowed\n");
1.355 + /* determine new number of columns */
1.356 + if (ncs < 1)
1.357 + xerror("glp_add_cols: ncs = %d; invalid number of columns\n",
1.358 + ncs);
1.359 + if (ncs > N_MAX - lp->n)
1.360 + xerror("glp_add_cols: ncs = %d; too many columns\n", ncs);
1.361 + n_new = lp->n + ncs;
1.362 + /* increase the room, if necessary */
1.363 + if (lp->n_max < n_new)
1.364 + { GLPCOL **save = lp->col;
1.365 + while (lp->n_max < n_new)
1.366 + { lp->n_max += lp->n_max;
1.367 + xassert(lp->n_max > 0);
1.368 + }
1.369 + lp->col = xcalloc(1+lp->n_max, sizeof(GLPCOL *));
1.370 + memcpy(&lp->col[1], &save[1], lp->n * sizeof(GLPCOL *));
1.371 + xfree(save);
1.372 + }
1.373 + /* add new columns to the end of the column list */
1.374 + for (j = lp->n+1; j <= n_new; j++)
1.375 + { /* create column descriptor */
1.376 + lp->col[j] = col = dmp_get_atom(lp->pool, sizeof(GLPCOL));
1.377 + col->j = j;
1.378 + col->name = NULL;
1.379 + col->node = NULL;
1.380 + col->kind = GLP_CV;
1.381 + col->type = GLP_FX;
1.382 + col->lb = col->ub = 0.0;
1.383 + col->coef = 0.0;
1.384 + col->ptr = NULL;
1.385 + col->sjj = 1.0;
1.386 + col->stat = GLP_NS;
1.387 +#if 0
1.388 + col->bind = -1;
1.389 +#else
1.390 + col->bind = 0; /* the basis may remain valid */
1.391 +#endif
1.392 + col->prim = col->dual = 0.0;
1.393 + col->pval = col->dval = 0.0;
1.394 + col->mipx = 0.0;
1.395 + }
1.396 + /* set new number of columns */
1.397 + lp->n = n_new;
1.398 + /* return the ordinal number of the first column added */
1.399 + return n_new - ncs + 1;
1.400 +}
1.401 +
1.402 +/***********************************************************************
1.403 +* NAME
1.404 +*
1.405 +* glp_set_row_name - assign (change) row name
1.406 +*
1.407 +* SYNOPSIS
1.408 +*
1.409 +* void glp_set_row_name(glp_prob *lp, int i, const char *name);
1.410 +*
1.411 +* DESCRIPTION
1.412 +*
1.413 +* The routine glp_set_row_name assigns a given symbolic name (1 up to
1.414 +* 255 characters) to i-th row (auxiliary variable) of the specified
1.415 +* problem object.
1.416 +*
1.417 +* If the parameter name is NULL or empty string, the routine erases an
1.418 +* existing name of i-th row. */
1.419 +
1.420 +void glp_set_row_name(glp_prob *lp, int i, const char *name)
1.421 +{ glp_tree *tree = lp->tree;
1.422 + GLPROW *row;
1.423 + if (!(1 <= i && i <= lp->m))
1.424 + xerror("glp_set_row_name: i = %d; row number out of range\n",
1.425 + i);
1.426 + row = lp->row[i];
1.427 + if (tree != NULL && tree->reason != 0)
1.428 + { xassert(tree->curr != NULL);
1.429 + xassert(row->level == tree->curr->level);
1.430 + }
1.431 + if (row->name != NULL)
1.432 + { if (row->node != NULL)
1.433 + { xassert(lp->r_tree != NULL);
1.434 + avl_delete_node(lp->r_tree, row->node);
1.435 + row->node = NULL;
1.436 + }
1.437 + dmp_free_atom(lp->pool, row->name, strlen(row->name)+1);
1.438 + row->name = NULL;
1.439 + }
1.440 + if (!(name == NULL || name[0] == '\0'))
1.441 + { int k;
1.442 + for (k = 0; name[k] != '\0'; k++)
1.443 + { if (k == 256)
1.444 + xerror("glp_set_row_name: i = %d; row name too long\n",
1.445 + i);
1.446 + if (iscntrl((unsigned char)name[k]))
1.447 + xerror("glp_set_row_name: i = %d: row name contains inva"
1.448 + "lid character(s)\n", i);
1.449 + }
1.450 + row->name = dmp_get_atom(lp->pool, strlen(name)+1);
1.451 + strcpy(row->name, name);
1.452 + if (lp->r_tree != NULL)
1.453 + { xassert(row->node == NULL);
1.454 + row->node = avl_insert_node(lp->r_tree, row->name);
1.455 + avl_set_node_link(row->node, row);
1.456 + }
1.457 + }
1.458 + return;
1.459 +}
1.460 +
1.461 +/***********************************************************************
1.462 +* NAME
1.463 +*
1.464 +* glp_set_col_name - assign (change) column name
1.465 +*
1.466 +* SYNOPSIS
1.467 +*
1.468 +* void glp_set_col_name(glp_prob *lp, int j, const char *name);
1.469 +*
1.470 +* DESCRIPTION
1.471 +*
1.472 +* The routine glp_set_col_name assigns a given symbolic name (1 up to
1.473 +* 255 characters) to j-th column (structural variable) of the specified
1.474 +* problem object.
1.475 +*
1.476 +* If the parameter name is NULL or empty string, the routine erases an
1.477 +* existing name of j-th column. */
1.478 +
1.479 +void glp_set_col_name(glp_prob *lp, int j, const char *name)
1.480 +{ glp_tree *tree = lp->tree;
1.481 + GLPCOL *col;
1.482 + if (tree != NULL && tree->reason != 0)
1.483 + xerror("glp_set_col_name: operation not allowed\n");
1.484 + if (!(1 <= j && j <= lp->n))
1.485 + xerror("glp_set_col_name: j = %d; column number out of range\n"
1.486 + , j);
1.487 + col = lp->col[j];
1.488 + if (col->name != NULL)
1.489 + { if (col->node != NULL)
1.490 + { xassert(lp->c_tree != NULL);
1.491 + avl_delete_node(lp->c_tree, col->node);
1.492 + col->node = NULL;
1.493 + }
1.494 + dmp_free_atom(lp->pool, col->name, strlen(col->name)+1);
1.495 + col->name = NULL;
1.496 + }
1.497 + if (!(name == NULL || name[0] == '\0'))
1.498 + { int k;
1.499 + for (k = 0; name[k] != '\0'; k++)
1.500 + { if (k == 256)
1.501 + xerror("glp_set_col_name: j = %d; column name too long\n"
1.502 + , j);
1.503 + if (iscntrl((unsigned char)name[k]))
1.504 + xerror("glp_set_col_name: j = %d: column name contains i"
1.505 + "nvalid character(s)\n", j);
1.506 + }
1.507 + col->name = dmp_get_atom(lp->pool, strlen(name)+1);
1.508 + strcpy(col->name, name);
1.509 + if (lp->c_tree != NULL && col->name != NULL)
1.510 + { xassert(col->node == NULL);
1.511 + col->node = avl_insert_node(lp->c_tree, col->name);
1.512 + avl_set_node_link(col->node, col);
1.513 + }
1.514 + }
1.515 + return;
1.516 +}
1.517 +
1.518 +/***********************************************************************
1.519 +* NAME
1.520 +*
1.521 +* glp_set_row_bnds - set (change) row bounds
1.522 +*
1.523 +* SYNOPSIS
1.524 +*
1.525 +* void glp_set_row_bnds(glp_prob *lp, int i, int type, double lb,
1.526 +* double ub);
1.527 +*
1.528 +* DESCRIPTION
1.529 +*
1.530 +* The routine glp_set_row_bnds sets (changes) the type and bounds of
1.531 +* i-th row (auxiliary variable) of the specified problem object.
1.532 +*
1.533 +* Parameters type, lb, and ub specify the type, lower bound, and upper
1.534 +* bound, respectively, as follows:
1.535 +*
1.536 +* Type Bounds Comments
1.537 +* ------------------------------------------------------
1.538 +* GLP_FR -inf < x < +inf Free variable
1.539 +* GLP_LO lb <= x < +inf Variable with lower bound
1.540 +* GLP_UP -inf < x <= ub Variable with upper bound
1.541 +* GLP_DB lb <= x <= ub Double-bounded variable
1.542 +* GLP_FX x = lb Fixed variable
1.543 +*
1.544 +* where x is the auxiliary variable associated with i-th row.
1.545 +*
1.546 +* If the row has no lower bound, the parameter lb is ignored. If the
1.547 +* row has no upper bound, the parameter ub is ignored. If the row is
1.548 +* an equality constraint (i.e. the corresponding auxiliary variable is
1.549 +* of fixed type), only the parameter lb is used while the parameter ub
1.550 +* is ignored. */
1.551 +
1.552 +void glp_set_row_bnds(glp_prob *lp, int i, int type, double lb,
1.553 + double ub)
1.554 +{ GLPROW *row;
1.555 + if (!(1 <= i && i <= lp->m))
1.556 + xerror("glp_set_row_bnds: i = %d; row number out of range\n",
1.557 + i);
1.558 + row = lp->row[i];
1.559 + row->type = type;
1.560 + switch (type)
1.561 + { case GLP_FR:
1.562 + row->lb = row->ub = 0.0;
1.563 + if (row->stat != GLP_BS) row->stat = GLP_NF;
1.564 + break;
1.565 + case GLP_LO:
1.566 + row->lb = lb, row->ub = 0.0;
1.567 + if (row->stat != GLP_BS) row->stat = GLP_NL;
1.568 + break;
1.569 + case GLP_UP:
1.570 + row->lb = 0.0, row->ub = ub;
1.571 + if (row->stat != GLP_BS) row->stat = GLP_NU;
1.572 + break;
1.573 + case GLP_DB:
1.574 + row->lb = lb, row->ub = ub;
1.575 + if (!(row->stat == GLP_BS ||
1.576 + row->stat == GLP_NL || row->stat == GLP_NU))
1.577 + row->stat = (fabs(lb) <= fabs(ub) ? GLP_NL : GLP_NU);
1.578 + break;
1.579 + case GLP_FX:
1.580 + row->lb = row->ub = lb;
1.581 + if (row->stat != GLP_BS) row->stat = GLP_NS;
1.582 + break;
1.583 + default:
1.584 + xerror("glp_set_row_bnds: i = %d; type = %d; invalid row ty"
1.585 + "pe\n", i, type);
1.586 + }
1.587 + return;
1.588 +}
1.589 +
1.590 +/***********************************************************************
1.591 +* NAME
1.592 +*
1.593 +* glp_set_col_bnds - set (change) column bounds
1.594 +*
1.595 +* SYNOPSIS
1.596 +*
1.597 +* void glp_set_col_bnds(glp_prob *lp, int j, int type, double lb,
1.598 +* double ub);
1.599 +*
1.600 +* DESCRIPTION
1.601 +*
1.602 +* The routine glp_set_col_bnds sets (changes) the type and bounds of
1.603 +* j-th column (structural variable) of the specified problem object.
1.604 +*
1.605 +* Parameters type, lb, and ub specify the type, lower bound, and upper
1.606 +* bound, respectively, as follows:
1.607 +*
1.608 +* Type Bounds Comments
1.609 +* ------------------------------------------------------
1.610 +* GLP_FR -inf < x < +inf Free variable
1.611 +* GLP_LO lb <= x < +inf Variable with lower bound
1.612 +* GLP_UP -inf < x <= ub Variable with upper bound
1.613 +* GLP_DB lb <= x <= ub Double-bounded variable
1.614 +* GLP_FX x = lb Fixed variable
1.615 +*
1.616 +* where x is the structural variable associated with j-th column.
1.617 +*
1.618 +* If the column has no lower bound, the parameter lb is ignored. If the
1.619 +* column has no upper bound, the parameter ub is ignored. If the column
1.620 +* is of fixed type, only the parameter lb is used while the parameter
1.621 +* ub is ignored. */
1.622 +
1.623 +void glp_set_col_bnds(glp_prob *lp, int j, int type, double lb,
1.624 + double ub)
1.625 +{ GLPCOL *col;
1.626 + if (!(1 <= j && j <= lp->n))
1.627 + xerror("glp_set_col_bnds: j = %d; column number out of range\n"
1.628 + , j);
1.629 + col = lp->col[j];
1.630 + col->type = type;
1.631 + switch (type)
1.632 + { case GLP_FR:
1.633 + col->lb = col->ub = 0.0;
1.634 + if (col->stat != GLP_BS) col->stat = GLP_NF;
1.635 + break;
1.636 + case GLP_LO:
1.637 + col->lb = lb, col->ub = 0.0;
1.638 + if (col->stat != GLP_BS) col->stat = GLP_NL;
1.639 + break;
1.640 + case GLP_UP:
1.641 + col->lb = 0.0, col->ub = ub;
1.642 + if (col->stat != GLP_BS) col->stat = GLP_NU;
1.643 + break;
1.644 + case GLP_DB:
1.645 + col->lb = lb, col->ub = ub;
1.646 + if (!(col->stat == GLP_BS ||
1.647 + col->stat == GLP_NL || col->stat == GLP_NU))
1.648 + col->stat = (fabs(lb) <= fabs(ub) ? GLP_NL : GLP_NU);
1.649 + break;
1.650 + case GLP_FX:
1.651 + col->lb = col->ub = lb;
1.652 + if (col->stat != GLP_BS) col->stat = GLP_NS;
1.653 + break;
1.654 + default:
1.655 + xerror("glp_set_col_bnds: j = %d; type = %d; invalid column"
1.656 + " type\n", j, type);
1.657 + }
1.658 + return;
1.659 +}
1.660 +
1.661 +/***********************************************************************
1.662 +* NAME
1.663 +*
1.664 +* glp_set_obj_coef - set (change) obj. coefficient or constant term
1.665 +*
1.666 +* SYNOPSIS
1.667 +*
1.668 +* void glp_set_obj_coef(glp_prob *lp, int j, double coef);
1.669 +*
1.670 +* DESCRIPTION
1.671 +*
1.672 +* The routine glp_set_obj_coef sets (changes) objective coefficient at
1.673 +* j-th column (structural variable) of the specified problem object.
1.674 +*
1.675 +* If the parameter j is 0, the routine sets (changes) the constant term
1.676 +* ("shift") of the objective function. */
1.677 +
1.678 +void glp_set_obj_coef(glp_prob *lp, int j, double coef)
1.679 +{ glp_tree *tree = lp->tree;
1.680 + if (tree != NULL && tree->reason != 0)
1.681 + xerror("glp_set_obj_coef: operation not allowed\n");
1.682 + if (!(0 <= j && j <= lp->n))
1.683 + xerror("glp_set_obj_coef: j = %d; column number out of range\n"
1.684 + , j);
1.685 + if (j == 0)
1.686 + lp->c0 = coef;
1.687 + else
1.688 + lp->col[j]->coef = coef;
1.689 + return;
1.690 +}
1.691 +
1.692 +/***********************************************************************
1.693 +* NAME
1.694 +*
1.695 +* glp_set_mat_row - set (replace) row of the constraint matrix
1.696 +*
1.697 +* SYNOPSIS
1.698 +*
1.699 +* void glp_set_mat_row(glp_prob *lp, int i, int len, const int ind[],
1.700 +* const double val[]);
1.701 +*
1.702 +* DESCRIPTION
1.703 +*
1.704 +* The routine glp_set_mat_row stores (replaces) the contents of i-th
1.705 +* row of the constraint matrix of the specified problem object.
1.706 +*
1.707 +* Column indices and numeric values of new row elements must be placed
1.708 +* in locations ind[1], ..., ind[len] and val[1], ..., val[len], where
1.709 +* 0 <= len <= n is the new length of i-th row, n is the current number
1.710 +* of columns in the problem object. Elements with identical column
1.711 +* indices are not allowed. Zero elements are allowed, but they are not
1.712 +* stored in the constraint matrix.
1.713 +*
1.714 +* If the parameter len is zero, the parameters ind and/or val can be
1.715 +* specified as NULL. */
1.716 +
1.717 +void glp_set_mat_row(glp_prob *lp, int i, int len, const int ind[],
1.718 + const double val[])
1.719 +{ glp_tree *tree = lp->tree;
1.720 + GLPROW *row;
1.721 + GLPCOL *col;
1.722 + GLPAIJ *aij, *next;
1.723 + int j, k;
1.724 + /* obtain pointer to i-th row */
1.725 + if (!(1 <= i && i <= lp->m))
1.726 + xerror("glp_set_mat_row: i = %d; row number out of range\n",
1.727 + i);
1.728 + row = lp->row[i];
1.729 + if (tree != NULL && tree->reason != 0)
1.730 + { xassert(tree->curr != NULL);
1.731 + xassert(row->level == tree->curr->level);
1.732 + }
1.733 + /* remove all existing elements from i-th row */
1.734 + while (row->ptr != NULL)
1.735 + { /* take next element in the row */
1.736 + aij = row->ptr;
1.737 + /* remove the element from the row list */
1.738 + row->ptr = aij->r_next;
1.739 + /* obtain pointer to corresponding column */
1.740 + col = aij->col;
1.741 + /* remove the element from the column list */
1.742 + if (aij->c_prev == NULL)
1.743 + col->ptr = aij->c_next;
1.744 + else
1.745 + aij->c_prev->c_next = aij->c_next;
1.746 + if (aij->c_next == NULL)
1.747 + ;
1.748 + else
1.749 + aij->c_next->c_prev = aij->c_prev;
1.750 + /* return the element to the memory pool */
1.751 + dmp_free_atom(lp->pool, aij, sizeof(GLPAIJ)), lp->nnz--;
1.752 + /* if the corresponding column is basic, invalidate the basis
1.753 + factorization */
1.754 + if (col->stat == GLP_BS) lp->valid = 0;
1.755 + }
1.756 + /* store new contents of i-th row */
1.757 + if (!(0 <= len && len <= lp->n))
1.758 + xerror("glp_set_mat_row: i = %d; len = %d; invalid row length "
1.759 + "\n", i, len);
1.760 + if (len > NNZ_MAX - lp->nnz)
1.761 + xerror("glp_set_mat_row: i = %d; len = %d; too many constraint"
1.762 + " coefficients\n", i, len);
1.763 + for (k = 1; k <= len; k++)
1.764 + { /* take number j of corresponding column */
1.765 + j = ind[k];
1.766 + /* obtain pointer to j-th column */
1.767 + if (!(1 <= j && j <= lp->n))
1.768 + xerror("glp_set_mat_row: i = %d; ind[%d] = %d; column index"
1.769 + " out of range\n", i, k, j);
1.770 + col = lp->col[j];
1.771 + /* if there is element with the same column index, it can only
1.772 + be found in the beginning of j-th column list */
1.773 + if (col->ptr != NULL && col->ptr->row->i == i)
1.774 + xerror("glp_set_mat_row: i = %d; ind[%d] = %d; duplicate co"
1.775 + "lumn indices not allowed\n", i, k, j);
1.776 + /* create new element */
1.777 + aij = dmp_get_atom(lp->pool, sizeof(GLPAIJ)), lp->nnz++;
1.778 + aij->row = row;
1.779 + aij->col = col;
1.780 + aij->val = val[k];
1.781 + /* add the new element to the beginning of i-th row and j-th
1.782 + column lists */
1.783 + aij->r_prev = NULL;
1.784 + aij->r_next = row->ptr;
1.785 + aij->c_prev = NULL;
1.786 + aij->c_next = col->ptr;
1.787 + if (aij->r_next != NULL) aij->r_next->r_prev = aij;
1.788 + if (aij->c_next != NULL) aij->c_next->c_prev = aij;
1.789 + row->ptr = col->ptr = aij;
1.790 + /* if the corresponding column is basic, invalidate the basis
1.791 + factorization */
1.792 + if (col->stat == GLP_BS && aij->val != 0.0) lp->valid = 0;
1.793 + }
1.794 + /* remove zero elements from i-th row */
1.795 + for (aij = row->ptr; aij != NULL; aij = next)
1.796 + { next = aij->r_next;
1.797 + if (aij->val == 0.0)
1.798 + { /* remove the element from the row list */
1.799 + if (aij->r_prev == NULL)
1.800 + row->ptr = next;
1.801 + else
1.802 + aij->r_prev->r_next = next;
1.803 + if (next == NULL)
1.804 + ;
1.805 + else
1.806 + next->r_prev = aij->r_prev;
1.807 + /* remove the element from the column list */
1.808 + xassert(aij->c_prev == NULL);
1.809 + aij->col->ptr = aij->c_next;
1.810 + if (aij->c_next != NULL) aij->c_next->c_prev = NULL;
1.811 + /* return the element to the memory pool */
1.812 + dmp_free_atom(lp->pool, aij, sizeof(GLPAIJ)), lp->nnz--;
1.813 + }
1.814 + }
1.815 + return;
1.816 +}
1.817 +
1.818 +/***********************************************************************
1.819 +* NAME
1.820 +*
1.821 +* glp_set_mat_col - set (replace) column of the constraint matrix
1.822 +*
1.823 +* SYNOPSIS
1.824 +*
1.825 +* void glp_set_mat_col(glp_prob *lp, int j, int len, const int ind[],
1.826 +* const double val[]);
1.827 +*
1.828 +* DESCRIPTION
1.829 +*
1.830 +* The routine glp_set_mat_col stores (replaces) the contents of j-th
1.831 +* column of the constraint matrix of the specified problem object.
1.832 +*
1.833 +* Row indices and numeric values of new column elements must be placed
1.834 +* in locations ind[1], ..., ind[len] and val[1], ..., val[len], where
1.835 +* 0 <= len <= m is the new length of j-th column, m is the current
1.836 +* number of rows in the problem object. Elements with identical column
1.837 +* indices are not allowed. Zero elements are allowed, but they are not
1.838 +* stored in the constraint matrix.
1.839 +*
1.840 +* If the parameter len is zero, the parameters ind and/or val can be
1.841 +* specified as NULL. */
1.842 +
1.843 +void glp_set_mat_col(glp_prob *lp, int j, int len, const int ind[],
1.844 + const double val[])
1.845 +{ glp_tree *tree = lp->tree;
1.846 + GLPROW *row;
1.847 + GLPCOL *col;
1.848 + GLPAIJ *aij, *next;
1.849 + int i, k;
1.850 + if (tree != NULL && tree->reason != 0)
1.851 + xerror("glp_set_mat_col: operation not allowed\n");
1.852 + /* obtain pointer to j-th column */
1.853 + if (!(1 <= j && j <= lp->n))
1.854 + xerror("glp_set_mat_col: j = %d; column number out of range\n",
1.855 + j);
1.856 + col = lp->col[j];
1.857 + /* remove all existing elements from j-th column */
1.858 + while (col->ptr != NULL)
1.859 + { /* take next element in the column */
1.860 + aij = col->ptr;
1.861 + /* remove the element from the column list */
1.862 + col->ptr = aij->c_next;
1.863 + /* obtain pointer to corresponding row */
1.864 + row = aij->row;
1.865 + /* remove the element from the row list */
1.866 + if (aij->r_prev == NULL)
1.867 + row->ptr = aij->r_next;
1.868 + else
1.869 + aij->r_prev->r_next = aij->r_next;
1.870 + if (aij->r_next == NULL)
1.871 + ;
1.872 + else
1.873 + aij->r_next->r_prev = aij->r_prev;
1.874 + /* return the element to the memory pool */
1.875 + dmp_free_atom(lp->pool, aij, sizeof(GLPAIJ)), lp->nnz--;
1.876 + }
1.877 + /* store new contents of j-th column */
1.878 + if (!(0 <= len && len <= lp->m))
1.879 + xerror("glp_set_mat_col: j = %d; len = %d; invalid column leng"
1.880 + "th\n", j, len);
1.881 + if (len > NNZ_MAX - lp->nnz)
1.882 + xerror("glp_set_mat_col: j = %d; len = %d; too many constraint"
1.883 + " coefficients\n", j, len);
1.884 + for (k = 1; k <= len; k++)
1.885 + { /* take number i of corresponding row */
1.886 + i = ind[k];
1.887 + /* obtain pointer to i-th row */
1.888 + if (!(1 <= i && i <= lp->m))
1.889 + xerror("glp_set_mat_col: j = %d; ind[%d] = %d; row index ou"
1.890 + "t of range\n", j, k, i);
1.891 + row = lp->row[i];
1.892 + /* if there is element with the same row index, it can only be
1.893 + found in the beginning of i-th row list */
1.894 + if (row->ptr != NULL && row->ptr->col->j == j)
1.895 + xerror("glp_set_mat_col: j = %d; ind[%d] = %d; duplicate ro"
1.896 + "w indices not allowed\n", j, k, i);
1.897 + /* create new element */
1.898 + aij = dmp_get_atom(lp->pool, sizeof(GLPAIJ)), lp->nnz++;
1.899 + aij->row = row;
1.900 + aij->col = col;
1.901 + aij->val = val[k];
1.902 + /* add the new element to the beginning of i-th row and j-th
1.903 + column lists */
1.904 + aij->r_prev = NULL;
1.905 + aij->r_next = row->ptr;
1.906 + aij->c_prev = NULL;
1.907 + aij->c_next = col->ptr;
1.908 + if (aij->r_next != NULL) aij->r_next->r_prev = aij;
1.909 + if (aij->c_next != NULL) aij->c_next->c_prev = aij;
1.910 + row->ptr = col->ptr = aij;
1.911 + }
1.912 + /* remove zero elements from j-th column */
1.913 + for (aij = col->ptr; aij != NULL; aij = next)
1.914 + { next = aij->c_next;
1.915 + if (aij->val == 0.0)
1.916 + { /* remove the element from the row list */
1.917 + xassert(aij->r_prev == NULL);
1.918 + aij->row->ptr = aij->r_next;
1.919 + if (aij->r_next != NULL) aij->r_next->r_prev = NULL;
1.920 + /* remove the element from the column list */
1.921 + if (aij->c_prev == NULL)
1.922 + col->ptr = next;
1.923 + else
1.924 + aij->c_prev->c_next = next;
1.925 + if (next == NULL)
1.926 + ;
1.927 + else
1.928 + next->c_prev = aij->c_prev;
1.929 + /* return the element to the memory pool */
1.930 + dmp_free_atom(lp->pool, aij, sizeof(GLPAIJ)), lp->nnz--;
1.931 + }
1.932 + }
1.933 + /* if j-th column is basic, invalidate the basis factorization */
1.934 + if (col->stat == GLP_BS) lp->valid = 0;
1.935 + return;
1.936 +}
1.937 +
1.938 +/***********************************************************************
1.939 +* NAME
1.940 +*
1.941 +* glp_load_matrix - load (replace) the whole constraint matrix
1.942 +*
1.943 +* SYNOPSIS
1.944 +*
1.945 +* void glp_load_matrix(glp_prob *lp, int ne, const int ia[],
1.946 +* const int ja[], const double ar[]);
1.947 +*
1.948 +* DESCRIPTION
1.949 +*
1.950 +* The routine glp_load_matrix loads the constraint matrix passed in
1.951 +* the arrays ia, ja, and ar into the specified problem object. Before
1.952 +* loading the current contents of the constraint matrix is destroyed.
1.953 +*
1.954 +* Constraint coefficients (elements of the constraint matrix) must be
1.955 +* specified as triplets (ia[k], ja[k], ar[k]) for k = 1, ..., ne,
1.956 +* where ia[k] is the row index, ja[k] is the column index, ar[k] is a
1.957 +* numeric value of corresponding constraint coefficient. The parameter
1.958 +* ne specifies the total number of (non-zero) elements in the matrix
1.959 +* to be loaded. Coefficients with identical indices are not allowed.
1.960 +* Zero coefficients are allowed, however, they are not stored in the
1.961 +* constraint matrix.
1.962 +*
1.963 +* If the parameter ne is zero, the parameters ia, ja, and ar can be
1.964 +* specified as NULL. */
1.965 +
1.966 +void glp_load_matrix(glp_prob *lp, int ne, const int ia[],
1.967 + const int ja[], const double ar[])
1.968 +{ glp_tree *tree = lp->tree;
1.969 + GLPROW *row;
1.970 + GLPCOL *col;
1.971 + GLPAIJ *aij, *next;
1.972 + int i, j, k;
1.973 + if (tree != NULL && tree->reason != 0)
1.974 + xerror("glp_load_matrix: operation not allowed\n");
1.975 + /* clear the constraint matrix */
1.976 + for (i = 1; i <= lp->m; i++)
1.977 + { row = lp->row[i];
1.978 + while (row->ptr != NULL)
1.979 + { aij = row->ptr;
1.980 + row->ptr = aij->r_next;
1.981 + dmp_free_atom(lp->pool, aij, sizeof(GLPAIJ)), lp->nnz--;
1.982 + }
1.983 + }
1.984 + xassert(lp->nnz == 0);
1.985 + for (j = 1; j <= lp->n; j++) lp->col[j]->ptr = NULL;
1.986 + /* load the new contents of the constraint matrix and build its
1.987 + row lists */
1.988 + if (ne < 0)
1.989 + xerror("glp_load_matrix: ne = %d; invalid number of constraint"
1.990 + " coefficients\n", ne);
1.991 + if (ne > NNZ_MAX)
1.992 + xerror("glp_load_matrix: ne = %d; too many constraint coeffici"
1.993 + "ents\n", ne);
1.994 + for (k = 1; k <= ne; k++)
1.995 + { /* take indices of new element */
1.996 + i = ia[k], j = ja[k];
1.997 + /* obtain pointer to i-th row */
1.998 + if (!(1 <= i && i <= lp->m))
1.999 + xerror("glp_load_matrix: ia[%d] = %d; row index out of rang"
1.1000 + "e\n", k, i);
1.1001 + row = lp->row[i];
1.1002 + /* obtain pointer to j-th column */
1.1003 + if (!(1 <= j && j <= lp->n))
1.1004 + xerror("glp_load_matrix: ja[%d] = %d; column index out of r"
1.1005 + "ange\n", k, j);
1.1006 + col = lp->col[j];
1.1007 + /* create new element */
1.1008 + aij = dmp_get_atom(lp->pool, sizeof(GLPAIJ)), lp->nnz++;
1.1009 + aij->row = row;
1.1010 + aij->col = col;
1.1011 + aij->val = ar[k];
1.1012 + /* add the new element to the beginning of i-th row list */
1.1013 + aij->r_prev = NULL;
1.1014 + aij->r_next = row->ptr;
1.1015 + if (aij->r_next != NULL) aij->r_next->r_prev = aij;
1.1016 + row->ptr = aij;
1.1017 + }
1.1018 + xassert(lp->nnz == ne);
1.1019 + /* build column lists of the constraint matrix and check elements
1.1020 + with identical indices */
1.1021 + for (i = 1; i <= lp->m; i++)
1.1022 + { for (aij = lp->row[i]->ptr; aij != NULL; aij = aij->r_next)
1.1023 + { /* obtain pointer to corresponding column */
1.1024 + col = aij->col;
1.1025 + /* if there is element with identical indices, it can only
1.1026 + be found in the beginning of j-th column list */
1.1027 + if (col->ptr != NULL && col->ptr->row->i == i)
1.1028 + { for (k = 1; k <= ne; k++)
1.1029 + if (ia[k] == i && ja[k] == col->j) break;
1.1030 + xerror("glp_load_mat: ia[%d] = %d; ja[%d] = %d; duplicat"
1.1031 + "e indices not allowed\n", k, i, k, col->j);
1.1032 + }
1.1033 + /* add the element to the beginning of j-th column list */
1.1034 + aij->c_prev = NULL;
1.1035 + aij->c_next = col->ptr;
1.1036 + if (aij->c_next != NULL) aij->c_next->c_prev = aij;
1.1037 + col->ptr = aij;
1.1038 + }
1.1039 + }
1.1040 + /* remove zero elements from the constraint matrix */
1.1041 + for (i = 1; i <= lp->m; i++)
1.1042 + { row = lp->row[i];
1.1043 + for (aij = row->ptr; aij != NULL; aij = next)
1.1044 + { next = aij->r_next;
1.1045 + if (aij->val == 0.0)
1.1046 + { /* remove the element from the row list */
1.1047 + if (aij->r_prev == NULL)
1.1048 + row->ptr = next;
1.1049 + else
1.1050 + aij->r_prev->r_next = next;
1.1051 + if (next == NULL)
1.1052 + ;
1.1053 + else
1.1054 + next->r_prev = aij->r_prev;
1.1055 + /* remove the element from the column list */
1.1056 + if (aij->c_prev == NULL)
1.1057 + aij->col->ptr = aij->c_next;
1.1058 + else
1.1059 + aij->c_prev->c_next = aij->c_next;
1.1060 + if (aij->c_next == NULL)
1.1061 + ;
1.1062 + else
1.1063 + aij->c_next->c_prev = aij->c_prev;
1.1064 + /* return the element to the memory pool */
1.1065 + dmp_free_atom(lp->pool, aij, sizeof(GLPAIJ)), lp->nnz--;
1.1066 + }
1.1067 + }
1.1068 + }
1.1069 + /* invalidate the basis factorization */
1.1070 + lp->valid = 0;
1.1071 + return;
1.1072 +}
1.1073 +
1.1074 +/***********************************************************************
1.1075 +* NAME
1.1076 +*
1.1077 +* glp_check_dup - check for duplicate elements in sparse matrix
1.1078 +*
1.1079 +* SYNOPSIS
1.1080 +*
1.1081 +* int glp_check_dup(int m, int n, int ne, const int ia[],
1.1082 +* const int ja[]);
1.1083 +*
1.1084 +* DESCRIPTION
1.1085 +*
1.1086 +* The routine glp_check_dup checks for duplicate elements (that is,
1.1087 +* elements with identical indices) in a sparse matrix specified in the
1.1088 +* coordinate format.
1.1089 +*
1.1090 +* The parameters m and n specifies, respectively, the number of rows
1.1091 +* and columns in the matrix, m >= 0, n >= 0.
1.1092 +*
1.1093 +* The parameter ne specifies the number of (structurally) non-zero
1.1094 +* elements in the matrix, ne >= 0.
1.1095 +*
1.1096 +* Elements of the matrix are specified as doublets (ia[k],ja[k]) for
1.1097 +* k = 1,...,ne, where ia[k] is a row index, ja[k] is a column index.
1.1098 +*
1.1099 +* The routine glp_check_dup can be used prior to a call to the routine
1.1100 +* glp_load_matrix to check that the constraint matrix to be loaded has
1.1101 +* no duplicate elements.
1.1102 +*
1.1103 +* RETURNS
1.1104 +*
1.1105 +* The routine glp_check_dup returns one of the following values:
1.1106 +*
1.1107 +* 0 - the matrix has no duplicate elements;
1.1108 +*
1.1109 +* -k - indices ia[k] or/and ja[k] are out of range;
1.1110 +*
1.1111 +* +k - element (ia[k],ja[k]) is duplicate. */
1.1112 +
1.1113 +int glp_check_dup(int m, int n, int ne, const int ia[], const int ja[])
1.1114 +{ int i, j, k, *ptr, *next, ret;
1.1115 + char *flag;
1.1116 + if (m < 0)
1.1117 + xerror("glp_check_dup: m = %d; invalid parameter\n");
1.1118 + if (n < 0)
1.1119 + xerror("glp_check_dup: n = %d; invalid parameter\n");
1.1120 + if (ne < 0)
1.1121 + xerror("glp_check_dup: ne = %d; invalid parameter\n");
1.1122 + if (ne > 0 && ia == NULL)
1.1123 + xerror("glp_check_dup: ia = %p; invalid parameter\n", ia);
1.1124 + if (ne > 0 && ja == NULL)
1.1125 + xerror("glp_check_dup: ja = %p; invalid parameter\n", ja);
1.1126 + for (k = 1; k <= ne; k++)
1.1127 + { i = ia[k], j = ja[k];
1.1128 + if (!(1 <= i && i <= m && 1 <= j && j <= n))
1.1129 + { ret = -k;
1.1130 + goto done;
1.1131 + }
1.1132 + }
1.1133 + if (m == 0 || n == 0)
1.1134 + { ret = 0;
1.1135 + goto done;
1.1136 + }
1.1137 + /* allocate working arrays */
1.1138 + ptr = xcalloc(1+m, sizeof(int));
1.1139 + next = xcalloc(1+ne, sizeof(int));
1.1140 + flag = xcalloc(1+n, sizeof(char));
1.1141 + /* build row lists */
1.1142 + for (i = 1; i <= m; i++)
1.1143 + ptr[i] = 0;
1.1144 + for (k = 1; k <= ne; k++)
1.1145 + { i = ia[k];
1.1146 + next[k] = ptr[i];
1.1147 + ptr[i] = k;
1.1148 + }
1.1149 + /* clear column flags */
1.1150 + for (j = 1; j <= n; j++)
1.1151 + flag[j] = 0;
1.1152 + /* check for duplicate elements */
1.1153 + for (i = 1; i <= m; i++)
1.1154 + { for (k = ptr[i]; k != 0; k = next[k])
1.1155 + { j = ja[k];
1.1156 + if (flag[j])
1.1157 + { /* find first element (i,j) */
1.1158 + for (k = 1; k <= ne; k++)
1.1159 + if (ia[k] == i && ja[k] == j) break;
1.1160 + xassert(k <= ne);
1.1161 + /* find next (duplicate) element (i,j) */
1.1162 + for (k++; k <= ne; k++)
1.1163 + if (ia[k] == i && ja[k] == j) break;
1.1164 + xassert(k <= ne);
1.1165 + ret = +k;
1.1166 + goto skip;
1.1167 + }
1.1168 + flag[j] = 1;
1.1169 + }
1.1170 + /* clear column flags */
1.1171 + for (k = ptr[i]; k != 0; k = next[k])
1.1172 + flag[ja[k]] = 0;
1.1173 + }
1.1174 + /* no duplicate element found */
1.1175 + ret = 0;
1.1176 +skip: /* free working arrays */
1.1177 + xfree(ptr);
1.1178 + xfree(next);
1.1179 + xfree(flag);
1.1180 +done: return ret;
1.1181 +}
1.1182 +
1.1183 +/***********************************************************************
1.1184 +* NAME
1.1185 +*
1.1186 +* glp_sort_matrix - sort elements of the constraint matrix
1.1187 +*
1.1188 +* SYNOPSIS
1.1189 +*
1.1190 +* void glp_sort_matrix(glp_prob *P);
1.1191 +*
1.1192 +* DESCRIPTION
1.1193 +*
1.1194 +* The routine glp_sort_matrix sorts elements of the constraint matrix
1.1195 +* rebuilding its row and column linked lists. On exit from the routine
1.1196 +* the constraint matrix is not changed, however, elements in the row
1.1197 +* linked lists become ordered by ascending column indices, and the
1.1198 +* elements in the column linked lists become ordered by ascending row
1.1199 +* indices. */
1.1200 +
1.1201 +void glp_sort_matrix(glp_prob *P)
1.1202 +{ GLPAIJ *aij;
1.1203 + int i, j;
1.1204 + if (P == NULL || P->magic != GLP_PROB_MAGIC)
1.1205 + xerror("glp_sort_matrix: P = %p; invalid problem object\n",
1.1206 + P);
1.1207 + /* rebuild row linked lists */
1.1208 + for (i = P->m; i >= 1; i--)
1.1209 + P->row[i]->ptr = NULL;
1.1210 + for (j = P->n; j >= 1; j--)
1.1211 + { for (aij = P->col[j]->ptr; aij != NULL; aij = aij->c_next)
1.1212 + { i = aij->row->i;
1.1213 + aij->r_prev = NULL;
1.1214 + aij->r_next = P->row[i]->ptr;
1.1215 + if (aij->r_next != NULL) aij->r_next->r_prev = aij;
1.1216 + P->row[i]->ptr = aij;
1.1217 + }
1.1218 + }
1.1219 + /* rebuild column linked lists */
1.1220 + for (j = P->n; j >= 1; j--)
1.1221 + P->col[j]->ptr = NULL;
1.1222 + for (i = P->m; i >= 1; i--)
1.1223 + { for (aij = P->row[i]->ptr; aij != NULL; aij = aij->r_next)
1.1224 + { j = aij->col->j;
1.1225 + aij->c_prev = NULL;
1.1226 + aij->c_next = P->col[j]->ptr;
1.1227 + if (aij->c_next != NULL) aij->c_next->c_prev = aij;
1.1228 + P->col[j]->ptr = aij;
1.1229 + }
1.1230 + }
1.1231 + return;
1.1232 +}
1.1233 +
1.1234 +/***********************************************************************
1.1235 +* NAME
1.1236 +*
1.1237 +* glp_del_rows - delete rows from problem object
1.1238 +*
1.1239 +* SYNOPSIS
1.1240 +*
1.1241 +* void glp_del_rows(glp_prob *lp, int nrs, const int num[]);
1.1242 +*
1.1243 +* DESCRIPTION
1.1244 +*
1.1245 +* The routine glp_del_rows deletes rows from the specified problem
1.1246 +* object. Ordinal numbers of rows to be deleted should be placed in
1.1247 +* locations num[1], ..., num[nrs], where nrs > 0.
1.1248 +*
1.1249 +* Note that deleting rows involves changing ordinal numbers of other
1.1250 +* rows remaining in the problem object. New ordinal numbers of the
1.1251 +* remaining rows are assigned under the assumption that the original
1.1252 +* order of rows is not changed. */
1.1253 +
1.1254 +void glp_del_rows(glp_prob *lp, int nrs, const int num[])
1.1255 +{ glp_tree *tree = lp->tree;
1.1256 + GLPROW *row;
1.1257 + int i, k, m_new;
1.1258 + /* mark rows to be deleted */
1.1259 + if (!(1 <= nrs && nrs <= lp->m))
1.1260 + xerror("glp_del_rows: nrs = %d; invalid number of rows\n",
1.1261 + nrs);
1.1262 + for (k = 1; k <= nrs; k++)
1.1263 + { /* take the number of row to be deleted */
1.1264 + i = num[k];
1.1265 + /* obtain pointer to i-th row */
1.1266 + if (!(1 <= i && i <= lp->m))
1.1267 + xerror("glp_del_rows: num[%d] = %d; row number out of range"
1.1268 + "\n", k, i);
1.1269 + row = lp->row[i];
1.1270 + if (tree != NULL && tree->reason != 0)
1.1271 + { if (!(tree->reason == GLP_IROWGEN ||
1.1272 + tree->reason == GLP_ICUTGEN))
1.1273 + xerror("glp_del_rows: operation not allowed\n");
1.1274 + xassert(tree->curr != NULL);
1.1275 + if (row->level != tree->curr->level)
1.1276 + xerror("glp_del_rows: num[%d] = %d; invalid attempt to d"
1.1277 + "elete row created not in current subproblem\n", k,i);
1.1278 + if (row->stat != GLP_BS)
1.1279 + xerror("glp_del_rows: num[%d] = %d; invalid attempt to d"
1.1280 + "elete active row (constraint)\n", k, i);
1.1281 + tree->reinv = 1;
1.1282 + }
1.1283 + /* check that the row is not marked yet */
1.1284 + if (row->i == 0)
1.1285 + xerror("glp_del_rows: num[%d] = %d; duplicate row numbers n"
1.1286 + "ot allowed\n", k, i);
1.1287 + /* erase symbolic name assigned to the row */
1.1288 + glp_set_row_name(lp, i, NULL);
1.1289 + xassert(row->node == NULL);
1.1290 + /* erase corresponding row of the constraint matrix */
1.1291 + glp_set_mat_row(lp, i, 0, NULL, NULL);
1.1292 + xassert(row->ptr == NULL);
1.1293 + /* mark the row to be deleted */
1.1294 + row->i = 0;
1.1295 + }
1.1296 + /* delete all marked rows from the row list */
1.1297 + m_new = 0;
1.1298 + for (i = 1; i <= lp->m; i++)
1.1299 + { /* obtain pointer to i-th row */
1.1300 + row = lp->row[i];
1.1301 + /* check if the row is marked */
1.1302 + if (row->i == 0)
1.1303 + { /* it is marked, delete it */
1.1304 + dmp_free_atom(lp->pool, row, sizeof(GLPROW));
1.1305 + }
1.1306 + else
1.1307 + { /* it is not marked; keep it */
1.1308 + row->i = ++m_new;
1.1309 + lp->row[row->i] = row;
1.1310 + }
1.1311 + }
1.1312 + /* set new number of rows */
1.1313 + lp->m = m_new;
1.1314 + /* invalidate the basis factorization */
1.1315 + lp->valid = 0;
1.1316 + return;
1.1317 +}
1.1318 +
1.1319 +/***********************************************************************
1.1320 +* NAME
1.1321 +*
1.1322 +* glp_del_cols - delete columns from problem object
1.1323 +*
1.1324 +* SYNOPSIS
1.1325 +*
1.1326 +* void glp_del_cols(glp_prob *lp, int ncs, const int num[]);
1.1327 +*
1.1328 +* DESCRIPTION
1.1329 +*
1.1330 +* The routine glp_del_cols deletes columns from the specified problem
1.1331 +* object. Ordinal numbers of columns to be deleted should be placed in
1.1332 +* locations num[1], ..., num[ncs], where ncs > 0.
1.1333 +*
1.1334 +* Note that deleting columns involves changing ordinal numbers of
1.1335 +* other columns remaining in the problem object. New ordinal numbers
1.1336 +* of the remaining columns are assigned under the assumption that the
1.1337 +* original order of columns is not changed. */
1.1338 +
1.1339 +void glp_del_cols(glp_prob *lp, int ncs, const int num[])
1.1340 +{ glp_tree *tree = lp->tree;
1.1341 + GLPCOL *col;
1.1342 + int j, k, n_new;
1.1343 + if (tree != NULL && tree->reason != 0)
1.1344 + xerror("glp_del_cols: operation not allowed\n");
1.1345 + /* mark columns to be deleted */
1.1346 + if (!(1 <= ncs && ncs <= lp->n))
1.1347 + xerror("glp_del_cols: ncs = %d; invalid number of columns\n",
1.1348 + ncs);
1.1349 + for (k = 1; k <= ncs; k++)
1.1350 + { /* take the number of column to be deleted */
1.1351 + j = num[k];
1.1352 + /* obtain pointer to j-th column */
1.1353 + if (!(1 <= j && j <= lp->n))
1.1354 + xerror("glp_del_cols: num[%d] = %d; column number out of ra"
1.1355 + "nge", k, j);
1.1356 + col = lp->col[j];
1.1357 + /* check that the column is not marked yet */
1.1358 + if (col->j == 0)
1.1359 + xerror("glp_del_cols: num[%d] = %d; duplicate column number"
1.1360 + "s not allowed\n", k, j);
1.1361 + /* erase symbolic name assigned to the column */
1.1362 + glp_set_col_name(lp, j, NULL);
1.1363 + xassert(col->node == NULL);
1.1364 + /* erase corresponding column of the constraint matrix */
1.1365 + glp_set_mat_col(lp, j, 0, NULL, NULL);
1.1366 + xassert(col->ptr == NULL);
1.1367 + /* mark the column to be deleted */
1.1368 + col->j = 0;
1.1369 + /* if it is basic, invalidate the basis factorization */
1.1370 + if (col->stat == GLP_BS) lp->valid = 0;
1.1371 + }
1.1372 + /* delete all marked columns from the column list */
1.1373 + n_new = 0;
1.1374 + for (j = 1; j <= lp->n; j++)
1.1375 + { /* obtain pointer to j-th column */
1.1376 + col = lp->col[j];
1.1377 + /* check if the column is marked */
1.1378 + if (col->j == 0)
1.1379 + { /* it is marked; delete it */
1.1380 + dmp_free_atom(lp->pool, col, sizeof(GLPCOL));
1.1381 + }
1.1382 + else
1.1383 + { /* it is not marked; keep it */
1.1384 + col->j = ++n_new;
1.1385 + lp->col[col->j] = col;
1.1386 + }
1.1387 + }
1.1388 + /* set new number of columns */
1.1389 + lp->n = n_new;
1.1390 + /* if the basis header is still valid, adjust it */
1.1391 + if (lp->valid)
1.1392 + { int m = lp->m;
1.1393 + int *head = lp->head;
1.1394 + for (j = 1; j <= n_new; j++)
1.1395 + { k = lp->col[j]->bind;
1.1396 + if (k != 0)
1.1397 + { xassert(1 <= k && k <= m);
1.1398 + head[k] = m + j;
1.1399 + }
1.1400 + }
1.1401 + }
1.1402 + return;
1.1403 +}
1.1404 +
1.1405 +/***********************************************************************
1.1406 +* NAME
1.1407 +*
1.1408 +* glp_copy_prob - copy problem object content
1.1409 +*
1.1410 +* SYNOPSIS
1.1411 +*
1.1412 +* void glp_copy_prob(glp_prob *dest, glp_prob *prob, int names);
1.1413 +*
1.1414 +* DESCRIPTION
1.1415 +*
1.1416 +* The routine glp_copy_prob copies the content of the problem object
1.1417 +* prob to the problem object dest.
1.1418 +*
1.1419 +* The parameter names is a flag. If it is non-zero, the routine also
1.1420 +* copies all symbolic names; otherwise, if it is zero, symbolic names
1.1421 +* are not copied. */
1.1422 +
1.1423 +void glp_copy_prob(glp_prob *dest, glp_prob *prob, int names)
1.1424 +{ glp_tree *tree = dest->tree;
1.1425 + glp_bfcp bfcp;
1.1426 + int i, j, len, *ind;
1.1427 + double *val;
1.1428 + if (tree != NULL && tree->reason != 0)
1.1429 + xerror("glp_copy_prob: operation not allowed\n");
1.1430 + if (dest == prob)
1.1431 + xerror("glp_copy_prob: copying problem object to itself not al"
1.1432 + "lowed\n");
1.1433 + if (!(names == GLP_ON || names == GLP_OFF))
1.1434 + xerror("glp_copy_prob: names = %d; invalid parameter\n",
1.1435 + names);
1.1436 + glp_erase_prob(dest);
1.1437 + if (names && prob->name != NULL)
1.1438 + glp_set_prob_name(dest, prob->name);
1.1439 + if (names && prob->obj != NULL)
1.1440 + glp_set_obj_name(dest, prob->obj);
1.1441 + dest->dir = prob->dir;
1.1442 + dest->c0 = prob->c0;
1.1443 + if (prob->m > 0)
1.1444 + glp_add_rows(dest, prob->m);
1.1445 + if (prob->n > 0)
1.1446 + glp_add_cols(dest, prob->n);
1.1447 + glp_get_bfcp(prob, &bfcp);
1.1448 + glp_set_bfcp(dest, &bfcp);
1.1449 + dest->pbs_stat = prob->pbs_stat;
1.1450 + dest->dbs_stat = prob->dbs_stat;
1.1451 + dest->obj_val = prob->obj_val;
1.1452 + dest->some = prob->some;
1.1453 + dest->ipt_stat = prob->ipt_stat;
1.1454 + dest->ipt_obj = prob->ipt_obj;
1.1455 + dest->mip_stat = prob->mip_stat;
1.1456 + dest->mip_obj = prob->mip_obj;
1.1457 + for (i = 1; i <= prob->m; i++)
1.1458 + { GLPROW *to = dest->row[i];
1.1459 + GLPROW *from = prob->row[i];
1.1460 + if (names && from->name != NULL)
1.1461 + glp_set_row_name(dest, i, from->name);
1.1462 + to->type = from->type;
1.1463 + to->lb = from->lb;
1.1464 + to->ub = from->ub;
1.1465 + to->rii = from->rii;
1.1466 + to->stat = from->stat;
1.1467 + to->prim = from->prim;
1.1468 + to->dual = from->dual;
1.1469 + to->pval = from->pval;
1.1470 + to->dval = from->dval;
1.1471 + to->mipx = from->mipx;
1.1472 + }
1.1473 + ind = xcalloc(1+prob->m, sizeof(int));
1.1474 + val = xcalloc(1+prob->m, sizeof(double));
1.1475 + for (j = 1; j <= prob->n; j++)
1.1476 + { GLPCOL *to = dest->col[j];
1.1477 + GLPCOL *from = prob->col[j];
1.1478 + if (names && from->name != NULL)
1.1479 + glp_set_col_name(dest, j, from->name);
1.1480 + to->kind = from->kind;
1.1481 + to->type = from->type;
1.1482 + to->lb = from->lb;
1.1483 + to->ub = from->ub;
1.1484 + to->coef = from->coef;
1.1485 + len = glp_get_mat_col(prob, j, ind, val);
1.1486 + glp_set_mat_col(dest, j, len, ind, val);
1.1487 + to->sjj = from->sjj;
1.1488 + to->stat = from->stat;
1.1489 + to->prim = from->prim;
1.1490 + to->dual = from->dual;
1.1491 + to->pval = from->pval;
1.1492 + to->dval = from->dval;
1.1493 + to->mipx = from->mipx;
1.1494 + }
1.1495 + xfree(ind);
1.1496 + xfree(val);
1.1497 + return;
1.1498 +}
1.1499 +
1.1500 +/***********************************************************************
1.1501 +* NAME
1.1502 +*
1.1503 +* glp_erase_prob - erase problem object content
1.1504 +*
1.1505 +* SYNOPSIS
1.1506 +*
1.1507 +* void glp_erase_prob(glp_prob *lp);
1.1508 +*
1.1509 +* DESCRIPTION
1.1510 +*
1.1511 +* The routine glp_erase_prob erases the content of the specified
1.1512 +* problem object. The effect of this operation is the same as if the
1.1513 +* problem object would be deleted with the routine glp_delete_prob and
1.1514 +* then created anew with the routine glp_create_prob, with exception
1.1515 +* that the handle (pointer) to the problem object remains valid. */
1.1516 +
1.1517 +static void delete_prob(glp_prob *lp);
1.1518 +
1.1519 +void glp_erase_prob(glp_prob *lp)
1.1520 +{ glp_tree *tree = lp->tree;
1.1521 + if (tree != NULL && tree->reason != 0)
1.1522 + xerror("glp_erase_prob: operation not allowed\n");
1.1523 + delete_prob(lp);
1.1524 + create_prob(lp);
1.1525 + return;
1.1526 +}
1.1527 +
1.1528 +/***********************************************************************
1.1529 +* NAME
1.1530 +*
1.1531 +* glp_delete_prob - delete problem object
1.1532 +*
1.1533 +* SYNOPSIS
1.1534 +*
1.1535 +* void glp_delete_prob(glp_prob *lp);
1.1536 +*
1.1537 +* DESCRIPTION
1.1538 +*
1.1539 +* The routine glp_delete_prob deletes the specified problem object and
1.1540 +* frees all the memory allocated to it. */
1.1541 +
1.1542 +static void delete_prob(glp_prob *lp)
1.1543 +{ lp->magic = 0x3F3F3F3F;
1.1544 + dmp_delete_pool(lp->pool);
1.1545 +#if 0 /* 17/XI-2009 */
1.1546 + xfree(lp->cps);
1.1547 +#else
1.1548 + if (lp->parms != NULL) xfree(lp->parms);
1.1549 +#endif
1.1550 + xassert(lp->tree == NULL);
1.1551 +#if 0
1.1552 + if (lp->cwa != NULL) xfree(lp->cwa);
1.1553 +#endif
1.1554 + xfree(lp->row);
1.1555 + xfree(lp->col);
1.1556 + if (lp->r_tree != NULL) avl_delete_tree(lp->r_tree);
1.1557 + if (lp->c_tree != NULL) avl_delete_tree(lp->c_tree);
1.1558 + xfree(lp->head);
1.1559 + if (lp->bfcp != NULL) xfree(lp->bfcp);
1.1560 + if (lp->bfd != NULL) bfd_delete_it(lp->bfd);
1.1561 + return;
1.1562 +}
1.1563 +
1.1564 +void glp_delete_prob(glp_prob *lp)
1.1565 +{ glp_tree *tree = lp->tree;
1.1566 + if (tree != NULL && tree->reason != 0)
1.1567 + xerror("glp_delete_prob: operation not allowed\n");
1.1568 + delete_prob(lp);
1.1569 + xfree(lp);
1.1570 + return;
1.1571 +}
1.1572 +
1.1573 +/* eof */