glpapi01.c

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

/* glpapi01.c (problem creating and modifying routines) */

/***********************************************************************
*  This code is part of GLPK (GNU Linear Programming Kit).
*
*  Copyright (C) 2000,01,02,03,04,05,06,07,08,2009 Andrew Makhorin,
*  Department for Applied Informatics, Moscow Aviation Institute,
*  Moscow, Russia. All rights reserved. E-mail: <[e-mail]>.
*
*  GLPK is free software: you can redistribute it and/or modify it
*  under the terms of the GNU General Public License as published by
*  the Free Software Foundation, either version 3 of the License, or
*  (at your option) any later version.
*
*  GLPK is distributed in the hope that it will be useful, but WITHOUT
*  ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
*  or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public
*  License for more details.
*
*  You should have received a copy of the GNU General Public License
*  along with GLPK. If not, see <http://www.gnu.org/licenses/>.
***********************************************************************/

#include "glpios.h"

/* CAUTION: DO NOT CHANGE THE LIMITS BELOW */

#define M_MAX 100000000 /* = 100*10^6 */
/* maximal number of rows in the problem object */

#define N_MAX 100000000 /* = 100*10^6 */
/* maximal number of columns in the problem object */

#define NNZ_MAX 500000000 /* = 500*10^6 */
/* maximal number of constraint coefficients in the problem object */

/***********************************************************************
*  NAME
*
*  glp_create_prob - create problem object
*
*  SYNOPSIS
*
*  glp_prob *glp_create_prob(void);
*
*  DESCRIPTION
*
*  The routine glp_create_prob creates a new problem object, which is
*  initially "empty", i.e. has no rows and columns.
*
*  RETURNS
*
*  The routine returns a pointer to the object created, which should be
*  used in any subsequent operations on this object. */

static void create_prob(glp_prob *lp)
{     lp->pool = dmp_create_pool();
      lp->cps = xmalloc(sizeof(struct LPXCPS));
      lpx_reset_parms(lp);
      lp->tree = NULL;
      lp->lwa = 0;
      lp->cwa = NULL;
      /* LP/MIP data */
      lp->name = NULL;
      lp->obj = NULL;
      lp->dir = GLP_MIN;
      lp->c0 = 0.0;
      lp->m_max = 100;
      lp->n_max = 200;
      lp->m = lp->n = 0;
      lp->nnz = 0;
      lp->row = xcalloc(1+lp->m_max, sizeof(GLPROW *));
      lp->col = xcalloc(1+lp->n_max, sizeof(GLPCOL *));
      lp->r_tree = lp->c_tree = NULL;
      /* basis factorization */
      lp->valid = 0;
      lp->head = xcalloc(1+lp->m_max, sizeof(int));
      lp->bfcp = NULL;
      lp->bfd = NULL;
      /* basic solution (LP) */
      lp->pbs_stat = lp->dbs_stat = GLP_UNDEF;
      lp->obj_val = 0.0;
      lp->it_cnt = 0;
      lp->some = 0;
      /* interior-point solution (LP) */
      lp->ipt_stat = GLP_UNDEF;
      lp->ipt_obj = 0.0;
      /* integer solution (MIP) */
      lp->mip_stat = GLP_UNDEF;
      lp->mip_obj = 0.0;
      return;
}

glp_prob *glp_create_prob(void)
{     glp_prob *lp;
      lp = xmalloc(sizeof(glp_prob));
      create_prob(lp);
      return lp;
}

/***********************************************************************
*  NAME
*
*  glp_set_prob_name - assign (change) problem name
*
*  SYNOPSIS
*
*  void glp_set_prob_name(glp_prob *lp, const char *name);
*
*  DESCRIPTION
*
*  The routine glp_set_prob_name assigns a given symbolic name (1 up to
*  255 characters) to the specified problem object.
*
*  If the parameter name is NULL or empty string, the routine erases an
*  existing symbolic name of the problem object. */

void glp_set_prob_name(glp_prob *lp, const char *name)
{     glp_tree *tree = lp->tree;
      if (tree != NULL && tree->reason != 0)
         xerror("glp_set_prob_name: operation not allowed\n");
      if (lp->name != NULL)
      {  dmp_free_atom(lp->pool, lp->name, strlen(lp->name)+1);
         lp->name = NULL;
      }
      if (!(name == NULL || name[0] == '\0'))
      {  int k;
         for (k = 0; name[k] != '\0'; k++)
         {  if (k == 256)
               xerror("glp_set_prob_name: problem name too long\n");
            if (iscntrl((unsigned char)name[k]))
               xerror("glp_set_prob_name: problem name contains invalid"
                  " character(s)\n");
         }
         lp->name = dmp_get_atom(lp->pool, strlen(name)+1);
         strcpy(lp->name, name);
      }
      return;
}

/***********************************************************************
*  NAME
*
*  glp_set_obj_name - assign (change) objective function name
*
*  SYNOPSIS
*
*  void glp_set_obj_name(glp_prob *lp, const char *name);
*
*  DESCRIPTION
*
*  The routine glp_set_obj_name assigns a given symbolic name (1 up to
*  255 characters) to the objective function of the specified problem
*  object.
*
*  If the parameter name is NULL or empty string, the routine erases an
*  existing name of the objective function. */

void glp_set_obj_name(glp_prob *lp, const char *name)
{     glp_tree *tree = lp->tree;
      if (tree != NULL && tree->reason != 0)
         xerror("glp_set_obj_name: operation not allowed\n");
     if (lp->obj != NULL)
      {  dmp_free_atom(lp->pool, lp->obj, strlen(lp->obj)+1);
         lp->obj = NULL;
      }
      if (!(name == NULL || name[0] == '\0'))
      {  int k;
         for (k = 0; name[k] != '\0'; k++)
         {  if (k == 256)
               xerror("glp_set_obj_name: objective name too long\n");
            if (iscntrl((unsigned char)name[k]))
               xerror("glp_set_obj_name: objective name contains invali"
                  "d character(s)\n");
         }
         lp->obj = dmp_get_atom(lp->pool, strlen(name)+1);
         strcpy(lp->obj, name);
      }
      return;
}

/***********************************************************************
*  NAME
*
*  glp_set_obj_dir - set (change) optimization direction flag
*
*  SYNOPSIS
*
*  void glp_set_obj_dir(glp_prob *lp, int dir);
*
*  DESCRIPTION
*
*  The routine glp_set_obj_dir sets (changes) optimization direction
*  flag (i.e. "sense" of the objective function) as specified by the
*  parameter dir:
*
*  GLP_MIN - minimization;
*  GLP_MAX - maximization. */

void glp_set_obj_dir(glp_prob *lp, int dir)
{     glp_tree *tree = lp->tree;
      if (tree != NULL && tree->reason != 0)
         xerror("glp_set_obj_dir: operation not allowed\n");
     if (!(dir == GLP_MIN || dir == GLP_MAX))
         xerror("glp_set_obj_dir: dir = %d; invalid direction flag\n",
            dir);
      lp->dir = dir;
      return;
}

/***********************************************************************
*  NAME
*
*  glp_add_rows - add new rows to problem object
*
*  SYNOPSIS
*
*  int glp_add_rows(glp_prob *lp, int nrs);
*
*  DESCRIPTION
*
*  The routine glp_add_rows adds nrs rows (constraints) to the specified
*  problem object. New rows are always added to the end of the row list,
*  so the ordinal numbers of existing rows remain unchanged.
*
*  Being added each new row is initially free (unbounded) and has empty
*  list of the constraint coefficients.
*
*  RETURNS
*
*  The routine glp_add_rows returns the ordinal number of the first new
*  row added to the problem object. */

int glp_add_rows(glp_prob *lp, int nrs)
{     glp_tree *tree = lp->tree;
      GLPROW *row;
      int m_new, i;
      /* determine new number of rows */
      if (nrs < 1)
         xerror("glp_add_rows: nrs = %d; invalid number of rows\n",
            nrs);
      if (nrs > M_MAX - lp->m)
         xerror("glp_add_rows: nrs = %d; too many rows\n", nrs);
      m_new = lp->m + nrs;
      /* increase the room, if necessary */
      if (lp->m_max < m_new)
      {  GLPROW **save = lp->row;
         while (lp->m_max < m_new)
         {  lp->m_max += lp->m_max;
            xassert(lp->m_max > 0);
         }
         lp->row = xcalloc(1+lp->m_max, sizeof(GLPROW *));
         memcpy(&lp->row[1], &save[1], lp->m * sizeof(GLPROW *));
         xfree(save);
         /* do not forget about the basis header */
         xfree(lp->head);
         lp->head = xcalloc(1+lp->m_max, sizeof(int));
      }
      /* add new rows to the end of the row list */
      for (i = lp->m+1; i <= m_new; i++)
      {  /* create row descriptor */
         lp->row[i] = row = dmp_get_atom(lp->pool, sizeof(GLPROW));
         row->i = i;
         row->name = NULL;
         row->node = NULL;
#if 1 /* 20/IX-2008 */
         row->level = 0;
         row->origin = 0;
         row->klass = 0;
         if (tree != NULL)
         {  switch (tree->reason)
            {  case 0:
                  break;
               case GLP_IROWGEN:
                  xassert(tree->curr != NULL);
                  row->level = tree->curr->level;
                  row->origin = GLP_RF_LAZY;
                  break;
               case GLP_ICUTGEN:
                  xassert(tree->curr != NULL);
                  row->level = tree->curr->level;
                  row->origin = GLP_RF_CUT;
                  break;
               default:
                  xassert(tree != tree);
            }
         }
#endif
         row->type = GLP_FR;
         row->lb = row->ub = 0.0;
         row->ptr = NULL;
         row->rii = 1.0;
         row->stat = GLP_BS;
#if 0
         row->bind = -1;
#else
         row->bind = 0;
#endif
         row->prim = row->dual = 0.0;
         row->pval = row->dval = 0.0;
         row->mipx = 0.0;
      }
      /* set new number of rows */
      lp->m = m_new;
      /* invalidate the basis factorization */
      lp->valid = 0;
#if 1
      if (tree != NULL && tree->reason != 0) tree->reopt = 1;
#endif
      /* return the ordinal number of the first row added */
      return m_new - nrs + 1;
}

/***********************************************************************
*  NAME
*
*  glp_add_cols - add new columns to problem object
*
*  SYNOPSIS
*
*  int glp_add_cols(glp_prob *lp, int ncs);
*
*  DESCRIPTION
*
*  The routine glp_add_cols adds ncs columns (structural variables) to
*  the specified problem object. New columns are always added to the end
*  of the column list, so the ordinal numbers of existing columns remain
*  unchanged.
*
*  Being added each new column is initially fixed at zero and has empty
*  list of the constraint coefficients.
*
*  RETURNS
*
*  The routine glp_add_cols returns the ordinal number of the first new
*  column added to the problem object. */

int glp_add_cols(glp_prob *lp, int ncs)
{     glp_tree *tree = lp->tree;
      GLPCOL *col;
      int n_new, j;
      if (tree != NULL && tree->reason != 0)
         xerror("glp_add_cols: operation not allowed\n");
      /* determine new number of columns */
      if (ncs < 1)
         xerror("glp_add_cols: ncs = %d; invalid number of columns\n",
            ncs);