glpapi01.c

著名的大规模线性规划求解器源码GLPK.C语言版本,可以修剪.内有详细帮助文档.

*
*  Column indices and numeric values of new row elements must be placed
*  in locations ind[1], ..., ind[len] and val[1], ..., val[len], where
*  0 <= len <= n is the new length of i-th row, n is the current number
*  of columns in the problem object. Elements with identical column
*  indices are not allowed. Zero elements are allowed, but they are not
*  stored in the constraint matrix.
*
*  If the parameter len is zero, the parameters ind and/or val can be
*  specified as NULL. */

void glp_set_mat_row(glp_prob *lp, int i, int len, const int ind[],
      const double val[])
{     glp_tree *tree = lp->tree;
      GLPROW *row;
      GLPCOL *col;
      GLPAIJ *aij, *next;
      int j, k;
      /* obtain pointer to i-th row */
      if (!(1 <= i && i <= lp->m))
         xerror("glp_set_mat_row: i = %d; row number out of range\n",
            i);
      row = lp->row[i];
      if (tree != NULL && tree->reason != 0)
      {  xassert(tree->curr != NULL);
         xassert(row->level == tree->curr->level);
      }
      /* remove all existing elements from i-th row */
      while (row->ptr != NULL)
      {  /* take next element in the row */
         aij = row->ptr;
         /* remove the element from the row list */
         row->ptr = aij->r_next;
         /* obtain pointer to corresponding column */
         col = aij->col;
         /* remove the element from the column list */
         if (aij->c_prev == NULL)
            col->ptr = aij->c_next;
         else
            aij->c_prev->c_next = aij->c_next;
         if (aij->c_next == NULL)
            ;
         else
            aij->c_next->c_prev = aij->c_prev;
         /* return the element to the memory pool */
         dmp_free_atom(lp->pool, aij, sizeof(GLPAIJ)), lp->nnz--;
         /* if the corresponding column is basic, invalidate the basis
            factorization */
         if (col->stat == GLP_BS) lp->valid = 0;
      }
      /* store new contents of i-th row */
      if (!(0 <= len && len <= lp->n))
         xerror("glp_set_mat_row: i = %d; len = %d; invalid row length "
            "\n", i, len);
      if (len > NNZ_MAX - lp->nnz)
         xerror("glp_set_mat_row: i = %d; len = %d; too many constraint"
            " coefficients\n", i, len);
      for (k = 1; k <= len; k++)
      {  /* take number j of corresponding column */
         j = ind[k];
         /* obtain pointer to j-th column */
         if (!(1 <= j && j <= lp->n))
            xerror("glp_set_mat_row: i = %d; ind[%d] = %d; column index"
               " out of range\n", i, k, j);
         col = lp->col[j];
         /* if there is element with the same column index, it can only
            be found in the beginning of j-th column list */
         if (col->ptr != NULL && col->ptr->row->i == i)
            xerror("glp_set_mat_row: i = %d; ind[%d] = %d; duplicate co"
               "lumn indices not allowed\n", i, k, j);
         /* create new element */
         aij = dmp_get_atom(lp->pool, sizeof(GLPAIJ)), lp->nnz++;
         aij->row = row;
         aij->col = col;
         aij->val = val[k];
         /* add the new element to the beginning of i-th row and j-th
            column lists */
         aij->r_prev = NULL;
         aij->r_next = row->ptr;
         aij->c_prev = NULL;
         aij->c_next = col->ptr;
         if (aij->r_next != NULL) aij->r_next->r_prev = aij;
         if (aij->c_next != NULL) aij->c_next->c_prev = aij;
         row->ptr = col->ptr = aij;
         /* if the corresponding column is basic, invalidate the basis
            factorization */
         if (col->stat == GLP_BS && aij->val != 0.0) lp->valid = 0;
      }
      /* remove zero elements from i-th row */
      for (aij = row->ptr; aij != NULL; aij = next)
      {  next = aij->r_next;
         if (aij->val == 0.0)
         {  /* remove the element from the row list */
            if (aij->r_prev == NULL)
               row->ptr = next;
            else
               aij->r_prev->r_next = next;
            if (next == NULL)
               ;
            else
               next->r_prev = aij->r_prev;
            /* remove the element from the column list */
            xassert(aij->c_prev == NULL);
            aij->col->ptr = aij->c_next;
            if (aij->c_next != NULL) aij->c_next->c_prev = NULL;
            /* return the element to the memory pool */
            dmp_free_atom(lp->pool, aij, sizeof(GLPAIJ)), lp->nnz--;
         }
      }
      return;
}

/***********************************************************************
*  NAME
*
*  glp_set_mat_col - set (replace) column of the constraint matrix
*
*  SYNOPSIS
*
*  void glp_set_mat_col(glp_prob *lp, int j, int len, const int ind[],
*     const double val[]);
*
*  DESCRIPTION
*
*  The routine glp_set_mat_col stores (replaces) the contents of j-th
*  column of the constraint matrix of the specified problem object.
*
*  Row indices and numeric values of new column elements must be placed
*  in locations ind[1], ..., ind[len] and val[1], ..., val[len], where
*  0 <= len <= m is the new length of j-th column, m is the current
*  number of rows in the problem object. Elements with identical column
*  indices are not allowed. Zero elements are allowed, but they are not
*  stored in the constraint matrix.
*
*  If the parameter len is zero, the parameters ind and/or val can be
*  specified as NULL. */

void glp_set_mat_col(glp_prob *lp, int j, int len, const int ind[],
      const double val[])
{     glp_tree *tree = lp->tree;
      GLPROW *row;
      GLPCOL *col;
      GLPAIJ *aij, *next;
      int i, k;
      if (tree != NULL && tree->reason != 0)
         xerror("glp_set_mat_col: operation not allowed\n");
      /* obtain pointer to j-th column */
      if (!(1 <= j && j <= lp->n))
         xerror("glp_set_mat_col: j = %d; column number out of range\n",
            j);
      col = lp->col[j];
      /* remove all existing elements from j-th column */
      while (col->ptr != NULL)
      {  /* take next element in the column */
         aij = col->ptr;
         /* remove the element from the column list */
         col->ptr = aij->c_next;
         /* obtain pointer to corresponding row */
         row = aij->row;
         /* remove the element from the row list */
         if (aij->r_prev == NULL)
            row->ptr = aij->r_next;
         else
            aij->r_prev->r_next = aij->r_next;
         if (aij->r_next == NULL)
            ;
         else
            aij->r_next->r_prev = aij->r_prev;
         /* return the element to the memory pool */
         dmp_free_atom(lp->pool, aij, sizeof(GLPAIJ)), lp->nnz--;
      }
      /* store new contents of j-th column */
      if (!(0 <= len && len <= lp->m))
         xerror("glp_set_mat_col: j = %d; len = %d; invalid column leng"
            "th\n", j, len);
      if (len > NNZ_MAX - lp->nnz)
         xerror("glp_set_mat_col: j = %d; len = %d; too many constraint"
            " coefficients\n", j, len);
      for (k = 1; k <= len; k++)
      {  /* take number i of corresponding row */
         i = ind[k];
         /* obtain pointer to i-th row */
         if (!(1 <= i && i <= lp->m))
            xerror("glp_set_mat_col: j = %d; ind[%d] = %d; row index ou"
               "t of range\n", j, k, i);
         row = lp->row[i];
         /* if there is element with the same row index, it can only be
            found in the beginning of i-th row list */
         if (row->ptr != NULL && row->ptr->col->j == j)
            xerror("glp_set_mat_col: j = %d; ind[%d] = %d; duplicate ro"
               "w indices not allowed\n", j, k, i);
         /* create new element */
         aij = dmp_get_atom(lp->pool, sizeof(GLPAIJ)), lp->nnz++;
         aij->row = row;
         aij->col = col;
         aij->val = val[k];
         /* add the new element to the beginning of i-th row and j-th
            column lists */
         aij->r_prev = NULL;
         aij->r_next = row->ptr;
         aij->c_prev = NULL;
         aij->c_next = col->ptr;
         if (aij->r_next != NULL) aij->r_next->r_prev = aij;
         if (aij->c_next != NULL) aij->c_next->c_prev = aij;
         row->ptr = col->ptr = aij;
      }
      /* remove zero elements from j-th column */
      for (aij = col->ptr; aij != NULL; aij = next)
      {  next = aij->c_next;
         if (aij->val == 0.0)
         {  /* remove the element from the row list */
            xassert(aij->r_prev == NULL);
            aij->row->ptr = aij->r_next;
            if (aij->r_next != NULL) aij->r_next->r_prev = NULL;
            /* remove the element from the column list */
            if (aij->c_prev == NULL)
               col->ptr = next;
            else
               aij->c_prev->c_next = next;
            if (next == NULL)
               ;
            else
               next->c_prev = aij->c_prev;
            /* return the element to the memory pool */
            dmp_free_atom(lp->pool, aij, sizeof(GLPAIJ)), lp->nnz--;
         }
      }
      /* if j-th column is basic, invalidate the basis factorization */
      if (col->stat == GLP_BS) lp->valid = 0;
      return;
}

/***********************************************************************
*  NAME
*
*  glp_load_matrix - load (replace) the whole constraint matrix
*
*  SYNOPSIS
*
*  void glp_load_matrix(glp_prob *lp, int ne, const int ia[],
*     const int ja[], const double ar[]);
*
*  DESCRIPTION
*
*  The routine glp_load_matrix loads the constraint matrix passed in
*  the arrays ia, ja, and ar into the specified problem object. Before
*  loading the current contents of the constraint matrix is destroyed.
*
*  Constraint coefficients (elements of the constraint matrix) must be
*  specified as triplets (ia[k], ja[k], ar[k]) for k = 1, ..., ne,
*  where ia[k] is the row index, ja[k] is the column index, ar[k] is a
*  numeric value of corresponding constraint coefficient. The parameter
*  ne specifies the total number of (non-zero) elements in the matrix
*  to be loaded. Coefficients with identical indices are not allowed.
*  Zero coefficients are allowed, however, they are not stored in the
*  constraint matrix.
*
*  If the parameter ne is zero, the parameters ia, ja, and ar can be
*  specified as NULL. */

void glp_load_matrix(glp_prob *lp, int ne, const int ia[],
      const int ja[], const double ar[])
{     glp_tree *tree = lp->tree;
      GLPROW *row;
      GLPCOL *col;
      GLPAIJ *aij, *next;
      int i, j, k;
      if (tree != NULL && tree->reason != 0)
         xerror("glp_load_matrix: operation not allowed\n");
      /* clear the constraint matrix */
      for (i = 1; i <= lp->m; i++)
      {  row = lp->row[i];
         while (row->ptr != NULL)
         {  aij = row->ptr;
            row->ptr = aij->r_next;
            dmp_free_atom(lp->pool, aij, sizeof(GLPAIJ)), lp->nnz--;
         }
      }
      xassert(lp->nnz == 0);
      for (j = 1; j <= lp->n; j++) lp->col[j]->ptr = NULL;
      /* load the new contents of the constraint matrix and build its
         row lists */
      if (ne < 0)
         xerror("glp_load_matrix: ne = %d; invalid number of constraint"
            " coefficients\n", ne);
      if (ne > NNZ_MAX)
         xerror("glp_load_matrix: ne = %d; too many constraint coeffici"
            "ents\n", ne);
      for (k = 1; k <= ne; k++)
      {  /* take indices of new element */
         i = ia[k], j = ja[k];
         /* obtain pointer to i-th row */
         if (!(1 <= i && i <= lp->m))
            xerror("glp_load_matrix: ia[%d] = %d; row index out of rang"
               "e\n", k, i);
         row = lp->row[i];
         /* obtain pointer to j-th column */
         if (!(1 <= j && j <= lp->n))
            xerror("glp_load_matrix: ja[%d] = %d; column index out of r"
               "ange\n", k, j);
         col = lp->col[j];
         /* create new element */
         aij = dmp_get_atom(lp->pool, sizeof(GLPAIJ)), lp->nnz++;
         aij->row = row;
         aij->col = col;
         aij->val = ar[k];
         /* add the new element to the beginning of i-th row list */
         aij->r_prev = NULL;
         aij->r_next = row->ptr;
         if (aij->r_next != NULL) aij->r_next->r_prev = aij;
         row->ptr = aij;
      }
      xassert(lp->nnz == ne);
      /* build column lists of the constraint matrix and check elements
         with identical indices */
      for (i = 1; i <= lp->m; i++)
      {  for (aij = lp->row[i]->ptr; aij != NULL; aij = aij->r_next)
         {  /* obtain pointer to corresponding column */
            col = aij->col;
            /* if there is element with identical indices, it can only
               be found in the beginning of j-th column list */
            if (col->ptr != NULL && col->ptr->row->i == i)
            {  for (k = 1; k <= ne; k++)
                  if (ia[k] == i && ja[k] == col->j) break;
               xerror("glp_load_mat: ia[%d] = %d; ja[%d] = %d; duplicat"
                  "e indices not allowed\n", k, i, k, col->j);
            }
            /* add the element to the beginning of j-th column list */
            aij->c_prev = NULL;
            aij->c_next = col->ptr;
            if (aij->c_next != NULL) aij->c_next->c_prev = aij;
            col->ptr = aij;
         }
      }
      /* remove zero elements from the constraint matrix */
      for (i = 1; i <= lp->m; i++)
      {  row = lp->row[i];
         for (aij = row->ptr; aij != NULL; aij = next)
         {  next = aij->r_next;
            if (aij->val == 0.0)
            {  /* remove the element from the row list */
               if (aij->r_prev == NULL)
                  row->ptr = next;
               else
                  aij->r_prev->r_next = next;
               if (next == NULL)
                  ;