COIN-OR::LEMON - Graph Library

source: lemon-project-template-glpk/deps/glpk/src/glpapi01.c @ 10:5545663ca997

subpack-glpk
Last change on this file since 10:5545663ca997 was 9:33de93886c88, checked in by Alpar Juttner <alpar@…>, 13 years ago

Import GLPK 4.47

File size: 51.7 KB
Line 
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
57static 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
102glp_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
126void 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
167void 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
208void 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
242int 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
346int 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
417void 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
476void 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
549void 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
620void 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
675void 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
714void 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
840void 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
963void 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
1110int 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;
1173skip: /* free working arrays */
1174      xfree(ptr);
1175      xfree(next);
1176      xfree(flag);
1177done: 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
1198void 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
1251void 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
1336void 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
1420void 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
1514static void delete_prob(glp_prob *lp);
1515
1516void 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
1539static 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
1561void 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 */
Note: See TracBrowser for help on using the repository browser.