lemon-project-template-glpk
diff deps/glpk/src/glpapi01.c @ 9:33de93886c88
Import GLPK 4.47
author | Alpar Juttner <alpar@cs.elte.hu> |
---|---|
date | Sun, 06 Nov 2011 20:59:10 +0100 |
parents | |
children |
line diff
1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000 1.2 +++ b/deps/glpk/src/glpapi01.c Sun Nov 06 20:59:10 2011 +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, 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 "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 */