lemon-project-template-glpk
view 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 source
1 /* glpapi01.c (problem creating and modifying routines) */
3 /***********************************************************************
4 * This code is part of GLPK (GNU Linear Programming Kit).
5 *
6 * Copyright (C) 2000, 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008,
7 * 2009, 2010, 2011 Andrew Makhorin, Department for Applied Informatics,
8 * Moscow Aviation Institute, Moscow, Russia. All rights reserved.
9 * E-mail: <mao@gnu.org>.
10 *
11 * GLPK is free software: you can redistribute it and/or modify it
12 * under the terms of the GNU General Public License as published by
13 * the Free Software Foundation, either version 3 of the License, or
14 * (at your option) any later version.
15 *
16 * GLPK is distributed in the hope that it will be useful, but WITHOUT
17 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
18 * or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public
19 * License for more details.
20 *
21 * You should have received a copy of the GNU General Public License
22 * along with GLPK. If not, see <http://www.gnu.org/licenses/>.
23 ***********************************************************************/
25 #include "glpios.h"
27 /* CAUTION: DO NOT CHANGE THE LIMITS BELOW */
29 #define M_MAX 100000000 /* = 100*10^6 */
30 /* maximal number of rows in the problem object */
32 #define N_MAX 100000000 /* = 100*10^6 */
33 /* maximal number of columns in the problem object */
35 #define NNZ_MAX 500000000 /* = 500*10^6 */
36 /* maximal number of constraint coefficients in the problem object */
38 /***********************************************************************
39 * NAME
40 *
41 * glp_create_prob - create problem object
42 *
43 * SYNOPSIS
44 *
45 * glp_prob *glp_create_prob(void);
46 *
47 * DESCRIPTION
48 *
49 * The routine glp_create_prob creates a new problem object, which is
50 * initially "empty", i.e. has no rows and columns.
51 *
52 * RETURNS
53 *
54 * The routine returns a pointer to the object created, which should be
55 * used in any subsequent operations on this object. */
57 static void create_prob(glp_prob *lp)
58 { lp->magic = GLP_PROB_MAGIC;
59 lp->pool = dmp_create_pool();
60 #if 0 /* 17/XI-2009 */
61 lp->cps = xmalloc(sizeof(struct LPXCPS));
62 lpx_reset_parms(lp);
63 #else
64 lp->parms = NULL;
65 #endif
66 lp->tree = NULL;
67 #if 0
68 lp->lwa = 0;
69 lp->cwa = NULL;
70 #endif
71 /* LP/MIP data */
72 lp->name = NULL;
73 lp->obj = NULL;
74 lp->dir = GLP_MIN;
75 lp->c0 = 0.0;
76 lp->m_max = 100;
77 lp->n_max = 200;
78 lp->m = lp->n = 0;
79 lp->nnz = 0;
80 lp->row = xcalloc(1+lp->m_max, sizeof(GLPROW *));
81 lp->col = xcalloc(1+lp->n_max, sizeof(GLPCOL *));
82 lp->r_tree = lp->c_tree = NULL;
83 /* basis factorization */
84 lp->valid = 0;
85 lp->head = xcalloc(1+lp->m_max, sizeof(int));
86 lp->bfcp = NULL;
87 lp->bfd = NULL;
88 /* basic solution (LP) */
89 lp->pbs_stat = lp->dbs_stat = GLP_UNDEF;
90 lp->obj_val = 0.0;
91 lp->it_cnt = 0;
92 lp->some = 0;
93 /* interior-point solution (LP) */
94 lp->ipt_stat = GLP_UNDEF;
95 lp->ipt_obj = 0.0;
96 /* integer solution (MIP) */
97 lp->mip_stat = GLP_UNDEF;
98 lp->mip_obj = 0.0;
99 return;
100 }
102 glp_prob *glp_create_prob(void)
103 { glp_prob *lp;
104 lp = xmalloc(sizeof(glp_prob));
105 create_prob(lp);
106 return lp;
107 }
109 /***********************************************************************
110 * NAME
111 *
112 * glp_set_prob_name - assign (change) problem name
113 *
114 * SYNOPSIS
115 *
116 * void glp_set_prob_name(glp_prob *lp, const char *name);
117 *
118 * DESCRIPTION
119 *
120 * The routine glp_set_prob_name assigns a given symbolic name (1 up to
121 * 255 characters) to the specified problem object.
122 *
123 * If the parameter name is NULL or empty string, the routine erases an
124 * existing symbolic name of the problem object. */
126 void glp_set_prob_name(glp_prob *lp, const char *name)
127 { glp_tree *tree = lp->tree;
128 if (tree != NULL && tree->reason != 0)
129 xerror("glp_set_prob_name: operation not allowed\n");
130 if (lp->name != NULL)
131 { dmp_free_atom(lp->pool, lp->name, strlen(lp->name)+1);
132 lp->name = NULL;
133 }
134 if (!(name == NULL || name[0] == '\0'))
135 { int k;
136 for (k = 0; name[k] != '\0'; k++)
137 { if (k == 256)
138 xerror("glp_set_prob_name: problem name too long\n");
139 if (iscntrl((unsigned char)name[k]))
140 xerror("glp_set_prob_name: problem name contains invalid"
141 " character(s)\n");
142 }
143 lp->name = dmp_get_atom(lp->pool, strlen(name)+1);
144 strcpy(lp->name, name);
145 }
146 return;
147 }
149 /***********************************************************************
150 * NAME
151 *
152 * glp_set_obj_name - assign (change) objective function name
153 *
154 * SYNOPSIS
155 *
156 * void glp_set_obj_name(glp_prob *lp, const char *name);
157 *
158 * DESCRIPTION
159 *
160 * The routine glp_set_obj_name assigns a given symbolic name (1 up to
161 * 255 characters) to the objective function of the specified problem
162 * object.
163 *
164 * If the parameter name is NULL or empty string, the routine erases an
165 * existing name of the objective function. */
167 void glp_set_obj_name(glp_prob *lp, const char *name)
168 { glp_tree *tree = lp->tree;
169 if (tree != NULL && tree->reason != 0)
170 xerror("glp_set_obj_name: operation not allowed\n");
171 if (lp->obj != NULL)
172 { dmp_free_atom(lp->pool, lp->obj, strlen(lp->obj)+1);
173 lp->obj = NULL;
174 }
175 if (!(name == NULL || name[0] == '\0'))
176 { int k;
177 for (k = 0; name[k] != '\0'; k++)
178 { if (k == 256)
179 xerror("glp_set_obj_name: objective name too long\n");
180 if (iscntrl((unsigned char)name[k]))
181 xerror("glp_set_obj_name: objective name contains invali"
182 "d character(s)\n");
183 }
184 lp->obj = dmp_get_atom(lp->pool, strlen(name)+1);
185 strcpy(lp->obj, name);
186 }
187 return;
188 }
190 /***********************************************************************
191 * NAME
192 *
193 * glp_set_obj_dir - set (change) optimization direction flag
194 *
195 * SYNOPSIS
196 *
197 * void glp_set_obj_dir(glp_prob *lp, int dir);
198 *
199 * DESCRIPTION
200 *
201 * The routine glp_set_obj_dir sets (changes) optimization direction
202 * flag (i.e. "sense" of the objective function) as specified by the
203 * parameter dir:
204 *
205 * GLP_MIN - minimization;
206 * GLP_MAX - maximization. */
208 void glp_set_obj_dir(glp_prob *lp, int dir)
209 { glp_tree *tree = lp->tree;
210 if (tree != NULL && tree->reason != 0)
211 xerror("glp_set_obj_dir: operation not allowed\n");
212 if (!(dir == GLP_MIN || dir == GLP_MAX))
213 xerror("glp_set_obj_dir: dir = %d; invalid direction flag\n",
214 dir);
215 lp->dir = dir;
216 return;
217 }
219 /***********************************************************************
220 * NAME
221 *
222 * glp_add_rows - add new rows to problem object
223 *
224 * SYNOPSIS
225 *
226 * int glp_add_rows(glp_prob *lp, int nrs);
227 *
228 * DESCRIPTION
229 *
230 * The routine glp_add_rows adds nrs rows (constraints) to the specified
231 * problem object. New rows are always added to the end of the row list,
232 * so the ordinal numbers of existing rows remain unchanged.
233 *
234 * Being added each new row is initially free (unbounded) and has empty
235 * list of the constraint coefficients.
236 *
237 * RETURNS
238 *
239 * The routine glp_add_rows returns the ordinal number of the first new
240 * row added to the problem object. */
242 int glp_add_rows(glp_prob *lp, int nrs)
243 { glp_tree *tree = lp->tree;
244 GLPROW *row;
245 int m_new, i;
246 /* determine new number of rows */
247 if (nrs < 1)
248 xerror("glp_add_rows: nrs = %d; invalid number of rows\n",
249 nrs);
250 if (nrs > M_MAX - lp->m)
251 xerror("glp_add_rows: nrs = %d; too many rows\n", nrs);
252 m_new = lp->m + nrs;
253 /* increase the room, if necessary */
254 if (lp->m_max < m_new)
255 { GLPROW **save = lp->row;
256 while (lp->m_max < m_new)
257 { lp->m_max += lp->m_max;
258 xassert(lp->m_max > 0);
259 }
260 lp->row = xcalloc(1+lp->m_max, sizeof(GLPROW *));
261 memcpy(&lp->row[1], &save[1], lp->m * sizeof(GLPROW *));
262 xfree(save);
263 /* do not forget about the basis header */
264 xfree(lp->head);
265 lp->head = xcalloc(1+lp->m_max, sizeof(int));
266 }
267 /* add new rows to the end of the row list */
268 for (i = lp->m+1; i <= m_new; i++)
269 { /* create row descriptor */
270 lp->row[i] = row = dmp_get_atom(lp->pool, sizeof(GLPROW));
271 row->i = i;
272 row->name = NULL;
273 row->node = NULL;
274 #if 1 /* 20/IX-2008 */
275 row->level = 0;
276 row->origin = 0;
277 row->klass = 0;
278 if (tree != NULL)
279 { switch (tree->reason)
280 { case 0:
281 break;
282 case GLP_IROWGEN:
283 xassert(tree->curr != NULL);
284 row->level = tree->curr->level;
285 row->origin = GLP_RF_LAZY;
286 break;
287 case GLP_ICUTGEN:
288 xassert(tree->curr != NULL);
289 row->level = tree->curr->level;
290 row->origin = GLP_RF_CUT;
291 break;
292 default:
293 xassert(tree != tree);
294 }
295 }
296 #endif
297 row->type = GLP_FR;
298 row->lb = row->ub = 0.0;
299 row->ptr = NULL;
300 row->rii = 1.0;
301 row->stat = GLP_BS;
302 #if 0
303 row->bind = -1;
304 #else
305 row->bind = 0;
306 #endif
307 row->prim = row->dual = 0.0;
308 row->pval = row->dval = 0.0;
309 row->mipx = 0.0;
310 }
311 /* set new number of rows */
312 lp->m = m_new;
313 /* invalidate the basis factorization */
314 lp->valid = 0;
315 #if 1
316 if (tree != NULL && tree->reason != 0) tree->reopt = 1;
317 #endif
318 /* return the ordinal number of the first row added */
319 return m_new - nrs + 1;
320 }
322 /***********************************************************************
323 * NAME
324 *
325 * glp_add_cols - add new columns to problem object
326 *
327 * SYNOPSIS
328 *
329 * int glp_add_cols(glp_prob *lp, int ncs);
330 *
331 * DESCRIPTION
332 *
333 * The routine glp_add_cols adds ncs columns (structural variables) to
334 * the specified problem object. New columns are always added to the end
335 * of the column list, so the ordinal numbers of existing columns remain
336 * unchanged.
337 *
338 * Being added each new column is initially fixed at zero and has empty
339 * list of the constraint coefficients.
340 *
341 * RETURNS
342 *
343 * The routine glp_add_cols returns the ordinal number of the first new
344 * column added to the problem object. */
346 int glp_add_cols(glp_prob *lp, int ncs)
347 { glp_tree *tree = lp->tree;
348 GLPCOL *col;
349 int n_new, j;
350 if (tree != NULL && tree->reason != 0)
351 xerror("glp_add_cols: operation not allowed\n");
352 /* determine new number of columns */
353 if (ncs < 1)
354 xerror("glp_add_cols: ncs = %d; invalid number of columns\n",
355 ncs);
356 if (ncs > N_MAX - lp->n)
357 xerror("glp_add_cols: ncs = %d; too many columns\n", ncs);
358 n_new = lp->n + ncs;
359 /* increase the room, if necessary */
360 if (lp->n_max < n_new)
361 { GLPCOL **save = lp->col;
362 while (lp->n_max < n_new)
363 { lp->n_max += lp->n_max;
364 xassert(lp->n_max > 0);
365 }
366 lp->col = xcalloc(1+lp->n_max, sizeof(GLPCOL *));
367 memcpy(&lp->col[1], &save[1], lp->n * sizeof(GLPCOL *));
368 xfree(save);
369 }
370 /* add new columns to the end of the column list */
371 for (j = lp->n+1; j <= n_new; j++)
372 { /* create column descriptor */
373 lp->col[j] = col = dmp_get_atom(lp->pool, sizeof(GLPCOL));
374 col->j = j;
375 col->name = NULL;
376 col->node = NULL;
377 col->kind = GLP_CV;
378 col->type = GLP_FX;
379 col->lb = col->ub = 0.0;
380 col->coef = 0.0;
381 col->ptr = NULL;
382 col->sjj = 1.0;
383 col->stat = GLP_NS;
384 #if 0
385 col->bind = -1;
386 #else
387 col->bind = 0; /* the basis may remain valid */
388 #endif
389 col->prim = col->dual = 0.0;
390 col->pval = col->dval = 0.0;
391 col->mipx = 0.0;
392 }
393 /* set new number of columns */
394 lp->n = n_new;
395 /* return the ordinal number of the first column added */
396 return n_new - ncs + 1;
397 }
399 /***********************************************************************
400 * NAME
401 *
402 * glp_set_row_name - assign (change) row name
403 *
404 * SYNOPSIS
405 *
406 * void glp_set_row_name(glp_prob *lp, int i, const char *name);
407 *
408 * DESCRIPTION
409 *
410 * The routine glp_set_row_name assigns a given symbolic name (1 up to
411 * 255 characters) to i-th row (auxiliary variable) of the specified
412 * problem object.
413 *
414 * If the parameter name is NULL or empty string, the routine erases an
415 * existing name of i-th row. */
417 void glp_set_row_name(glp_prob *lp, int i, const char *name)
418 { glp_tree *tree = lp->tree;
419 GLPROW *row;
420 if (!(1 <= i && i <= lp->m))
421 xerror("glp_set_row_name: i = %d; row number out of range\n",
422 i);
423 row = lp->row[i];
424 if (tree != NULL && tree->reason != 0)
425 { xassert(tree->curr != NULL);
426 xassert(row->level == tree->curr->level);
427 }
428 if (row->name != NULL)
429 { if (row->node != NULL)
430 { xassert(lp->r_tree != NULL);
431 avl_delete_node(lp->r_tree, row->node);
432 row->node = NULL;
433 }
434 dmp_free_atom(lp->pool, row->name, strlen(row->name)+1);
435 row->name = NULL;
436 }
437 if (!(name == NULL || name[0] == '\0'))
438 { int k;
439 for (k = 0; name[k] != '\0'; k++)
440 { if (k == 256)
441 xerror("glp_set_row_name: i = %d; row name too long\n",
442 i);
443 if (iscntrl((unsigned char)name[k]))
444 xerror("glp_set_row_name: i = %d: row name contains inva"
445 "lid character(s)\n", i);
446 }
447 row->name = dmp_get_atom(lp->pool, strlen(name)+1);
448 strcpy(row->name, name);
449 if (lp->r_tree != NULL)
450 { xassert(row->node == NULL);
451 row->node = avl_insert_node(lp->r_tree, row->name);
452 avl_set_node_link(row->node, row);
453 }
454 }
455 return;
456 }
458 /***********************************************************************
459 * NAME
460 *
461 * glp_set_col_name - assign (change) column name
462 *
463 * SYNOPSIS
464 *
465 * void glp_set_col_name(glp_prob *lp, int j, const char *name);
466 *
467 * DESCRIPTION
468 *
469 * The routine glp_set_col_name assigns a given symbolic name (1 up to
470 * 255 characters) to j-th column (structural variable) of the specified
471 * problem object.
472 *
473 * If the parameter name is NULL or empty string, the routine erases an
474 * existing name of j-th column. */
476 void glp_set_col_name(glp_prob *lp, int j, const char *name)
477 { glp_tree *tree = lp->tree;
478 GLPCOL *col;
479 if (tree != NULL && tree->reason != 0)
480 xerror("glp_set_col_name: operation not allowed\n");
481 if (!(1 <= j && j <= lp->n))
482 xerror("glp_set_col_name: j = %d; column number out of range\n"
483 , j);
484 col = lp->col[j];
485 if (col->name != NULL)
486 { if (col->node != NULL)
487 { xassert(lp->c_tree != NULL);
488 avl_delete_node(lp->c_tree, col->node);
489 col->node = NULL;
490 }
491 dmp_free_atom(lp->pool, col->name, strlen(col->name)+1);
492 col->name = NULL;
493 }
494 if (!(name == NULL || name[0] == '\0'))
495 { int k;
496 for (k = 0; name[k] != '\0'; k++)
497 { if (k == 256)
498 xerror("glp_set_col_name: j = %d; column name too long\n"
499 , j);
500 if (iscntrl((unsigned char)name[k]))
501 xerror("glp_set_col_name: j = %d: column name contains i"
502 "nvalid character(s)\n", j);
503 }
504 col->name = dmp_get_atom(lp->pool, strlen(name)+1);
505 strcpy(col->name, name);
506 if (lp->c_tree != NULL && col->name != NULL)
507 { xassert(col->node == NULL);
508 col->node = avl_insert_node(lp->c_tree, col->name);
509 avl_set_node_link(col->node, col);
510 }
511 }
512 return;
513 }
515 /***********************************************************************
516 * NAME
517 *
518 * glp_set_row_bnds - set (change) row bounds
519 *
520 * SYNOPSIS
521 *
522 * void glp_set_row_bnds(glp_prob *lp, int i, int type, double lb,
523 * double ub);
524 *
525 * DESCRIPTION
526 *
527 * The routine glp_set_row_bnds sets (changes) the type and bounds of
528 * i-th row (auxiliary variable) of the specified problem object.
529 *
530 * Parameters type, lb, and ub specify the type, lower bound, and upper
531 * bound, respectively, as follows:
532 *
533 * Type Bounds Comments
534 * ------------------------------------------------------
535 * GLP_FR -inf < x < +inf Free variable
536 * GLP_LO lb <= x < +inf Variable with lower bound
537 * GLP_UP -inf < x <= ub Variable with upper bound
538 * GLP_DB lb <= x <= ub Double-bounded variable
539 * GLP_FX x = lb Fixed variable
540 *
541 * where x is the auxiliary variable associated with i-th row.
542 *
543 * If the row has no lower bound, the parameter lb is ignored. If the
544 * row has no upper bound, the parameter ub is ignored. If the row is
545 * an equality constraint (i.e. the corresponding auxiliary variable is
546 * of fixed type), only the parameter lb is used while the parameter ub
547 * is ignored. */
549 void glp_set_row_bnds(glp_prob *lp, int i, int type, double lb,
550 double ub)
551 { GLPROW *row;
552 if (!(1 <= i && i <= lp->m))
553 xerror("glp_set_row_bnds: i = %d; row number out of range\n",
554 i);
555 row = lp->row[i];
556 row->type = type;
557 switch (type)
558 { case GLP_FR:
559 row->lb = row->ub = 0.0;
560 if (row->stat != GLP_BS) row->stat = GLP_NF;
561 break;
562 case GLP_LO:
563 row->lb = lb, row->ub = 0.0;
564 if (row->stat != GLP_BS) row->stat = GLP_NL;
565 break;
566 case GLP_UP:
567 row->lb = 0.0, row->ub = ub;
568 if (row->stat != GLP_BS) row->stat = GLP_NU;
569 break;
570 case GLP_DB:
571 row->lb = lb, row->ub = ub;
572 if (!(row->stat == GLP_BS ||
573 row->stat == GLP_NL || row->stat == GLP_NU))
574 row->stat = (fabs(lb) <= fabs(ub) ? GLP_NL : GLP_NU);
575 break;
576 case GLP_FX:
577 row->lb = row->ub = lb;
578 if (row->stat != GLP_BS) row->stat = GLP_NS;
579 break;
580 default:
581 xerror("glp_set_row_bnds: i = %d; type = %d; invalid row ty"
582 "pe\n", i, type);
583 }
584 return;
585 }
587 /***********************************************************************
588 * NAME
589 *
590 * glp_set_col_bnds - set (change) column bounds
591 *
592 * SYNOPSIS
593 *
594 * void glp_set_col_bnds(glp_prob *lp, int j, int type, double lb,
595 * double ub);
596 *
597 * DESCRIPTION
598 *
599 * The routine glp_set_col_bnds sets (changes) the type and bounds of
600 * j-th column (structural variable) of the specified problem object.
601 *
602 * Parameters type, lb, and ub specify the type, lower bound, and upper
603 * bound, respectively, as follows:
604 *
605 * Type Bounds Comments
606 * ------------------------------------------------------
607 * GLP_FR -inf < x < +inf Free variable
608 * GLP_LO lb <= x < +inf Variable with lower bound
609 * GLP_UP -inf < x <= ub Variable with upper bound
610 * GLP_DB lb <= x <= ub Double-bounded variable
611 * GLP_FX x = lb Fixed variable
612 *
613 * where x is the structural variable associated with j-th column.
614 *
615 * If the column has no lower bound, the parameter lb is ignored. If the
616 * column has no upper bound, the parameter ub is ignored. If the column
617 * is of fixed type, only the parameter lb is used while the parameter
618 * ub is ignored. */
620 void glp_set_col_bnds(glp_prob *lp, int j, int type, double lb,
621 double ub)
622 { GLPCOL *col;
623 if (!(1 <= j && j <= lp->n))
624 xerror("glp_set_col_bnds: j = %d; column number out of range\n"
625 , j);
626 col = lp->col[j];
627 col->type = type;
628 switch (type)
629 { case GLP_FR:
630 col->lb = col->ub = 0.0;
631 if (col->stat != GLP_BS) col->stat = GLP_NF;
632 break;
633 case GLP_LO:
634 col->lb = lb, col->ub = 0.0;
635 if (col->stat != GLP_BS) col->stat = GLP_NL;
636 break;
637 case GLP_UP:
638 col->lb = 0.0, col->ub = ub;
639 if (col->stat != GLP_BS) col->stat = GLP_NU;
640 break;
641 case GLP_DB:
642 col->lb = lb, col->ub = ub;
643 if (!(col->stat == GLP_BS ||
644 col->stat == GLP_NL || col->stat == GLP_NU))
645 col->stat = (fabs(lb) <= fabs(ub) ? GLP_NL : GLP_NU);
646 break;
647 case GLP_FX:
648 col->lb = col->ub = lb;
649 if (col->stat != GLP_BS) col->stat = GLP_NS;
650 break;
651 default:
652 xerror("glp_set_col_bnds: j = %d; type = %d; invalid column"
653 " type\n", j, type);
654 }
655 return;
656 }
658 /***********************************************************************
659 * NAME
660 *
661 * glp_set_obj_coef - set (change) obj. coefficient or constant term
662 *
663 * SYNOPSIS
664 *
665 * void glp_set_obj_coef(glp_prob *lp, int j, double coef);
666 *
667 * DESCRIPTION
668 *
669 * The routine glp_set_obj_coef sets (changes) objective coefficient at
670 * j-th column (structural variable) of the specified problem object.
671 *
672 * If the parameter j is 0, the routine sets (changes) the constant term
673 * ("shift") of the objective function. */
675 void glp_set_obj_coef(glp_prob *lp, int j, double coef)
676 { glp_tree *tree = lp->tree;
677 if (tree != NULL && tree->reason != 0)
678 xerror("glp_set_obj_coef: operation not allowed\n");
679 if (!(0 <= j && j <= lp->n))
680 xerror("glp_set_obj_coef: j = %d; column number out of range\n"
681 , j);
682 if (j == 0)
683 lp->c0 = coef;
684 else
685 lp->col[j]->coef = coef;
686 return;
687 }
689 /***********************************************************************
690 * NAME
691 *
692 * glp_set_mat_row - set (replace) row of the constraint matrix
693 *
694 * SYNOPSIS
695 *
696 * void glp_set_mat_row(glp_prob *lp, int i, int len, const int ind[],
697 * const double val[]);
698 *
699 * DESCRIPTION
700 *
701 * The routine glp_set_mat_row stores (replaces) the contents of i-th
702 * row of the constraint matrix of the specified problem object.
703 *
704 * Column indices and numeric values of new row elements must be placed
705 * in locations ind[1], ..., ind[len] and val[1], ..., val[len], where
706 * 0 <= len <= n is the new length of i-th row, n is the current number
707 * of columns in the problem object. Elements with identical column
708 * indices are not allowed. Zero elements are allowed, but they are not
709 * stored in the constraint matrix.
710 *
711 * If the parameter len is zero, the parameters ind and/or val can be
712 * specified as NULL. */
714 void glp_set_mat_row(glp_prob *lp, int i, int len, const int ind[],
715 const double val[])
716 { glp_tree *tree = lp->tree;
717 GLPROW *row;
718 GLPCOL *col;
719 GLPAIJ *aij, *next;
720 int j, k;
721 /* obtain pointer to i-th row */
722 if (!(1 <= i && i <= lp->m))
723 xerror("glp_set_mat_row: i = %d; row number out of range\n",
724 i);
725 row = lp->row[i];
726 if (tree != NULL && tree->reason != 0)
727 { xassert(tree->curr != NULL);
728 xassert(row->level == tree->curr->level);
729 }
730 /* remove all existing elements from i-th row */
731 while (row->ptr != NULL)
732 { /* take next element in the row */
733 aij = row->ptr;
734 /* remove the element from the row list */
735 row->ptr = aij->r_next;
736 /* obtain pointer to corresponding column */
737 col = aij->col;
738 /* remove the element from the column list */
739 if (aij->c_prev == NULL)
740 col->ptr = aij->c_next;
741 else
742 aij->c_prev->c_next = aij->c_next;
743 if (aij->c_next == NULL)
744 ;
745 else
746 aij->c_next->c_prev = aij->c_prev;
747 /* return the element to the memory pool */
748 dmp_free_atom(lp->pool, aij, sizeof(GLPAIJ)), lp->nnz--;
749 /* if the corresponding column is basic, invalidate the basis
750 factorization */
751 if (col->stat == GLP_BS) lp->valid = 0;
752 }
753 /* store new contents of i-th row */
754 if (!(0 <= len && len <= lp->n))
755 xerror("glp_set_mat_row: i = %d; len = %d; invalid row length "
756 "\n", i, len);
757 if (len > NNZ_MAX - lp->nnz)
758 xerror("glp_set_mat_row: i = %d; len = %d; too many constraint"
759 " coefficients\n", i, len);
760 for (k = 1; k <= len; k++)
761 { /* take number j of corresponding column */
762 j = ind[k];
763 /* obtain pointer to j-th column */
764 if (!(1 <= j && j <= lp->n))
765 xerror("glp_set_mat_row: i = %d; ind[%d] = %d; column index"
766 " out of range\n", i, k, j);
767 col = lp->col[j];
768 /* if there is element with the same column index, it can only
769 be found in the beginning of j-th column list */
770 if (col->ptr != NULL && col->ptr->row->i == i)
771 xerror("glp_set_mat_row: i = %d; ind[%d] = %d; duplicate co"
772 "lumn indices not allowed\n", i, k, j);
773 /* create new element */
774 aij = dmp_get_atom(lp->pool, sizeof(GLPAIJ)), lp->nnz++;
775 aij->row = row;
776 aij->col = col;
777 aij->val = val[k];
778 /* add the new element to the beginning of i-th row and j-th
779 column lists */
780 aij->r_prev = NULL;
781 aij->r_next = row->ptr;
782 aij->c_prev = NULL;
783 aij->c_next = col->ptr;
784 if (aij->r_next != NULL) aij->r_next->r_prev = aij;
785 if (aij->c_next != NULL) aij->c_next->c_prev = aij;
786 row->ptr = col->ptr = aij;
787 /* if the corresponding column is basic, invalidate the basis
788 factorization */
789 if (col->stat == GLP_BS && aij->val != 0.0) lp->valid = 0;
790 }
791 /* remove zero elements from i-th row */
792 for (aij = row->ptr; aij != NULL; aij = next)
793 { next = aij->r_next;
794 if (aij->val == 0.0)
795 { /* remove the element from the row list */
796 if (aij->r_prev == NULL)
797 row->ptr = next;
798 else
799 aij->r_prev->r_next = next;
800 if (next == NULL)
801 ;
802 else
803 next->r_prev = aij->r_prev;
804 /* remove the element from the column list */
805 xassert(aij->c_prev == NULL);
806 aij->col->ptr = aij->c_next;
807 if (aij->c_next != NULL) aij->c_next->c_prev = NULL;
808 /* return the element to the memory pool */
809 dmp_free_atom(lp->pool, aij, sizeof(GLPAIJ)), lp->nnz--;
810 }
811 }
812 return;
813 }
815 /***********************************************************************
816 * NAME
817 *
818 * glp_set_mat_col - set (replace) column of the constraint matrix
819 *
820 * SYNOPSIS
821 *
822 * void glp_set_mat_col(glp_prob *lp, int j, int len, const int ind[],
823 * const double val[]);
824 *
825 * DESCRIPTION
826 *
827 * The routine glp_set_mat_col stores (replaces) the contents of j-th
828 * column of the constraint matrix of the specified problem object.
829 *
830 * Row indices and numeric values of new column elements must be placed
831 * in locations ind[1], ..., ind[len] and val[1], ..., val[len], where
832 * 0 <= len <= m is the new length of j-th column, m is the current
833 * number of rows in the problem object. Elements with identical column
834 * indices are not allowed. Zero elements are allowed, but they are not
835 * stored in the constraint matrix.
836 *
837 * If the parameter len is zero, the parameters ind and/or val can be
838 * specified as NULL. */
840 void glp_set_mat_col(glp_prob *lp, int j, int len, const int ind[],
841 const double val[])
842 { glp_tree *tree = lp->tree;
843 GLPROW *row;
844 GLPCOL *col;
845 GLPAIJ *aij, *next;
846 int i, k;
847 if (tree != NULL && tree->reason != 0)
848 xerror("glp_set_mat_col: operation not allowed\n");
849 /* obtain pointer to j-th column */
850 if (!(1 <= j && j <= lp->n))
851 xerror("glp_set_mat_col: j = %d; column number out of range\n",
852 j);
853 col = lp->col[j];
854 /* remove all existing elements from j-th column */
855 while (col->ptr != NULL)
856 { /* take next element in the column */
857 aij = col->ptr;
858 /* remove the element from the column list */
859 col->ptr = aij->c_next;
860 /* obtain pointer to corresponding row */
861 row = aij->row;
862 /* remove the element from the row list */
863 if (aij->r_prev == NULL)
864 row->ptr = aij->r_next;
865 else
866 aij->r_prev->r_next = aij->r_next;
867 if (aij->r_next == NULL)
868 ;
869 else
870 aij->r_next->r_prev = aij->r_prev;
871 /* return the element to the memory pool */
872 dmp_free_atom(lp->pool, aij, sizeof(GLPAIJ)), lp->nnz--;
873 }
874 /* store new contents of j-th column */
875 if (!(0 <= len && len <= lp->m))
876 xerror("glp_set_mat_col: j = %d; len = %d; invalid column leng"
877 "th\n", j, len);
878 if (len > NNZ_MAX - lp->nnz)
879 xerror("glp_set_mat_col: j = %d; len = %d; too many constraint"
880 " coefficients\n", j, len);
881 for (k = 1; k <= len; k++)
882 { /* take number i of corresponding row */
883 i = ind[k];
884 /* obtain pointer to i-th row */
885 if (!(1 <= i && i <= lp->m))
886 xerror("glp_set_mat_col: j = %d; ind[%d] = %d; row index ou"
887 "t of range\n", j, k, i);
888 row = lp->row[i];
889 /* if there is element with the same row index, it can only be
890 found in the beginning of i-th row list */
891 if (row->ptr != NULL && row->ptr->col->j == j)
892 xerror("glp_set_mat_col: j = %d; ind[%d] = %d; duplicate ro"
893 "w indices not allowed\n", j, k, i);
894 /* create new element */
895 aij = dmp_get_atom(lp->pool, sizeof(GLPAIJ)), lp->nnz++;
896 aij->row = row;
897 aij->col = col;
898 aij->val = val[k];
899 /* add the new element to the beginning of i-th row and j-th
900 column lists */
901 aij->r_prev = NULL;
902 aij->r_next = row->ptr;
903 aij->c_prev = NULL;
904 aij->c_next = col->ptr;
905 if (aij->r_next != NULL) aij->r_next->r_prev = aij;
906 if (aij->c_next != NULL) aij->c_next->c_prev = aij;
907 row->ptr = col->ptr = aij;
908 }
909 /* remove zero elements from j-th column */
910 for (aij = col->ptr; aij != NULL; aij = next)
911 { next = aij->c_next;
912 if (aij->val == 0.0)
913 { /* remove the element from the row list */
914 xassert(aij->r_prev == NULL);
915 aij->row->ptr = aij->r_next;
916 if (aij->r_next != NULL) aij->r_next->r_prev = NULL;
917 /* remove the element from the column list */
918 if (aij->c_prev == NULL)
919 col->ptr = next;
920 else
921 aij->c_prev->c_next = next;
922 if (next == NULL)
923 ;
924 else
925 next->c_prev = aij->c_prev;
926 /* return the element to the memory pool */
927 dmp_free_atom(lp->pool, aij, sizeof(GLPAIJ)), lp->nnz--;
928 }
929 }
930 /* if j-th column is basic, invalidate the basis factorization */
931 if (col->stat == GLP_BS) lp->valid = 0;
932 return;
933 }
935 /***********************************************************************
936 * NAME
937 *
938 * glp_load_matrix - load (replace) the whole constraint matrix
939 *
940 * SYNOPSIS
941 *
942 * void glp_load_matrix(glp_prob *lp, int ne, const int ia[],
943 * const int ja[], const double ar[]);
944 *
945 * DESCRIPTION
946 *
947 * The routine glp_load_matrix loads the constraint matrix passed in
948 * the arrays ia, ja, and ar into the specified problem object. Before
949 * loading the current contents of the constraint matrix is destroyed.
950 *
951 * Constraint coefficients (elements of the constraint matrix) must be
952 * specified as triplets (ia[k], ja[k], ar[k]) for k = 1, ..., ne,
953 * where ia[k] is the row index, ja[k] is the column index, ar[k] is a
954 * numeric value of corresponding constraint coefficient. The parameter
955 * ne specifies the total number of (non-zero) elements in the matrix
956 * to be loaded. Coefficients with identical indices are not allowed.
957 * Zero coefficients are allowed, however, they are not stored in the
958 * constraint matrix.
959 *
960 * If the parameter ne is zero, the parameters ia, ja, and ar can be
961 * specified as NULL. */
963 void glp_load_matrix(glp_prob *lp, int ne, const int ia[],
964 const int ja[], const double ar[])
965 { glp_tree *tree = lp->tree;
966 GLPROW *row;
967 GLPCOL *col;
968 GLPAIJ *aij, *next;
969 int i, j, k;
970 if (tree != NULL && tree->reason != 0)
971 xerror("glp_load_matrix: operation not allowed\n");
972 /* clear the constraint matrix */
973 for (i = 1; i <= lp->m; i++)
974 { row = lp->row[i];
975 while (row->ptr != NULL)
976 { aij = row->ptr;
977 row->ptr = aij->r_next;
978 dmp_free_atom(lp->pool, aij, sizeof(GLPAIJ)), lp->nnz--;
979 }
980 }
981 xassert(lp->nnz == 0);
982 for (j = 1; j <= lp->n; j++) lp->col[j]->ptr = NULL;
983 /* load the new contents of the constraint matrix and build its
984 row lists */
985 if (ne < 0)
986 xerror("glp_load_matrix: ne = %d; invalid number of constraint"
987 " coefficients\n", ne);
988 if (ne > NNZ_MAX)
989 xerror("glp_load_matrix: ne = %d; too many constraint coeffici"
990 "ents\n", ne);
991 for (k = 1; k <= ne; k++)
992 { /* take indices of new element */
993 i = ia[k], j = ja[k];
994 /* obtain pointer to i-th row */
995 if (!(1 <= i && i <= lp->m))
996 xerror("glp_load_matrix: ia[%d] = %d; row index out of rang"
997 "e\n", k, i);
998 row = lp->row[i];
999 /* obtain pointer to j-th column */
1000 if (!(1 <= j && j <= lp->n))
1001 xerror("glp_load_matrix: ja[%d] = %d; column index out of r"
1002 "ange\n", k, j);
1003 col = lp->col[j];
1004 /* create new element */
1005 aij = dmp_get_atom(lp->pool, sizeof(GLPAIJ)), lp->nnz++;
1006 aij->row = row;
1007 aij->col = col;
1008 aij->val = ar[k];
1009 /* add the new element to the beginning of i-th row list */
1010 aij->r_prev = NULL;
1011 aij->r_next = row->ptr;
1012 if (aij->r_next != NULL) aij->r_next->r_prev = aij;
1013 row->ptr = aij;
1014 }
1015 xassert(lp->nnz == ne);
1016 /* build column lists of the constraint matrix and check elements
1017 with identical indices */
1018 for (i = 1; i <= lp->m; i++)
1019 { for (aij = lp->row[i]->ptr; aij != NULL; aij = aij->r_next)
1020 { /* obtain pointer to corresponding column */
1021 col = aij->col;
1022 /* if there is element with identical indices, it can only
1023 be found in the beginning of j-th column list */
1024 if (col->ptr != NULL && col->ptr->row->i == i)
1025 { for (k = 1; k <= ne; k++)
1026 if (ia[k] == i && ja[k] == col->j) break;
1027 xerror("glp_load_mat: ia[%d] = %d; ja[%d] = %d; duplicat"
1028 "e indices not allowed\n", k, i, k, col->j);
1029 }
1030 /* add the element to the beginning of j-th column list */
1031 aij->c_prev = NULL;
1032 aij->c_next = col->ptr;
1033 if (aij->c_next != NULL) aij->c_next->c_prev = aij;
1034 col->ptr = aij;
1035 }
1036 }
1037 /* remove zero elements from the constraint matrix */
1038 for (i = 1; i <= lp->m; i++)
1039 { row = lp->row[i];
1040 for (aij = row->ptr; aij != NULL; aij = next)
1041 { next = aij->r_next;
1042 if (aij->val == 0.0)
1043 { /* remove the element from the row list */
1044 if (aij->r_prev == NULL)
1045 row->ptr = next;
1046 else
1047 aij->r_prev->r_next = next;
1048 if (next == NULL)
1049 ;
1050 else
1051 next->r_prev = aij->r_prev;
1052 /* remove the element from the column list */
1053 if (aij->c_prev == NULL)
1054 aij->col->ptr = aij->c_next;
1055 else
1056 aij->c_prev->c_next = aij->c_next;
1057 if (aij->c_next == NULL)
1058 ;
1059 else
1060 aij->c_next->c_prev = aij->c_prev;
1061 /* return the element to the memory pool */
1062 dmp_free_atom(lp->pool, aij, sizeof(GLPAIJ)), lp->nnz--;
1063 }
1064 }
1065 }
1066 /* invalidate the basis factorization */
1067 lp->valid = 0;
1068 return;
1069 }
1071 /***********************************************************************
1072 * NAME
1073 *
1074 * glp_check_dup - check for duplicate elements in sparse matrix
1075 *
1076 * SYNOPSIS
1077 *
1078 * int glp_check_dup(int m, int n, int ne, const int ia[],
1079 * const int ja[]);
1080 *
1081 * DESCRIPTION
1082 *
1083 * The routine glp_check_dup checks for duplicate elements (that is,
1084 * elements with identical indices) in a sparse matrix specified in the
1085 * coordinate format.
1086 *
1087 * The parameters m and n specifies, respectively, the number of rows
1088 * and columns in the matrix, m >= 0, n >= 0.
1089 *
1090 * The parameter ne specifies the number of (structurally) non-zero
1091 * elements in the matrix, ne >= 0.
1092 *
1093 * Elements of the matrix are specified as doublets (ia[k],ja[k]) for
1094 * k = 1,...,ne, where ia[k] is a row index, ja[k] is a column index.
1095 *
1096 * The routine glp_check_dup can be used prior to a call to the routine
1097 * glp_load_matrix to check that the constraint matrix to be loaded has
1098 * no duplicate elements.
1099 *
1100 * RETURNS
1101 *
1102 * The routine glp_check_dup returns one of the following values:
1103 *
1104 * 0 - the matrix has no duplicate elements;
1105 *
1106 * -k - indices ia[k] or/and ja[k] are out of range;
1107 *
1108 * +k - element (ia[k],ja[k]) is duplicate. */
1110 int glp_check_dup(int m, int n, int ne, const int ia[], const int ja[])
1111 { int i, j, k, *ptr, *next, ret;
1112 char *flag;
1113 if (m < 0)
1114 xerror("glp_check_dup: m = %d; invalid parameter\n");
1115 if (n < 0)
1116 xerror("glp_check_dup: n = %d; invalid parameter\n");
1117 if (ne < 0)
1118 xerror("glp_check_dup: ne = %d; invalid parameter\n");
1119 if (ne > 0 && ia == NULL)
1120 xerror("glp_check_dup: ia = %p; invalid parameter\n", ia);
1121 if (ne > 0 && ja == NULL)
1122 xerror("glp_check_dup: ja = %p; invalid parameter\n", ja);
1123 for (k = 1; k <= ne; k++)
1124 { i = ia[k], j = ja[k];
1125 if (!(1 <= i && i <= m && 1 <= j && j <= n))
1126 { ret = -k;
1127 goto done;
1128 }
1129 }
1130 if (m == 0 || n == 0)
1131 { ret = 0;
1132 goto done;
1133 }
1134 /* allocate working arrays */
1135 ptr = xcalloc(1+m, sizeof(int));
1136 next = xcalloc(1+ne, sizeof(int));
1137 flag = xcalloc(1+n, sizeof(char));
1138 /* build row lists */
1139 for (i = 1; i <= m; i++)
1140 ptr[i] = 0;
1141 for (k = 1; k <= ne; k++)
1142 { i = ia[k];
1143 next[k] = ptr[i];
1144 ptr[i] = k;
1145 }
1146 /* clear column flags */
1147 for (j = 1; j <= n; j++)
1148 flag[j] = 0;
1149 /* check for duplicate elements */
1150 for (i = 1; i <= m; i++)
1151 { for (k = ptr[i]; k != 0; k = next[k])
1152 { j = ja[k];
1153 if (flag[j])
1154 { /* find first element (i,j) */
1155 for (k = 1; k <= ne; k++)
1156 if (ia[k] == i && ja[k] == j) break;
1157 xassert(k <= ne);
1158 /* find next (duplicate) element (i,j) */
1159 for (k++; k <= ne; k++)
1160 if (ia[k] == i && ja[k] == j) break;
1161 xassert(k <= ne);
1162 ret = +k;
1163 goto skip;
1164 }
1165 flag[j] = 1;
1166 }
1167 /* clear column flags */
1168 for (k = ptr[i]; k != 0; k = next[k])
1169 flag[ja[k]] = 0;
1170 }
1171 /* no duplicate element found */
1172 ret = 0;
1173 skip: /* free working arrays */
1174 xfree(ptr);
1175 xfree(next);
1176 xfree(flag);
1177 done: return ret;
1178 }
1180 /***********************************************************************
1181 * NAME
1182 *
1183 * glp_sort_matrix - sort elements of the constraint matrix
1184 *
1185 * SYNOPSIS
1186 *
1187 * void glp_sort_matrix(glp_prob *P);
1188 *
1189 * DESCRIPTION
1190 *
1191 * The routine glp_sort_matrix sorts elements of the constraint matrix
1192 * rebuilding its row and column linked lists. On exit from the routine
1193 * the constraint matrix is not changed, however, elements in the row
1194 * linked lists become ordered by ascending column indices, and the
1195 * elements in the column linked lists become ordered by ascending row
1196 * indices. */
1198 void glp_sort_matrix(glp_prob *P)
1199 { GLPAIJ *aij;
1200 int i, j;
1201 if (P == NULL || P->magic != GLP_PROB_MAGIC)
1202 xerror("glp_sort_matrix: P = %p; invalid problem object\n",
1203 P);
1204 /* rebuild row linked lists */
1205 for (i = P->m; i >= 1; i--)
1206 P->row[i]->ptr = NULL;
1207 for (j = P->n; j >= 1; j--)
1208 { for (aij = P->col[j]->ptr; aij != NULL; aij = aij->c_next)
1209 { i = aij->row->i;
1210 aij->r_prev = NULL;
1211 aij->r_next = P->row[i]->ptr;
1212 if (aij->r_next != NULL) aij->r_next->r_prev = aij;
1213 P->row[i]->ptr = aij;
1214 }
1215 }
1216 /* rebuild column linked lists */
1217 for (j = P->n; j >= 1; j--)
1218 P->col[j]->ptr = NULL;
1219 for (i = P->m; i >= 1; i--)
1220 { for (aij = P->row[i]->ptr; aij != NULL; aij = aij->r_next)
1221 { j = aij->col->j;
1222 aij->c_prev = NULL;
1223 aij->c_next = P->col[j]->ptr;
1224 if (aij->c_next != NULL) aij->c_next->c_prev = aij;
1225 P->col[j]->ptr = aij;
1226 }
1227 }
1228 return;
1229 }
1231 /***********************************************************************
1232 * NAME
1233 *
1234 * glp_del_rows - delete rows from problem object
1235 *
1236 * SYNOPSIS
1237 *
1238 * void glp_del_rows(glp_prob *lp, int nrs, const int num[]);
1239 *
1240 * DESCRIPTION
1241 *
1242 * The routine glp_del_rows deletes rows from the specified problem
1243 * object. Ordinal numbers of rows to be deleted should be placed in
1244 * locations num[1], ..., num[nrs], where nrs > 0.
1245 *
1246 * Note that deleting rows involves changing ordinal numbers of other
1247 * rows remaining in the problem object. New ordinal numbers of the
1248 * remaining rows are assigned under the assumption that the original
1249 * order of rows is not changed. */
1251 void glp_del_rows(glp_prob *lp, int nrs, const int num[])
1252 { glp_tree *tree = lp->tree;
1253 GLPROW *row;
1254 int i, k, m_new;
1255 /* mark rows to be deleted */
1256 if (!(1 <= nrs && nrs <= lp->m))
1257 xerror("glp_del_rows: nrs = %d; invalid number of rows\n",
1258 nrs);
1259 for (k = 1; k <= nrs; k++)
1260 { /* take the number of row to be deleted */
1261 i = num[k];
1262 /* obtain pointer to i-th row */
1263 if (!(1 <= i && i <= lp->m))
1264 xerror("glp_del_rows: num[%d] = %d; row number out of range"
1265 "\n", k, i);
1266 row = lp->row[i];
1267 if (tree != NULL && tree->reason != 0)
1268 { if (!(tree->reason == GLP_IROWGEN ||
1269 tree->reason == GLP_ICUTGEN))
1270 xerror("glp_del_rows: operation not allowed\n");
1271 xassert(tree->curr != NULL);
1272 if (row->level != tree->curr->level)
1273 xerror("glp_del_rows: num[%d] = %d; invalid attempt to d"
1274 "elete row created not in current subproblem\n", k,i);
1275 if (row->stat != GLP_BS)
1276 xerror("glp_del_rows: num[%d] = %d; invalid attempt to d"
1277 "elete active row (constraint)\n", k, i);
1278 tree->reinv = 1;
1279 }
1280 /* check that the row is not marked yet */
1281 if (row->i == 0)
1282 xerror("glp_del_rows: num[%d] = %d; duplicate row numbers n"
1283 "ot allowed\n", k, i);
1284 /* erase symbolic name assigned to the row */
1285 glp_set_row_name(lp, i, NULL);
1286 xassert(row->node == NULL);
1287 /* erase corresponding row of the constraint matrix */
1288 glp_set_mat_row(lp, i, 0, NULL, NULL);
1289 xassert(row->ptr == NULL);
1290 /* mark the row to be deleted */
1291 row->i = 0;
1292 }
1293 /* delete all marked rows from the row list */
1294 m_new = 0;
1295 for (i = 1; i <= lp->m; i++)
1296 { /* obtain pointer to i-th row */
1297 row = lp->row[i];
1298 /* check if the row is marked */
1299 if (row->i == 0)
1300 { /* it is marked, delete it */
1301 dmp_free_atom(lp->pool, row, sizeof(GLPROW));
1302 }
1303 else
1304 { /* it is not marked; keep it */
1305 row->i = ++m_new;
1306 lp->row[row->i] = row;
1307 }
1308 }
1309 /* set new number of rows */
1310 lp->m = m_new;
1311 /* invalidate the basis factorization */
1312 lp->valid = 0;
1313 return;
1314 }
1316 /***********************************************************************
1317 * NAME
1318 *
1319 * glp_del_cols - delete columns from problem object
1320 *
1321 * SYNOPSIS
1322 *
1323 * void glp_del_cols(glp_prob *lp, int ncs, const int num[]);
1324 *
1325 * DESCRIPTION
1326 *
1327 * The routine glp_del_cols deletes columns from the specified problem
1328 * object. Ordinal numbers of columns to be deleted should be placed in
1329 * locations num[1], ..., num[ncs], where ncs > 0.
1330 *
1331 * Note that deleting columns involves changing ordinal numbers of
1332 * other columns remaining in the problem object. New ordinal numbers
1333 * of the remaining columns are assigned under the assumption that the
1334 * original order of columns is not changed. */
1336 void glp_del_cols(glp_prob *lp, int ncs, const int num[])
1337 { glp_tree *tree = lp->tree;
1338 GLPCOL *col;
1339 int j, k, n_new;
1340 if (tree != NULL && tree->reason != 0)
1341 xerror("glp_del_cols: operation not allowed\n");
1342 /* mark columns to be deleted */
1343 if (!(1 <= ncs && ncs <= lp->n))
1344 xerror("glp_del_cols: ncs = %d; invalid number of columns\n",
1345 ncs);
1346 for (k = 1; k <= ncs; k++)
1347 { /* take the number of column to be deleted */
1348 j = num[k];
1349 /* obtain pointer to j-th column */
1350 if (!(1 <= j && j <= lp->n))
1351 xerror("glp_del_cols: num[%d] = %d; column number out of ra"
1352 "nge", k, j);
1353 col = lp->col[j];
1354 /* check that the column is not marked yet */
1355 if (col->j == 0)
1356 xerror("glp_del_cols: num[%d] = %d; duplicate column number"
1357 "s not allowed\n", k, j);
1358 /* erase symbolic name assigned to the column */
1359 glp_set_col_name(lp, j, NULL);
1360 xassert(col->node == NULL);
1361 /* erase corresponding column of the constraint matrix */
1362 glp_set_mat_col(lp, j, 0, NULL, NULL);
1363 xassert(col->ptr == NULL);
1364 /* mark the column to be deleted */
1365 col->j = 0;
1366 /* if it is basic, invalidate the basis factorization */
1367 if (col->stat == GLP_BS) lp->valid = 0;
1368 }
1369 /* delete all marked columns from the column list */
1370 n_new = 0;
1371 for (j = 1; j <= lp->n; j++)
1372 { /* obtain pointer to j-th column */
1373 col = lp->col[j];
1374 /* check if the column is marked */
1375 if (col->j == 0)
1376 { /* it is marked; delete it */
1377 dmp_free_atom(lp->pool, col, sizeof(GLPCOL));
1378 }
1379 else
1380 { /* it is not marked; keep it */
1381 col->j = ++n_new;
1382 lp->col[col->j] = col;
1383 }
1384 }
1385 /* set new number of columns */
1386 lp->n = n_new;
1387 /* if the basis header is still valid, adjust it */
1388 if (lp->valid)
1389 { int m = lp->m;
1390 int *head = lp->head;
1391 for (j = 1; j <= n_new; j++)
1392 { k = lp->col[j]->bind;
1393 if (k != 0)
1394 { xassert(1 <= k && k <= m);
1395 head[k] = m + j;
1396 }
1397 }
1398 }
1399 return;
1400 }
1402 /***********************************************************************
1403 * NAME
1404 *
1405 * glp_copy_prob - copy problem object content
1406 *
1407 * SYNOPSIS
1408 *
1409 * void glp_copy_prob(glp_prob *dest, glp_prob *prob, int names);
1410 *
1411 * DESCRIPTION
1412 *
1413 * The routine glp_copy_prob copies the content of the problem object
1414 * prob to the problem object dest.
1415 *
1416 * The parameter names is a flag. If it is non-zero, the routine also
1417 * copies all symbolic names; otherwise, if it is zero, symbolic names
1418 * are not copied. */
1420 void glp_copy_prob(glp_prob *dest, glp_prob *prob, int names)
1421 { glp_tree *tree = dest->tree;
1422 glp_bfcp bfcp;
1423 int i, j, len, *ind;
1424 double *val;
1425 if (tree != NULL && tree->reason != 0)
1426 xerror("glp_copy_prob: operation not allowed\n");
1427 if (dest == prob)
1428 xerror("glp_copy_prob: copying problem object to itself not al"
1429 "lowed\n");
1430 if (!(names == GLP_ON || names == GLP_OFF))
1431 xerror("glp_copy_prob: names = %d; invalid parameter\n",
1432 names);
1433 glp_erase_prob(dest);
1434 if (names && prob->name != NULL)
1435 glp_set_prob_name(dest, prob->name);
1436 if (names && prob->obj != NULL)
1437 glp_set_obj_name(dest, prob->obj);
1438 dest->dir = prob->dir;
1439 dest->c0 = prob->c0;
1440 if (prob->m > 0)
1441 glp_add_rows(dest, prob->m);
1442 if (prob->n > 0)
1443 glp_add_cols(dest, prob->n);
1444 glp_get_bfcp(prob, &bfcp);
1445 glp_set_bfcp(dest, &bfcp);
1446 dest->pbs_stat = prob->pbs_stat;
1447 dest->dbs_stat = prob->dbs_stat;
1448 dest->obj_val = prob->obj_val;
1449 dest->some = prob->some;
1450 dest->ipt_stat = prob->ipt_stat;
1451 dest->ipt_obj = prob->ipt_obj;
1452 dest->mip_stat = prob->mip_stat;
1453 dest->mip_obj = prob->mip_obj;
1454 for (i = 1; i <= prob->m; i++)
1455 { GLPROW *to = dest->row[i];
1456 GLPROW *from = prob->row[i];
1457 if (names && from->name != NULL)
1458 glp_set_row_name(dest, i, from->name);
1459 to->type = from->type;
1460 to->lb = from->lb;
1461 to->ub = from->ub;
1462 to->rii = from->rii;
1463 to->stat = from->stat;
1464 to->prim = from->prim;
1465 to->dual = from->dual;
1466 to->pval = from->pval;
1467 to->dval = from->dval;
1468 to->mipx = from->mipx;
1469 }
1470 ind = xcalloc(1+prob->m, sizeof(int));
1471 val = xcalloc(1+prob->m, sizeof(double));
1472 for (j = 1; j <= prob->n; j++)
1473 { GLPCOL *to = dest->col[j];
1474 GLPCOL *from = prob->col[j];
1475 if (names && from->name != NULL)
1476 glp_set_col_name(dest, j, from->name);
1477 to->kind = from->kind;
1478 to->type = from->type;
1479 to->lb = from->lb;
1480 to->ub = from->ub;
1481 to->coef = from->coef;
1482 len = glp_get_mat_col(prob, j, ind, val);
1483 glp_set_mat_col(dest, j, len, ind, val);
1484 to->sjj = from->sjj;
1485 to->stat = from->stat;
1486 to->prim = from->prim;
1487 to->dual = from->dual;
1488 to->pval = from->pval;
1489 to->dval = from->dval;
1490 to->mipx = from->mipx;
1491 }
1492 xfree(ind);
1493 xfree(val);
1494 return;
1495 }
1497 /***********************************************************************
1498 * NAME
1499 *
1500 * glp_erase_prob - erase problem object content
1501 *
1502 * SYNOPSIS
1503 *
1504 * void glp_erase_prob(glp_prob *lp);
1505 *
1506 * DESCRIPTION
1507 *
1508 * The routine glp_erase_prob erases the content of the specified
1509 * problem object. The effect of this operation is the same as if the
1510 * problem object would be deleted with the routine glp_delete_prob and
1511 * then created anew with the routine glp_create_prob, with exception
1512 * that the handle (pointer) to the problem object remains valid. */
1514 static void delete_prob(glp_prob *lp);
1516 void glp_erase_prob(glp_prob *lp)
1517 { glp_tree *tree = lp->tree;
1518 if (tree != NULL && tree->reason != 0)
1519 xerror("glp_erase_prob: operation not allowed\n");
1520 delete_prob(lp);
1521 create_prob(lp);
1522 return;
1523 }
1525 /***********************************************************************
1526 * NAME
1527 *
1528 * glp_delete_prob - delete problem object
1529 *
1530 * SYNOPSIS
1531 *
1532 * void glp_delete_prob(glp_prob *lp);
1533 *
1534 * DESCRIPTION
1535 *
1536 * The routine glp_delete_prob deletes the specified problem object and
1537 * frees all the memory allocated to it. */
1539 static void delete_prob(glp_prob *lp)
1540 { lp->magic = 0x3F3F3F3F;
1541 dmp_delete_pool(lp->pool);
1542 #if 0 /* 17/XI-2009 */
1543 xfree(lp->cps);
1544 #else
1545 if (lp->parms != NULL) xfree(lp->parms);
1546 #endif
1547 xassert(lp->tree == NULL);
1548 #if 0
1549 if (lp->cwa != NULL) xfree(lp->cwa);
1550 #endif
1551 xfree(lp->row);
1552 xfree(lp->col);
1553 if (lp->r_tree != NULL) avl_delete_tree(lp->r_tree);
1554 if (lp->c_tree != NULL) avl_delete_tree(lp->c_tree);
1555 xfree(lp->head);
1556 if (lp->bfcp != NULL) xfree(lp->bfcp);
1557 if (lp->bfd != NULL) bfd_delete_it(lp->bfd);
1558 return;
1559 }
1561 void glp_delete_prob(glp_prob *lp)
1562 { glp_tree *tree = lp->tree;
1563 if (tree != NULL && tree->reason != 0)
1564 xerror("glp_delete_prob: operation not allowed\n");
1565 delete_prob(lp);
1566 xfree(lp);
1567 return;
1568 }
1570 /* eof */