lemon-project-template-glpk
comparison deps/glpk/src/glpapi01.c @ 11:4fc6ad2fb8a6
Test GLPK in src/main.cc
author | Alpar Juttner <alpar@cs.elte.hu> |
---|---|
date | Sun, 06 Nov 2011 21:43:29 +0100 |
parents | |
children |
comparison
equal
deleted
inserted
replaced
-1:000000000000 | 0:4d66e5b65013 |
---|---|
1 /* glpapi01.c (problem creating and modifying routines) */ | |
2 | |
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 ***********************************************************************/ | |
24 | |
25 #include "glpios.h" | |
26 | |
27 /* CAUTION: DO NOT CHANGE THE LIMITS BELOW */ | |
28 | |
29 #define M_MAX 100000000 /* = 100*10^6 */ | |
30 /* maximal number of rows in the problem object */ | |
31 | |
32 #define N_MAX 100000000 /* = 100*10^6 */ | |
33 /* maximal number of columns in the problem object */ | |
34 | |
35 #define NNZ_MAX 500000000 /* = 500*10^6 */ | |
36 /* maximal number of constraint coefficients in the problem object */ | |
37 | |
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. */ | |
56 | |
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 } | |
101 | |
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 } | |
108 | |
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. */ | |
125 | |
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 } | |
148 | |
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. */ | |
166 | |
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 } | |
189 | |
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. */ | |
207 | |
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 } | |
218 | |
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. */ | |
241 | |
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 } | |
321 | |
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. */ | |
345 | |
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 } | |
398 | |
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. */ | |
416 | |
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 } | |
457 | |
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. */ | |
475 | |
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 } | |
514 | |
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. */ | |
548 | |
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 } | |
586 | |
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. */ | |
619 | |
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 } | |
657 | |
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. */ | |
674 | |
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 } | |
688 | |
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. */ | |
713 | |
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 } | |
814 | |
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. */ | |
839 | |
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 } | |
934 | |
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. */ | |
962 | |
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 } | |
1070 | |
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. */ | |
1109 | |
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 } | |
1179 | |
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. */ | |
1197 | |
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 } | |
1230 | |
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. */ | |
1250 | |
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 } | |
1315 | |
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. */ | |
1335 | |
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 } | |
1401 | |
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. */ | |
1419 | |
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 } | |
1496 | |
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. */ | |
1513 | |
1514 static void delete_prob(glp_prob *lp); | |
1515 | |
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 } | |
1524 | |
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. */ | |
1538 | |
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 } | |
1560 | |
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 } | |
1569 | |
1570 /* eof */ |