glpssx.h

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

/* glpssx.h (simplex method, bignum arithmetic) */

/***********************************************************************
*  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/>.
***********************************************************************/

#ifndef _GLPSSX_H
#define _GLPSSX_H

#include "glpbfx.h"
#include "glplib.h"

typedef struct SSX SSX;

struct SSX
{     /* simplex solver workspace */
/*----------------------------------------------------------------------
// LP PROBLEM DATA
//
// It is assumed that LP problem has the following statement:
//
//    minimize (or maximize)
//
//       z = c[1]*x[1] + ... + c[m+n]*x[m+n] + c[0]                  (1)
//
//    subject to equality constraints
//
//       x[1] - a[1,1]*x[m+1] - ... - a[1,n]*x[m+n] = 0
//
//          .  .  .  .  .  .  .                                      (2)
//
//       x[m] - a[m,1]*x[m+1] + ... - a[m,n]*x[m+n] = 0
//
//    and bounds of variables
//
//         l[1] <= x[1]   <= u[1]
//
//          .  .  .  .  .  .  .                                      (3)
//
//       l[m+n] <= x[m+n] <= u[m+n]
//
// where:
// x[1], ..., x[m]      - auxiliary variables;
// x[m+1], ..., x[m+n]  - structural variables;
// z                    - objective function;
// c[1], ..., c[m+n]    - coefficients of the objective function;
// c[0]                 - constant term of the objective function;
// a[1,1], ..., a[m,n]  - constraint coefficients;
// l[1], ..., l[m+n]    - lower bounds of variables;
// u[1], ..., u[m+n]    - upper bounds of variables.
//
// Bounds of variables can be finite as well as inifinite. Besides,
// lower and upper bounds can be equal to each other. So the following
// five types of variables are possible:
//
//    Bounds of variable      Type of variable
//    -------------------------------------------------
//    -inf <  x[k] <  +inf    Free (unbounded) variable
//    l[k] <= x[k] <  +inf    Variable with lower bound
//    -inf <  x[k] <= u[k]    Variable with upper bound
//    l[k] <= x[k] <= u[k]    Double-bounded variable
//    l[k] =  x[k] =  u[k]    Fixed variable
//
// Using vector-matrix notations the LP problem (1)-(3) can be written
// as follows:
//
//    minimize (or maximize)
//
//       z = c * x + c[0]                                            (4)
//
//    subject to equality constraints
//
//       xR - A * xS = 0                                             (5)
//
//    and bounds of variables
//
//       l <= x <= u                                                 (6)
//
// where:
// xR                   - vector of auxiliary variables;
// xS                   - vector of structural variables;
// x = (xR, xS)         - vector of all variables;
// z                    - objective function;
// c                    - vector of objective coefficients;
// c[0]                 - constant term of the objective function;
// A                    - matrix of constraint coefficients (has m rows
//                        and n columns);
// l                    - vector of lower bounds of variables;
// u                    - vector of upper bounds of variables.
//
// The simplex method makes no difference between auxiliary and
// structural variables, so it is convenient to think the system of
// equality constraints (5) written in a homogeneous form:
//
//    (I | -A) * x = 0,                                              (7)
//
// where (I | -A) is an augmented (m+n)xm constraint matrix, I is mxm
// unity matrix whose columns correspond to auxiliary variables, and A
// is the original mxn constraint matrix whose columns correspond to
// structural variables. Note that only the matrix A is stored.
----------------------------------------------------------------------*/
      int m;
      /* number of rows (auxiliary variables), m > 0 */
      int n;
      /* number of columns (structural variables), n > 0 */
      int *type; /* int type[1+m+n]; */
      /* type[0] is not used;
         type[k], 1 <= k <= m+n, is the type of variable x[k]: */
#define SSX_FR          0     /* free (unbounded) variable */
#define SSX_LO          1     /* variable with lower bound */
#define SSX_UP          2     /* variable with upper bound */
#define SSX_DB          3     /* double-bounded variable */
#define SSX_FX          4     /* fixed variable */
      mpq_t *lb; /* mpq_t lb[1+m+n]; alias: l */
      /* lb[0] is not used;
         lb[k], 1 <= k <= m+n, is an lower bound of variable x[k];
         if x[k] has no lower bound, lb[k] is zero */
      mpq_t *ub; /* mpq_t ub[1+m+n]; alias: u */
      /* ub[0] is not used;
         ub[k], 1 <= k <= m+n, is an upper bound of variable x[k];
         if x[k] has no upper bound, ub[k] is zero;
         if x[k] is of fixed type, ub[k] is equal to lb[k] */
      int dir;
      /* optimization direction (sense of the objective function): */
#define SSX_MIN         0     /* minimization */
#define SSX_MAX         1     /* maximization */
      mpq_t *coef; /* mpq_t coef[1+m+n]; alias: c */
      /* coef[0] is a constant term of the objective function;
         coef[k], 1 <= k <= m+n, is a coefficient of the objective
         function at variable x[k];
         note that auxiliary variables also may have non-zero objective
         coefficients */
      int *A_ptr; /* int A_ptr[1+n+1]; */
      int *A_ind; /* int A_ind[A_ptr[n+1]]; */
      mpq_t *A_val; /* mpq_t A_val[A_ptr[n+1]]; */
      /* constraint matrix A (see (5)) in storage-by-columns format */
/*----------------------------------------------------------------------
// LP BASIS AND CURRENT BASIC SOLUTION
//
// The LP basis is defined by the following partition of the augmented
// constraint matrix (7):
//
//    (B | N) = (I | -A) * Q,                                        (8)
//
// where B is a mxm non-singular basis matrix whose columns correspond
// to basic variables xB, N is a mxn matrix whose columns correspond to
// non-basic variables xN, and Q is a permutation (m+n)x(m+n) matrix.
//
// From (7) and (8) it follows that
//
//    (I | -A) * x = (I | -A) * Q * Q' * x = (B | N) * (xB, xN),
//
// therefore
//
//    (xB, xN) = Q' * x,                                             (9)
//
// where x is the vector of all variables in the original order, xB is
// a vector of basic variables, xN is a vector of non-basic variables,
// Q' = inv(Q) is a matrix transposed to Q.
//
// Current values of non-basic variables xN[j], j = 1, ..., n, are not
// stored; they are defined implicitly by their statuses as follows:
//
//    0,             if xN[j] is free variable
//    lN[j],         if xN[j] is on its lower bound                 (10)
//    uN[j],         if xN[j] is on its upper bound
//    lN[j] = uN[j], if xN[j] is fixed variable
//
// where lN[j] and uN[j] are lower and upper bounds of xN[j].
//
// Current values of basic variables xB[i], i = 1, ..., m, are computed
// as follows:
//
//    beta = - inv(B) * N * xN,                                     (11)
//
// where current values of xN are defined by (10).
//
// Current values of simplex multipliers pi[i], i = 1, ..., m (which
// are values of Lagrange multipliers for equality constraints (7) also
// called shadow prices) are computed as follows:
//
//    pi = inv(B') * cB,                                            (12)
//
// where B' is a matrix transposed to B, cB is a vector of objective
// coefficients at basic variables xB.
//
// Current values of reduced costs d[j], j = 1, ..., n, (which are
// values of Langrange multipliers for active inequality constraints
// corresponding to non-basic variables) are computed as follows:
//
//    d = cN - N' * pi,                                             (13)
//