glpssx.h

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

// where N' is a matrix transposed to N, cN is a vector of objective
// coefficients at non-basic variables xN.
----------------------------------------------------------------------*/
      int *stat; /* int stat[1+m+n]; */
      /* stat[0] is not used;
         stat[k], 1 <= k <= m+n, is the status of variable x[k]: */
#define SSX_BS          0     /* basic variable */
#define SSX_NL          1     /* non-basic variable on lower bound */
#define SSX_NU          2     /* non-basic variable on upper bound */
#define SSX_NF          3     /* non-basic free variable */
#define SSX_NS          4     /* non-basic fixed variable */
      int *Q_row; /* int Q_row[1+m+n]; */
      /* matrix Q in row-like format;
         Q_row[0] is not used;
         Q_row[i] = j means that q[i,j] = 1 */
      int *Q_col; /* int Q_col[1+m+n]; */
      /* matrix Q in column-like format;
         Q_col[0] is not used;
         Q_col[j] = i means that q[i,j] = 1 */
      /* if k-th column of the matrix (I | A) is k'-th column of the
         matrix (B | N), then Q_row[k] = k' and Q_col[k'] = k;
         if x[k] is xB[i], then Q_row[k] = i and Q_col[i] = k;
         if x[k] is xN[j], then Q_row[k] = m+j and Q_col[m+j] = k */
      BFX *binv;
      /* invertable form of the basis matrix B */
      mpq_t *bbar; /* mpq_t bbar[1+m]; alias: beta */
      /* bbar[0] is a value of the objective function;
         bbar[i], 1 <= i <= m, is a value of basic variable xB[i] */
      mpq_t *pi; /* mpq_t pi[1+m]; */
      /* pi[0] is not used;
         pi[i], 1 <= i <= m, is a simplex multiplier corresponding to
         i-th row (equality constraint) */
      mpq_t *cbar; /* mpq_t cbar[1+n]; alias: d */
      /* cbar[0] is not used;
         cbar[j], 1 <= j <= n, is a reduced cost of non-basic variable
         xN[j] */
/*----------------------------------------------------------------------
// SIMPLEX TABLE
//
// Due to (8) and (9) the system of equality constraints (7) for the
// current basis can be written as follows:
//
//    xB = A~ * xN,                                                 (14)
//
// where
//
//    A~ = - inv(B) * N                                             (15)
//
// is a mxn matrix called the simplex table.
//
// The revised simplex method uses only two components of A~, namely,
// pivot column corresponding to non-basic variable xN[q] chosen to
// enter the basis, and pivot row corresponding to basic variable xB[p]
// chosen to leave the basis.
//
// Pivot column alfa_q is q-th column of A~, so
//
//    alfa_q = A~ * e[q] = - inv(B) * N * e[q] = - inv(B) * N[q],   (16)
//
// where N[q] is q-th column of the matrix N.
//
// Pivot row alfa_p is p-th row of A~ or, equivalently, p-th column of
// A~', a matrix transposed to A~, so
//
//    alfa_p = A~' * e[p] = - N' * inv(B') * e[p] = - N' * rho_p,   (17)
//
// where (*)' means transposition, and
//
//    rho_p = inv(B') * e[p],                                       (18)
//
// is p-th column of inv(B') or, that is the same, p-th row of inv(B).
----------------------------------------------------------------------*/
      int p;
      /* number of basic variable xB[p], 1 <= p <= m, chosen to leave
         the basis */
      mpq_t *rho; /* mpq_t rho[1+m]; */
      /* p-th row of the inverse inv(B); see (18) */
      mpq_t *ap; /* mpq_t ap[1+n]; */
      /* p-th row of the simplex table; see (17) */
      int q;
      /* number of non-basic variable xN[q], 1 <= q <= n, chosen to
         enter the basis */
      mpq_t *aq; /* mpq_t aq[1+m]; */
      /* q-th column of the simplex table; see (16) */
/*--------------------------------------------------------------------*/
      int q_dir;
      /* direction in which non-basic variable xN[q] should change on
         moving to the adjacent vertex of the polyhedron:
         +1 means that xN[q] increases
         -1 means that xN[q] decreases */
      int p_stat;
      /* non-basic status which should be assigned to basic variable
         xB[p] when it has left the basis and become xN[q] */
      mpq_t delta;
      /* actual change of xN[q] in the adjacent basis (it has the same
         sign as q_dir) */
/*--------------------------------------------------------------------*/
      int it_lim;
      /* simplex iterations limit; if this value is positive, it is
         decreased by one each time when one simplex iteration has been
         performed, and reaching zero value signals the solver to stop
         the search; negative value means no iterations limit */
      int it_cnt;
      /* simplex iterations count; this count is increased by one each
         time when one simplex iteration has been performed */
      double tm_lim;
      /* searching time limit, in seconds; if this value is positive,
         it is decreased each time when one simplex iteration has been
         performed by the amount of time spent for the iteration, and
         reaching zero value signals the solver to stop the search;
         negative value means no time limit */
      double out_frq;
      /* output frequency, in seconds; this parameter specifies how
         frequently the solver sends information about the progress of
         the search to the standard output */
      xlong_t tm_beg;
      /* starting time of the search, in seconds; the total time of the
         search is the difference between xtime() and tm_beg */
      xlong_t tm_lag;
      /* the most recent time, in seconds, at which the progress of the
         the search was displayed */
};

#define ssx_create            _glp_ssx_create
#define ssx_factorize         _glp_ssx_factorize
#define ssx_get_xNj           _glp_ssx_get_xNj
#define ssx_eval_bbar         _glp_ssx_eval_bbar
#define ssx_eval_pi           _glp_ssx_eval_pi
#define ssx_eval_dj           _glp_ssx_eval_dj
#define ssx_eval_cbar         _glp_ssx_eval_cbar
#define ssx_eval_rho          _glp_ssx_eval_rho
#define ssx_eval_row          _glp_ssx_eval_row
#define ssx_eval_col          _glp_ssx_eval_col
#define ssx_chuzc             _glp_ssx_chuzc
#define ssx_chuzr             _glp_ssx_chuzr
#define ssx_update_bbar       _glp_ssx_update_bbar
#define ssx_update_pi         _glp_ssx_update_pi
#define ssx_update_cbar       _glp_ssx_update_cbar
#define ssx_change_basis      _glp_ssx_change_basis
#define ssx_delete            _glp_ssx_delete

#define ssx_phase_I           _glp_ssx_phase_I
#define ssx_phase_II          _glp_ssx_phase_II
#define ssx_driver            _glp_ssx_driver

SSX *ssx_create(int m, int n, int nnz);
/* create simplex solver workspace */

int ssx_factorize(SSX *ssx);
/* factorize the current basis matrix */

void ssx_get_xNj(SSX *ssx, int j, mpq_t x);
/* determine value of non-basic variable */

void ssx_eval_bbar(SSX *ssx);
/* compute values of basic variables */

void ssx_eval_pi(SSX *ssx);
/* compute values of simplex multipliers */

void ssx_eval_dj(SSX *ssx, int j, mpq_t dj);
/* compute reduced cost of non-basic variable */

void ssx_eval_cbar(SSX *ssx);
/* compute reduced costs of all non-basic variables */

void ssx_eval_rho(SSX *ssx);
/* compute p-th row of the inverse */

void ssx_eval_row(SSX *ssx);
/* compute pivot row of the simplex table */

void ssx_eval_col(SSX *ssx);
/* compute pivot column of the simplex table */

void ssx_chuzc(SSX *ssx);
/* choose pivot column */

void ssx_chuzr(SSX *ssx);
/* choose pivot row */

void ssx_update_bbar(SSX *ssx);
/* update values of basic variables */

void ssx_update_pi(SSX *ssx);
/* update simplex multipliers */

void ssx_update_cbar(SSX *ssx);
/* update reduced costs of non-basic variables */

void ssx_change_basis(SSX *ssx);
/* change current basis to adjacent one */

void ssx_delete(SSX *ssx);
/* delete simplex solver workspace */

int ssx_phase_I(SSX *ssx);
/* find primal feasible solution */

int ssx_phase_II(SSX *ssx);
/* find optimal solution */

int ssx_driver(SSX *ssx);
/* base driver to exact simplex method */

#endif

/* eof */