1
/* glpapi01.c (problem creating and modifying routines) */
3
/***********************************************************************
4
* This code is part of GLPK (GNU Linear Programming Kit).
6
* Copyright (C) 2000, 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008,
7
* 2009, 2010 Andrew Makhorin, Department for Applied Informatics,
8
* Moscow Aviation Institute, Moscow, Russia. All rights reserved.
9
* E-mail: <mao@gnu.org>.
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.
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.
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
***********************************************************************/
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
/***********************************************************************
41
* glp_create_prob - create problem object
45
* glp_prob *glp_create_prob(void);
49
* The routine glp_create_prob creates a new problem object, which is
50
* initially "empty", i.e. has no rows and columns.
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));
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 */
85
lp->head = xcalloc(1+lp->m_max, sizeof(int));
88
/* basic solution (LP) */
89
lp->pbs_stat = lp->dbs_stat = GLP_UNDEF;
93
/* interior-point solution (LP) */
94
lp->ipt_stat = GLP_UNDEF;
96
/* integer solution (MIP) */
97
lp->mip_stat = GLP_UNDEF;
102
glp_prob *glp_create_prob(void)
104
lp = xmalloc(sizeof(glp_prob));
109
/***********************************************************************
112
* glp_set_prob_name - assign (change) problem name
116
* void glp_set_prob_name(glp_prob *lp, const char *name);
120
* The routine glp_set_prob_name assigns a given symbolic name (1 up to
121
* 255 characters) to the specified problem object.
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);
134
if (!(name == NULL || name[0] == '\0'))
136
for (k = 0; name[k] != '\0'; k++)
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"
143
lp->name = dmp_get_atom(lp->pool, strlen(name)+1);
144
strcpy(lp->name, name);
149
/***********************************************************************
152
* glp_set_obj_name - assign (change) objective function name
156
* void glp_set_obj_name(glp_prob *lp, const char *name);
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
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");
172
{ dmp_free_atom(lp->pool, lp->obj, strlen(lp->obj)+1);
175
if (!(name == NULL || name[0] == '\0'))
177
for (k = 0; name[k] != '\0'; k++)
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"
184
lp->obj = dmp_get_atom(lp->pool, strlen(name)+1);
185
strcpy(lp->obj, name);
190
/***********************************************************************
193
* glp_set_obj_dir - set (change) optimization direction flag
197
* void glp_set_obj_dir(glp_prob *lp, int dir);
201
* The routine glp_set_obj_dir sets (changes) optimization direction
202
* flag (i.e. "sense" of the objective function) as specified by the
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",
219
/***********************************************************************
222
* glp_add_rows - add new rows to problem object
226
* int glp_add_rows(glp_prob *lp, int nrs);
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.
234
* Being added each new row is initially free (unbounded) and has empty
235
* list of the constraint coefficients.
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;
246
/* determine new number of rows */
248
xerror("glp_add_rows: nrs = %d; invalid number of rows\n",
250
if (nrs > M_MAX - lp->m)
251
xerror("glp_add_rows: nrs = %d; too many rows\n", 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);
260
lp->row = xcalloc(1+lp->m_max, sizeof(GLPROW *));
261
memcpy(&lp->row[1], &save[1], lp->m * sizeof(GLPROW *));
263
/* do not forget about the basis header */
265
lp->head = xcalloc(1+lp->m_max, sizeof(int));
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));
274
#if 1 /* 20/IX-2008 */
279
{ switch (tree->reason)
283
xassert(tree->curr != NULL);
284
row->level = tree->curr->level;
285
row->origin = GLP_RF_LAZY;
288
xassert(tree->curr != NULL);
289
row->level = tree->curr->level;
290
row->origin = GLP_RF_CUT;
293
xassert(tree != tree);
298
row->lb = row->ub = 0.0;
307
row->prim = row->dual = 0.0;
308
row->pval = row->dval = 0.0;
311
/* set new number of rows */
313
/* invalidate the basis factorization */
316
if (tree != NULL && tree->reason != 0) tree->reopt = 1;
318
/* return the ordinal number of the first row added */
319
return m_new - nrs + 1;
322
/***********************************************************************
325
* glp_add_cols - add new columns to problem object
329
* int glp_add_cols(glp_prob *lp, int ncs);
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
338
* Being added each new column is initially fixed at zero and has empty
339
* list of the constraint coefficients.
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;
350
if (tree != NULL && tree->reason != 0)
351
xerror("glp_add_cols: operation not allowed\n");
352
/* determine new number of columns */
354
xerror("glp_add_cols: ncs = %d; invalid number of columns\n",
356
if (ncs > N_MAX - lp->n)
357
xerror("glp_add_cols: ncs = %d; too many columns\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);
366
lp->col = xcalloc(1+lp->n_max, sizeof(GLPCOL *));
367
memcpy(&lp->col[1], &save[1], lp->n * sizeof(GLPCOL *));
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));
379
col->lb = col->ub = 0.0;
387
col->bind = 0; /* the basis may remain valid */
389
col->prim = col->dual = 0.0;
390
col->pval = col->dval = 0.0;
393
/* set new number of columns */
395
/* return the ordinal number of the first column added */
396
return n_new - ncs + 1;
399
/***********************************************************************
402
* glp_set_row_name - assign (change) row name
406
* void glp_set_row_name(glp_prob *lp, int i, const char *name);
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
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;
420
if (!(1 <= i && i <= lp->m))
421
xerror("glp_set_row_name: i = %d; row number out of range\n",
424
if (tree != NULL && tree->reason != 0)
425
{ xassert(tree->curr != NULL);
426
xassert(row->level == tree->curr->level);
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);
434
dmp_free_atom(lp->pool, row->name, strlen(row->name)+1);
437
if (!(name == NULL || name[0] == '\0'))
439
for (k = 0; name[k] != '\0'; k++)
441
xerror("glp_set_row_name: i = %d; row name too long\n",
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);
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);
458
/***********************************************************************
461
* glp_set_col_name - assign (change) column name
465
* void glp_set_col_name(glp_prob *lp, int j, const char *name);
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
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;
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"
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);
491
dmp_free_atom(lp->pool, col->name, strlen(col->name)+1);
494
if (!(name == NULL || name[0] == '\0'))
496
for (k = 0; name[k] != '\0'; k++)
498
xerror("glp_set_col_name: j = %d; column name too long\n"
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);
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);
515
/***********************************************************************
518
* glp_set_row_bnds - set (change) row bounds
522
* void glp_set_row_bnds(glp_prob *lp, int i, int type, double lb,
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.
530
* Parameters type, lb, and ub specify the type, lower bound, and upper
531
* bound, respectively, as follows:
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
541
* where x is the auxiliary variable associated with i-th row.
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
549
void glp_set_row_bnds(glp_prob *lp, int i, int type, double lb,
552
if (!(1 <= i && i <= lp->m))
553
xerror("glp_set_row_bnds: i = %d; row number out of range\n",
559
row->lb = row->ub = 0.0;
560
if (row->stat != GLP_BS) row->stat = GLP_NF;
563
row->lb = lb, row->ub = 0.0;
564
if (row->stat != GLP_BS) row->stat = GLP_NL;
567
row->lb = 0.0, row->ub = ub;
568
if (row->stat != GLP_BS) row->stat = GLP_NU;
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);
577
row->lb = row->ub = lb;
578
if (row->stat != GLP_BS) row->stat = GLP_NS;
581
xerror("glp_set_row_bnds: i = %d; type = %d; invalid row ty"
587
/***********************************************************************
590
* glp_set_col_bnds - set (change) column bounds
594
* void glp_set_col_bnds(glp_prob *lp, int j, int type, double lb,
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.
602
* Parameters type, lb, and ub specify the type, lower bound, and upper
603
* bound, respectively, as follows:
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
613
* where x is the structural variable associated with j-th column.
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
620
void glp_set_col_bnds(glp_prob *lp, int j, int type, double lb,
623
if (!(1 <= j && j <= lp->n))
624
xerror("glp_set_col_bnds: j = %d; column number out of range\n"
630
col->lb = col->ub = 0.0;
631
if (col->stat != GLP_BS) col->stat = GLP_NF;
634
col->lb = lb, col->ub = 0.0;
635
if (col->stat != GLP_BS) col->stat = GLP_NL;
638
col->lb = 0.0, col->ub = ub;
639
if (col->stat != GLP_BS) col->stat = GLP_NU;
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);
648
col->lb = col->ub = lb;
649
if (col->stat != GLP_BS) col->stat = GLP_NS;
652
xerror("glp_set_col_bnds: j = %d; type = %d; invalid column"
658
/***********************************************************************
661
* glp_set_obj_coef - set (change) obj. coefficient or constant term
665
* void glp_set_obj_coef(glp_prob *lp, int j, double coef);
669
* The routine glp_set_obj_coef sets (changes) objective coefficient at
670
* j-th column (structural variable) of the specified problem object.
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"
685
lp->col[j]->coef = coef;
689
/***********************************************************************
692
* glp_set_mat_row - set (replace) row of the constraint matrix
696
* void glp_set_mat_row(glp_prob *lp, int i, int len, const int ind[],
697
* const double val[]);
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.
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.
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[],
716
{ glp_tree *tree = lp->tree;
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",
726
if (tree != NULL && tree->reason != 0)
727
{ xassert(tree->curr != NULL);
728
xassert(row->level == tree->curr->level);
730
/* remove all existing elements from i-th row */
731
while (row->ptr != NULL)
732
{ /* take next element in the row */
734
/* remove the element from the row list */
735
row->ptr = aij->r_next;
736
/* obtain pointer to corresponding column */
738
/* remove the element from the column list */
739
if (aij->c_prev == NULL)
740
col->ptr = aij->c_next;
742
aij->c_prev->c_next = aij->c_next;
743
if (aij->c_next == NULL)
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
751
if (col->stat == GLP_BS) lp->valid = 0;
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 "
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 */
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);
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++;
778
/* add the new element to the beginning of i-th row and j-th
781
aij->r_next = row->ptr;
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
789
if (col->stat == GLP_BS && aij->val != 0.0) lp->valid = 0;
791
/* remove zero elements from i-th row */
792
for (aij = row->ptr; aij != NULL; aij = next)
793
{ next = aij->r_next;
795
{ /* remove the element from the row list */
796
if (aij->r_prev == NULL)
799
aij->r_prev->r_next = next;
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--;
815
/***********************************************************************
818
* glp_set_mat_col - set (replace) column of the constraint matrix
822
* void glp_set_mat_col(glp_prob *lp, int j, int len, const int ind[],
823
* const double val[]);
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.
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.
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[],
842
{ glp_tree *tree = lp->tree;
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",
854
/* remove all existing elements from j-th column */
855
while (col->ptr != NULL)
856
{ /* take next element in the column */
858
/* remove the element from the column list */
859
col->ptr = aij->c_next;
860
/* obtain pointer to corresponding row */
862
/* remove the element from the row list */
863
if (aij->r_prev == NULL)
864
row->ptr = aij->r_next;
866
aij->r_prev->r_next = aij->r_next;
867
if (aij->r_next == NULL)
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--;
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"
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 */
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);
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++;
899
/* add the new element to the beginning of i-th row and j-th
902
aij->r_next = row->ptr;
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;
909
/* remove zero elements from j-th column */
910
for (aij = col->ptr; aij != NULL; aij = next)
911
{ next = aij->c_next;
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)
921
aij->c_prev->c_next = next;
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--;
930
/* if j-th column is basic, invalidate the basis factorization */
931
if (col->stat == GLP_BS) lp->valid = 0;
935
/***********************************************************************
938
* glp_load_matrix - load (replace) the whole constraint matrix
942
* void glp_load_matrix(glp_prob *lp, int ne, const int ia[],
943
* const int ja[], const double ar[]);
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.
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
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;
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++)
975
while (row->ptr != NULL)
977
row->ptr = aij->r_next;
978
dmp_free_atom(lp->pool, aij, sizeof(GLPAIJ)), lp->nnz--;
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
986
xerror("glp_load_matrix: ne = %d; invalid number of constraint"
987
" coefficients\n", ne);
989
xerror("glp_load_matrix: ne = %d; too many constraint coeffici"
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"
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"
1004
/* create new element */
1005
aij = dmp_get_atom(lp->pool, sizeof(GLPAIJ)), lp->nnz++;
1009
/* add the new element to the beginning of i-th row list */
1011
aij->r_next = row->ptr;
1012
if (aij->r_next != NULL) aij->r_next->r_prev = aij;
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 */
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);
1030
/* add the element to the beginning of j-th column list */
1032
aij->c_next = col->ptr;
1033
if (aij->c_next != NULL) aij->c_next->c_prev = aij;
1037
/* remove zero elements from the constraint matrix */
1038
for (i = 1; i <= lp->m; 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)
1047
aij->r_prev->r_next = next;
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;
1056
aij->c_prev->c_next = aij->c_next;
1057
if (aij->c_next == NULL)
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--;
1066
/* invalidate the basis factorization */
1071
/***********************************************************************
1074
* glp_check_dup - check for duplicate elements in sparse matrix
1078
* int glp_check_dup(int m, int n, int ne, const int ia[],
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.
1087
* The parameters m and n specifies, respectively, the number of rows
1088
* and columns in the matrix, m >= 0, n >= 0.
1090
* The parameter ne specifies the number of (structurally) non-zero
1091
* elements in the matrix, ne >= 0.
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.
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.
1102
* The routine glp_check_dup returns one of the following values:
1104
* 0 - the matrix has no duplicate elements;
1106
* -k - indices ia[k] or/and ja[k] are out of range;
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;
1114
xerror("glp_check_dup: m = %d; invalid parameter\n");
1116
xerror("glp_check_dup: n = %d; invalid parameter\n");
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))
1130
if (m == 0 || n == 0)
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++)
1141
for (k = 1; k <= ne; k++)
1146
/* clear column flags */
1147
for (j = 1; j <= n; j++)
1149
/* check for duplicate elements */
1150
for (i = 1; i <= m; i++)
1151
{ for (k = ptr[i]; k != 0; k = next[k])
1154
{ /* find first element (i,j) */
1155
for (k = 1; k <= ne; k++)
1156
if (ia[k] == i && ja[k] == j) break;
1158
/* find next (duplicate) element (i,j) */
1159
for (k++; k <= ne; k++)
1160
if (ia[k] == i && ja[k] == j) break;
1167
/* clear column flags */
1168
for (k = ptr[i]; k != 0; k = next[k])
1171
/* no duplicate element found */
1173
skip: /* free working arrays */
1180
/***********************************************************************
1183
* glp_sort_matrix - sort elements of the constraint matrix
1187
* void glp_sort_matrix(glp_prob *P);
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
1198
void glp_sort_matrix(glp_prob *P)
1201
if (P == NULL || P->magic != GLP_PROB_MAGIC)
1202
xerror("glp_sort_matrix: P = %p; invalid problem object\n",
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)
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;
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)
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;
1231
/***********************************************************************
1234
* glp_del_rows - delete rows from problem object
1238
* void glp_del_rows(glp_prob *lp, int nrs, const int num[]);
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.
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;
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",
1259
for (k = 1; k <= nrs; k++)
1260
{ /* take the number of row to be deleted */
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"
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);
1280
/* check that the row is not marked yet */
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 */
1293
/* delete all marked rows from the row list */
1295
for (i = 1; i <= lp->m; i++)
1296
{ /* obtain pointer to i-th row */
1298
/* check if the row is marked */
1300
{ /* it is marked, delete it */
1301
dmp_free_atom(lp->pool, row, sizeof(GLPROW));
1304
{ /* it is not marked; keep it */
1306
lp->row[row->i] = row;
1309
/* set new number of rows */
1311
/* invalidate the basis factorization */
1316
/***********************************************************************
1319
* glp_del_cols - delete columns from problem object
1323
* void glp_del_cols(glp_prob *lp, int ncs, const int num[]);
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.
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;
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",
1346
for (k = 1; k <= ncs; k++)
1347
{ /* take the number of column to be deleted */
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"
1354
/* check that the column is not marked yet */
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 */
1366
/* if it is basic, invalidate the basis factorization */
1367
if (col->stat == GLP_BS) lp->valid = 0;
1369
/* delete all marked columns from the column list */
1371
for (j = 1; j <= lp->n; j++)
1372
{ /* obtain pointer to j-th column */
1374
/* check if the column is marked */
1376
{ /* it is marked; delete it */
1377
dmp_free_atom(lp->pool, col, sizeof(GLPCOL));
1380
{ /* it is not marked; keep it */
1382
lp->col[col->j] = col;
1385
/* set new number of columns */
1387
/* if the basis header is still valid, adjust it */
1390
int *head = lp->head;
1391
for (j = 1; j <= n_new; j++)
1392
{ k = lp->col[j]->bind;
1394
{ xassert(1 <= k && k <= m);
1402
/***********************************************************************
1405
* glp_copy_prob - copy problem object content
1409
* void glp_copy_prob(glp_prob *dest, glp_prob *prob, int names);
1413
* The routine glp_copy_prob copies the content of the problem object
1414
* prob to the problem object dest.
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;
1423
int i, j, len, *ind;
1425
if (tree != NULL && tree->reason != 0)
1426
xerror("glp_copy_prob: operation not allowed\n");
1428
xerror("glp_copy_prob: copying problem object to itself not al"
1430
if (!(names == GLP_ON || names == GLP_OFF))
1431
xerror("glp_copy_prob: names = %d; invalid parameter\n",
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;
1441
glp_add_rows(dest, prob->m);
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;
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;
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;
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;
1497
/***********************************************************************
1500
* glp_erase_prob - erase problem object content
1504
* void glp_erase_prob(glp_prob *lp);
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");
1525
/***********************************************************************
1528
* glp_delete_prob - delete problem object
1532
* void glp_delete_prob(glp_prob *lp);
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 */
1545
if (lp->parms != NULL) xfree(lp->parms);
1547
xassert(lp->tree == NULL);
1549
if (lp->cwa != NULL) xfree(lp->cwa);
1553
if (lp->r_tree != NULL) avl_delete_tree(lp->r_tree);
1554
if (lp->c_tree != NULL) avl_delete_tree(lp->c_tree);
1556
if (lp->bfcp != NULL) xfree(lp->bfcp);
1557
if (lp->bfd != NULL) bfd_delete_it(lp->bfd);
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");
added
removed
optional/glpk/glpapi01.c
