cplex.c

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

/* cplex.c (CPLEX-like interface to GLPK API) */

/***********************************************************************
*  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 <stdarg.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <glpk.h>
#include "cplex.h"

struct CPXENV
{     /* environment block */
      CPXLP *list;
      /* linked list of problem objects */
      int *intparam; /* int intparam[]; */
      /* integer control parameters */
      double *dblparam; /* double dblparam[]; */
      /* floating-point control parameters */
};

struct CPXLP
{     /* problem object */
      CPXENV *env;
      /* pointer to environment block */
      glp_prob *prob;
      /* pointer to underlying GLPK problem object */
      int rflen;
      /* length of the array rflag */
      char *rflag; /* char rflag[rflen]; */
      /* rflag[i], i = 0,...,nrows-1, is a flag of i-th row: */
#define RF_NOT_RANGED   0  /* not ranged */
#define RF_RANGED_POS   1  /* ranged, RHS = lower bound */
#define RF_RANGED_NEG   2  /* ranged, RHS = upper bound */
      int stat;
      /* solution status reported by CPXgetstat; zero means no solution
         exists */
      int meth;
      /* method indicator reported by CPXgetmethod */
      int iwlen;
      /* length of the working array */
      int *iwork; /* int iwork[iwlen] */
      /* working array initialized by binary zeros */
      CPXLP *link;
      /* pointer to another problem object */
};

struct intparam
{     int which;
      int defv;
      int minv;
      int maxv;
};

struct dblparam
{     int which;
      double defv;
      double minv;
      double maxv;
};

struct errstring
{     int code;
      const char *string;
};

#define BIGINT 2100000000
#define BIGDBL 1e75

static const struct intparam intparam[] =
{     {CPX_PARAM_ADVIND, 0, 0, 2},
      {CPX_PARAM_AGGIND, -1, -1, BIGINT},
      {CPX_PARAM_DATACHECK, CPX_OFF, CPX_OFF, CPX_ON},
      {CPX_PARAM_DPRIIND, CPX_DPRIIND_AUTO, CPX_DPRIIND_AUTO,
         CPX_DPRIIND_DEVEX},
      {CPX_PARAM_FASTMIP, CPX_OFF, CPX_OFF, CPX_ON}, /* ??? */
      {CPX_PARAM_ITLIM, BIGINT, 0, BIGINT},
      {CPX_PARAM_PERIND, CPX_OFF, CPX_OFF, CPX_ON},
      {CPX_PARAM_PPRIIND, CPX_PPRIIND_AUTO, CPX_PPRIIND_PARTIAL,
         CPX_PPRIIND_FULL},
      {CPX_PARAM_PREIND, CPX_ON, CPX_OFF, CPX_ON},
      {CPX_PARAM_REINV, 0, 0, 10000},
      {CPX_PARAM_SCRIND, CPX_OFF, CPX_OFF, CPX_ON},
      {CPX_PARAM_SIMDISPLAY, 1, 0, 2},
};

static const struct dblparam dblparam[] =
{     {CPX_PARAM_EPOPT, 1e-6, 1e-9, 1e-1},
      {CPX_PARAM_EPPER, 1e-6, 1e-8, BIGDBL},
      {CPX_PARAM_EPRHS, 1e-6, 1e-9, 1e-1},
      {CPX_PARAM_OBJLLIM, -BIGDBL, -BIGDBL, +BIGDBL},
      {CPX_PARAM_OBJULIM, +BIGDBL, -BIGDBL, +BIGDBL},
};

static const struct errstring errstring[] =
{     {CPXERR_ARRAY_NOT_ASCENDING, "Array entry %d not ascending"},
      {CPXERR_BAD_ARGUMENT, "Invalid argument"},
      {CPXERR_BAD_CTYPE, "Invalid ctype entry %d"},
      {CPXERR_BAD_LUB, "Invalid bound change indicator entry %d"},
      {CPXERR_BAD_PARAM_NUM, "Invalid parameter number"},
      {CPXERR_BAD_SENSE, "Invalid sense entry %d"},
      {CPXERR_BAD_STATUS, "Invalid status entry %d for basis specificat"
         "ion"},
      {CPXERR_COL_INDEX_RANGE, "Column index %d out of range"},
      {CPXERR_COUNT_RANGE, "Count entry %d negative or larger than allo"
         "wed"},
      {CPXERR_DUP_ENTRY, "Duplicate entry"},
      {CPXERR_INDEX_RANGE, "Index is outside range of valid values"},
      {CPXERR_NEGATIVE_SURPLUS, "Insufficient array length"},
      {CPXERR_NO_BASIC_SOLN, "No basic solution exists"},
      {CPXERR_NO_ENVIRONMENT, "No environment exists"},
      {CPXERR_NO_MEMORY, "Out of memory"},
      {CPXERR_NO_PROBLEM, "No problem exists"},
      {CPXERR_NO_SOLN, "No solution exists"},
      {CPXERR_NOT_FIXED, "Only fixed variables are pivoted out"},
      {CPXERR_NULL_NAME, "Null pointer %d in name array"},
      {CPXERR_NULL_POINTER, "Null pointer for required data"},
      {CPXERR_PARAM_TOO_BIG, "Parameter value too big"},
      {CPXERR_PARAM_TOO_SMALL, "Parameter value too small"},
      {CPXERR_ROW_INDEX_RANGE, "Row index %d out of range"},
};

/**********************************************************************/

#define xassert(expr) \
      ((void)((expr) || (_xassert(#expr, __FILE__, __LINE__), 1)))

static void _xassert(const char *expr, const char *file, int line)
{     printf("Assertion failed: %s\n", expr);
      printf("Error detected in file %s at line %d\n", file, line);
      exit(EXIT_FAILURE);
      /* no return */
}

static int findintparam(int whichparam)
{     int k, card;
      card = sizeof(intparam) / sizeof(struct intparam);
      for (k = 0; k < card; k++)
         if (intparam[k].which == whichparam) return k;
      return -1;
}

static int getintparam(CPXENV *env, int whichparam)
{     int k;
      xassert(env != NULL);
      k = findintparam(whichparam);
      xassert(k >= 0);
      return env->intparam[k];
}

static int finddblparam(int whichparam)
{     int k, card;
      card = sizeof(dblparam) / sizeof(struct dblparam);
      for (k = 0; k < card; k++)
         if (dblparam[k].which == whichparam) return k;
      return -1;
}

static double getdblparam(CPXENV *env, int whichparam)
{     int k;
      xassert(env != NULL);
      k = finddblparam(whichparam);
      xassert(k >= 0);
      return env->dblparam[k];
}

static const char *finderrstring(int errcode)
{     int k, card;
      card = sizeof(errstring) / sizeof(struct errstring);
      for (k = 0; k < card; k++)
      {  if (errstring[k].code == errcode)
            return errstring[k].string;
      }
      return NULL;
}

static int error(CPXENV *env, int errcode, ...)
{     va_list arg;
      char buffer[510];
      xassert(env != NULL);
      if (getintparam(env, CPX_PARAM_SCRIND) == CPX_ON)
      {  xassert(CPXgeterrorstring(env, errcode, buffer) == buffer);
         va_start(arg, errcode);
         vprintf(buffer, arg);
         va_end(arg);
      }
      return errcode;
}

static int checkenv(CPXENV *env)
{     int errcode;
      if (env == NULL)
         errcode = CPXERR_NO_ENVIRONMENT;
      else
         errcode = 0;
      return errcode;
}

static checklp(CPXENV *env, CPXLP *lp)
{     int errcode;
      errcode = checkenv(env);
      if (errcode) goto done;
      if (lp == NULL)
         errcode = error(env, CPXERR_NO_PROBLEM);
done: return errcode;
}

static void invalidate(CPXLP *lp)
{     lp->stat = 0;
      lp->meth = CPX_ALG_NONE;
      return;
}

static void enlargerflag(CPXLP *lp)
{     int m;
      xassert(lp != NULL);
      m = glp_get_num_rows(lp->prob);
      if (lp->rflen < m)
      {  int rflen = lp->rflen;
         char *rflag = lp->rflag;
         while (lp->rflen < m)
         {  lp->rflen += lp->rflen;
            xassert(lp->rflen > 0);
         }
         lp->rflag = glp_calloc(lp->rflen, sizeof(char));
         memcpy(lp->rflag, rflag, rflen);
         glp_free(rflag);
      }
      return;
}

static void enlargeiwork(CPXLP *lp, int len)
{     xassert(len >= 0);
      if (lp->iwlen < len)
      {  glp_free(lp->iwork);
         while (lp->iwlen < len)
         {  lp->iwlen += lp->iwlen;
            xassert(lp->iwlen > 0);
         }
         lp->iwork = glp_calloc(lp->iwlen, sizeof(int));
         memset(lp->iwork, 0, lp->iwlen * sizeof(int));
      }
      return;
}

/**********************************************************************/

int CPXaddcols(CPXENV *env, CPXLP *lp, int ccnt, int nzcnt,
      const double obj[], const int cmatbeg[], const int cmatind[],
      const double cmatval[], const double lb[], const double ub[],
      char *colname[])
{     int j, k, m, n, beg, end, type, errcode;
      double lbnd, ubnd;
      errcode = checklp(env, lp);
      if (errcode) goto done;
      if (ccnt < 0 || nzcnt < 0)
      {  errcode = error(env, CPXERR_BAD_ARGUMENT);
         goto done;
      }
      if (ccnt > 0)
      {  if (cmatbeg == NULL || cmatind == NULL || cmatval == NULL)
         {  errcode = error(env, CPXERR_NULL_POINTER);
            goto done;
         }
      }
      m = glp_get_num_rows(lp->prob);
      n = glp_get_num_cols(lp->prob);
      enlargeiwork(lp, m);
      for (j = 0; j < ccnt; j++)
      {  beg = cmatbeg[j];
         if (j > 0 && !(cmatbeg[j-1] <= beg))
         {  errcode = error(env, CPXERR_ARRAY_NOT_ASCENDING, j);
            goto done;
         }
         if (!(0 <= beg && beg <= nzcnt))
         {  errcode = error(env, CPXERR_INDEX_RANGE);
            goto done;
         }
         end = (j < ccnt-1 ? cmatbeg[j+1] : nzcnt);
         for (k = beg; k < end; k++)
         {  if (!(0 <= cmatind[k] && cmatind[k] < m))
            {  errcode = error(env, CPXERR_ROW_INDEX_RANGE, k);
               goto done;
            }
         }
         errcode = 0;
         for (k = beg; k < end; k++)
         {  if (lp->iwork[cmatind[k]])
            {  errcode = error(env, CPXERR_DUP_ENTRY);
               break;
            }
            lp->iwork[cmatind[k]] = 1;
         }
         for (k = beg; k < end; k++)
            lp->iwork[cmatind[k]] = 0;
         if (errcode) goto done;
         if (colname != NULL)
         {  if (colname[j] == NULL)
            {  errcode = error(env, CPXERR_NULL_NAME, j);
               goto done;
            }
         }
      }
      errcode = 0;
      invalidate(lp);
      if (ccnt > 0)
         glp_add_cols(lp->prob, ccnt);
      for (j = 0; j < ccnt; j++)
      {  if (colname != NULL)
            glp_set_col_name(lp->prob, n+j+1, colname[j]);
         lbnd = (lb == NULL ? 0.0 : lb[j]);
         ubnd = (ub == NULL ? +CPX_INFBOUND : ub[j]);
         if (lbnd <= -CPX_INFBOUND && ubnd >= +CPX_INFBOUND)
            type = GLP_FR;
         else if (ubnd >= +CPX_INFBOUND)
            type = GLP_LO;
         else if (lbnd <= -CPX_INFBOUND)
            type = GLP_UP;
         else if (lbnd != ubnd)
            type = GLP_DB;
         else
            type = GLP_FX;
         glp_set_col_bnds(lp->prob, n+j+1, type, lbnd, ubnd);
         if (obj != NULL)
            glp_set_obj_coef(lp->prob, n+j+1, obj[j]);
         beg = cmatbeg[j];
         end = (j < ccnt-1 ? cmatbeg[j+1] : nzcnt);
         for (k = beg; k < end; k++)
            lp->iwork[k-beg] = cmatind[k]+1;
         glp_set_mat_col(lp->prob, n+j+1, end-beg, lp->iwork-1,
            cmatval+beg-1);
         for (k = beg; k < end; k++)
            lp->iwork[k-beg] = 0;
      }
done: return errcode;
}

int CPXaddrows(CPXENV *env, CPXLP *lp, int ccnt, int rcnt, int nzcnt,
      const double rhs[], const char sense[], const int rmatbeg[],
      const int rmatind[], const double rmatval[], char *colname[],
      char *rowname[])
{     int i, j, k, m, n, beg, end, type, errcode;
      double temp;
      errcode = checklp(env, lp);
      if (errcode) goto done;
      if (ccnt < 0 || rcnt < 0 || nzcnt < 0)
      {  errcode = error(env, CPXERR_BAD_ARGUMENT);
         goto done;
      }
      if (rcnt > 0)
      {  if (rmatbeg == NULL || rmatind == NULL || rmatval == NULL)
         {  errcode = error(env, CPXERR_NULL_POINTER);
            goto done;
         }
      }
      m = glp_get_num_rows(lp->prob);
      n = glp_get_num_cols(lp->prob);
      enlargeiwork(lp, n+ccnt);
      for (i = 0; i < rcnt; i++)
      {  if (sense != NULL)
         {  if (!(sense[i] == 'L' || sense[i] == 'E' ||
                  sense[i] == 'G' || sense[i] == 'R'))
            {  errcode = error(env, CPXERR_BAD_SENSE, i);
               goto done;
            }
         }
         beg = rmatbeg[i];
         if (i > 0 && !(rmatbeg[i-1] <= beg))
         {  errcode = error(env, CPXERR_ARRAY_NOT_ASCENDING, i);
            goto done;
         }
         if (!(0 <= beg && beg <= nzcnt))
         {  errcode = error(env, CPXERR_INDEX_RANGE);
            goto done;
         }
         end = (i < rcnt-1 ? rmatbeg[i+1] : nzcnt);
         for (k = beg; k < end; k++)
         {  if (!(0 <= rmatind[k] && rmatind[k] < n+ccnt))
            {  errcode = error(env, CPXERR_COL_INDEX_RANGE, k);
               goto done;
            }
         }
         errcode = 0;
         for (k = beg; k < end; k++)
         {  if (lp->iwork[rmatind[k]])
            {  errcode = error(env, CPXERR_DUP_ENTRY);
               break;
            }
            lp->iwork[rmatind[k]] = 1;
         }
         for (k = beg; k < end; k++)
            lp->iwork[rmatind[k]] = 0;
         if (errcode) goto done;
         if (rowname != NULL)
         {  if (rowname[i] == NULL)
            {  errcode = error(env, CPXERR_NULL_NAME, i);
               goto done;
            }
         }
      }
      for (j = 0; j < ccnt; j++)
      {  if (colname != NULL)
         {  if (colname[j] == NULL)
            {  errcode = error(env, CPXERR_NULL_NAME, j);
               goto done;
            }
         }
      }
      errcode = 0;
      invalidate(lp);
      if (rcnt > 0)
         glp_add_rows(lp->prob, rcnt);
      if (ccnt > 0)
         glp_add_cols(lp->prob, ccnt);
      enlargerflag(lp);
      for (i = 0; i < rcnt; i++)
      {  if (rowname != NULL)
            glp_set_row_name(lp->prob, m+i+1, rowname[i]);
         temp = (rhs == NULL ? 0.0 : rhs[i]);
         if (sense == NULL || sense[i] == 'E')
         {  lp->rflag[m+i] = RF_NOT_RANGED;
            type = GLP_FX;
         }
         else if (sense[i] == 'L')