/home/coin/SVN-release/Cgl-0.53.1/DyLP/src/Dylp/dylp.h

Go to the documentation of this file.

/*
  This file is a part of the Dylp LP distribution.

        Copyright (C) 2005 -- 2007 Lou Hafer

        School of Computing Science
        Simon Fraser University
        Burnaby, B.C., V5A 1S6, Canada
        lou@cs.sfu.ca

  This code is licensed under the terms of the Common Public License (CPL).
*/

#ifndef _DYLP_H
#define _DYLP_H

/*
  @(#)dylp.h    4.6     10/15/05
  svn/cvs: $Id: dylp.h 218 2008-03-28 15:57:22Z lou $

  This file contains definitions related to dylp, a subroutine library which
  implements a dynamic (primal-dual) linear programming algorithm based on
  the algorithm described by Padberg in Linear Optimisation & Extensions,
  Springer-Verlag, 1995.  dylp also owes a debt to previous and contemporary
  codes the author has worked with --- la05, bandbx, zoom/xmp, ylp, and glpk.

  At minimum, dylp requires only a constraint system. Since it manages a
  dynamically sized private copy of the constraint system while solving the
  LP, there's no point in having the client attach logical variables (they'd
  just get in the way, really).

  dylp will accept a basis specification. This takes the form of a status
  vector giving the status of all variables, and a basis vector specifying
  the active constraints and their associated basic variables. From this
  dylp will construct an initial active problem which consists of exactly
  the given constraints and basic variables, with the logicals for the
  constraints making up the nonbasic partition.

  dylp returns as a solution the simplex termination code, the objective
  value (or related value, appropriate for the termination code), status for
  all variables, the active constraints, and the associated primal and dual
  variables (put a little differently, a basis, the values of the basic
  variables, and the dual variables associated with the active constraints).

  The conditional compilation symbol DYLP_INTERNAL is used to delimit
  definitions that should be considered internal to dylp. Don't define this
  symbol in a client.
*/

#include "dylib_errs.h"
#include "dylib_io.h"
#include "dy_consys.h"

/*
  A few words on notation. Traditional matrix and vector notation for LP
  suffers a bit when limited to ascii text, but it's readable if you're
  familiar with the original. The notation in the comments and code is
  loosely based on Chvatal, "Linear Programming", W.H. Freeman, 1983, which
  the author happens to like.

  A matrix is represented with a capital letter, e.g., B. A vector is
  represented with a small letter, e.g., x. A subscript is given in angle
  brackets, e.g., x<j> for the jth coefficient of x. An individual element of
  a matrix has two subscripts, e.g., a<i,j> for the element in row i, column
  j. Column and row vectors are shown with one subscript, e.g., a<j> for the
  jth column (or row).  Whether the vector is supposed to be a column or a
  row should generally be clear from context. A capital letter in the
  subscript position indicates a set of elements, e.g., x<N> is the non-basic
  variables.

  The inverse of a matrix is denoted inv(*), e.g., the basis inverse,
  inv(B).  The dot product of two vectors is denoted dot(*,*), e.g.,
  dot(c,x), or sometimes just written directly, e.g., cx.

  The system of constraints is assumed to be Ax <= b, with m rows and n
  columns. Once the logical variables (aka slacks and artificials) have been
  added, it becomes Ax = b.  A is the constraint matrix, x is the vector of
  primal variables, and b is the right-hand-side (rhs).  NOTE that the
  convention for indices is NOT the usual one. Logical variables are assigned
  indices 1..m and architectural variables are assigned indices m+1..m+n. It
  makes for more efficient addition/deletion of variables; see dy_consys.h for a
  little more explanation.

  There is an objective function z = cx, where z is the objective value and c
  is the vector of coefficients.  dylp minimises the objective.
  
  The matrix A is partitioned into the set of basic columns B, and the set of
  non-basic columns N (sometimes A<N>). The corresponding partitions of c and
  x are c<B>, x<B>, and c<N>, x<N>.

  Premultiplication by the basis inverse (e.g., inv(B)a<j>) is referred to as
  an `ftran'; postmultiplication (e.g., c<B>inv(B)) as a `btran'.  Quantities
  that have been transformed using the basis inverse are often (but not
  always) renamed as 'barred' quantities.

  The basic primal variables are x<B> = inv(B)b.  The dual variables are y =
  c<B>inv(B).  The jth column of A, premultiplied by inv(B), is abar<j> =
  inv(B)a<j>. The reduced costs are cbar = c<N> - c<B>inv(B)N = c<N>-yN.

  The variable i is used as a row index, j as a column index. Often they will
  represent the entering primal variable (j) and the leaving primal variable
  (i). Be aware that comments are often written as if the leaving primal
  variable x<i> occupies row i of the basis. This simplifies the writing.
  But keep in mind that variable x<i> can occupy an arbitrary row k of the
  basis.
*/

/*
  Termination codes for dy_primal and dy_dual, the top level routines of the
  dylp simplex algorithms. Also used by various internal routines.  Codes
  marked with (*) will never be returned to the client unless dylp has
  failed.

  lpINV         The code is not valid (i.e., not set by an execution of
                dy_primal or dy_dual).

  lpOPTIMAL     The problem has an optimal solution.

  lpUNBOUNDED   The problem is unbounded.

  lpSWING(*)    The problem is pseudo-unbounded: Some primal variable grew
                excessively in a single pivot.

  lpINFEAS      The problem is infeasible.

  lpACCCHK      An accuracy check failed and dylp's internal recovery
                algorithms could not recover the situation.

  lpSTALLED     The problem has been abandoned due to stalling. (We could
                in fact actually be cycling, but that's too much trouble
                to prove.)

  lpITERLIM     The problem has been abandoned because it has exceeded an
                absolute iteration limit.

  lpNOSPACE     The problem has been abandoned because the basis package did
                not have sufficient space to maintain the basis.

  lpLOSTFEAS    Feasibility was lost during simplex execution.

  lpPUNT        The lp has punted because it ran into a pivoting problem.

                The next three codes indicate that we're in the middle of
                attempting a forced transition for error recovery purposes.

  lpFORCEDUAL(*) Force a primal to dual transition.

  lpFORCEPRIMAL(*) Force a dual to primal transition.

  lpFORCEFULL(*) Force all inactive constraints and variables to be loaded.

  lpFATAL       Fatal confusion or error of some sort; covers a multitude
                of sins.

  The dual simplex routine does not have a phase I routine equivalent to
  dy_primal1 for the primal simplex. (In the context of dylp, it expects
  to run after dy_primal has been used to find an initial optimal solution.)

  When using the dual simplex method, internal codes reflect the state of
  the dual problem, but dy_dual makes the usual translation back to the
  primal problem, as:

  Dual          Primal          Rationale
  ----          ------          ---------
  lpUNBOUNDED   lpINFEAS        Standard duality theorem.

  Note that lpSWING always refers to primal variables.
*/

typedef enum { lpFATAL = -1, lpINV = 0,
               lpOPTIMAL, lpUNBOUNDED, lpSWING, lpINFEAS,
               lpACCCHK,
               lpSTALLED, lpITERLIM, lpNOSPACE,
               lpLOSTFEAS, lpPUNT,
               lpFORCEDUAL, lpFORCEPRIMAL, lpFORCEFULL } lpret_enum ;


/*
  Phase codes for dylp

  dyINV         Invalid phase
  dyINIT        Initialisation and setup, including establishing the
                initial set of constraints and variables and crashing the
                first basis.
  dyPRIMAL1     Primal simplex phase I
  dyPRIMAL2     Primal simplex phase II
  dyDUAL        Dual simplex
  dyPURGEVAR    Deactivation of variables.
  dyGENVAR      Generation of new variables (not part of original problem).
  dyADDVAR      Activation of variables.
  dyPURGECON    Deactivation of constraints.
  dyGENCON      Generation of new constraints (not part of original problem).
  dyADDCON      Activation of constraints.
  dyFORCEDUAL   Force dual feasibility (error recovery)
  dyFORCEPRIMAL Force primal feasibility (error recovery)
  dyFORCEFULL   Force activation of the full system (error recovery)
  dyDONE        Execution is finished, for one reason or another.

  It's true that new variables will be added during dyGENCON -- at the least,
  each newly generated constraint will bring with it a logical variable.
  dyGENVAR differs in that it is augmenting some subset of the constraints
  with new variables (classic column generation, for example).

  The main loop states (dyPRIMAL1 -- dyFORCEFULL) must remain a contiguous
  block. dy_dumpstats counts on dyPRIMAL1 and dyFORCEPRIMAL being first and
  last, respectively, in the block.

  dyDONE must remain the last code --- it's used to dimension a statistics
  array that tracks the number of times the main loop states are entered.
*/

typedef enum { dyINV = 0, dyINIT,
               dyPRIMAL1, dyPRIMAL2, dyDUAL,
               dyPURGEVAR, dyGENVAR, dyADDVAR,
               dyPURGECON, dyGENCON, dyADDCON,
               dyFORCEDUAL, dyFORCEPRIMAL, dyFORCEFULL,
               dyDONE } dyphase_enum ;
/*
  General return and error codes.
  
  Used by various routines in dylp.
  No routine
  uses all of these, but there's enough overlap to make one big enum
  convenient.

  dyrINV        Invalid code.

  dyrOK         Whatever it was that was being done was done without incident.
  dyrOPTIMAL    The problem is optimal.
  dyrUNBOUND    The problem is unbounded.
  dyrSWING      The problem is pseudo-unbounded: Some variable grew by an
                excessive amount in a single pivot.
  dyrINFEAS     The problem is infeasible.

  dyrREQCHK     Requests a refactor and accuracy check (triggered by various
                checks for bogus numbers).
  dyrACCCHK     An accuracy check has failed.
  dyrLOSTPFEAS  Primal feasibility has been lost.
  dyrLOSTDFEAS  Dual feasibility has been lost.

  dyrDEGEN      Degeneracy has been discovered, or a degenerate pivot has been
                taken.
  dyrRESELECT   Reselect an incoming variable (after an abortive pivot
                attempt).
  dyrMADPIV     The selected pivot coefficient was (numerically) unstable.
  dyrPUNT       In the context of the dual simplex: the dual simplex has
                decided to punt to the primal simplex phase I, for any of
                several reasons. Generally this is indicative of the relative
                lack of sophistication in the dual simplex.
                In the context of the primal simplex: this indicates that all
                candidates to enter the basis were flagged with a NOPIVOT
                qualifier.

  dyrPATCHED    The basis package managed to factor the basis after patching
                it.
  dyrSINGULAR   The basis package discovered the basis was singular. (Typically
                as a consequence of a pivot gone bad.)
  dyrNUMERIC    The basis package detected unacceptable growth in the basis
                coefficients.
  dyrBSPACE     The basis package ran out of space for the basis
                representation. 
  dyrSTALLED    The LP seems to have stalled (and could possibly be cycling,
                but that's too much trouble to prove); triggered by too many
                iterations with no change in the objective.
  dyrITERLIM    The iteration limit has been exceeded.

  dyrFATAL      Fatal confusion; covers a multitude of sins.

   The specific values assigned to some of the codes in the enum come from
   earlier use of yla05 as the basis package. It's gone, but there's no
   incentive to remove the values.
*/

typedef enum { dyrFATAL = -10, dyrITERLIM, dyrSTALLED,
               dyrBSPACE = -7, dyrSINGULAR = -6, dyrNUMERIC = -5,
               dyrLOSTPFEAS, dyrLOSTDFEAS, dyrDEGEN, dyrMADPIV,
               dyrINV = 0, dyrOK = 1, dyrPATCHED = 2,
               dyrRESELECT, dyrREQCHK, dyrACCCHK, dyrPUNT,
               dyrOPTIMAL, dyrUNBOUND, dyrSWING, dyrINFEAS } dyret_enum ;

/*
  Requests and results for checks and recalculations

  Some symbolic names for requesting and reporting on factoring, accuracy
  checks and primal and dual variable calculations. These originated with la
  Duenna, hence the lad prefix. Interpretation varies subtly from routine to
  routine, so check the parameter notes.

  ladPRIMALCHK  (i) set to request primal accuracy check, Bx<B> = b - Nx<N>,
                (o) set to indicate failure of check
  ladDUALCHK    (i) set to to request dual accuracy check, yB = c<B>
                (o) set to indicate failure of check
  ladPRIMFEAS   (i) set to request primal feasibility check (primal variables
                    within bounds)
                (o) set to indicate loss of primal feasibility
  ladDUALFEAS   (i) set to request dual feasibility check (reduced costs of
                    proper sign)
                (o) set to indicate loss of dual feasibility
  ladPFQUIET    (i) set to suppress warnings about variables which are not
                    primal feasible
  ladDFQUIET    (i) set to suppress warnings about variables which are not
                    dual feasible
  ladDUALS      (i) set to request calculation of the dual variables and
                    gradient vector
                (o) set to indicate calculation of the dual variables and
                    gradient vector
  ladPRIMALS    (i) set to request calculation of the primal variables
                (o) set to indicate calculation of the primal variables
  ladFACTOR     (i) set to indicate the basis should be refactored
                (o) set to indicate the basis has been factored
  ladEXPAND     (i) set to force expansion of the space allocated for the
                    basis representation
                (o) set to indicate the space allocated for the basis was
                    increased
*/

#define ladPRIMFEAS     1<<0
#define ladPRIMALCHK    1<<1
#define ladPFQUIET      1<<2
#define ladDUALFEAS     1<<3
#define ladDUALCHK      1<<4
#define ladDFQUIET      1<<5
#define ladDUALS        1<<6
#define ladPRIMALS      1<<7
#define ladFACTOR       1<<8
#define ladEXPAND       1<<9



/*
  Variable status codes

  dylp keeps explicit status for both basic and nonbasic variables. These are
  set up as flags so that it's easy to test when more than one status will do
  for a particular action.

  vstatBFX      basic, fixed
  vstatBUUB     basic, above upper bound
  vstatBUB      basic, at upper bound
  vstatB        basic, strictly between bounds (a well-behaved basic variable)
  vstatBLB      basic, at lower bound
  vstatBLLB     basic, below lower bound
  vstatBFR      basic, free (unbounded)

  vstatNBFX     nonbasic, fixed
  vstatNBUB     nonbasic at upper bound
  vstatNBLB     nonbasic at lower bound
  vstatNBFR     nonbasic free

  vstatSB       superbasic, within bounds

  dylp ensures that superbasic variables are, in fact, always strictly within
  bounds.

  Inactive NBFR variables can be created at startup if dylp is working with a
  partial system and there are free variables that are not selected to be in
  the initial basis. If the client is forcing a full system, these will be
  active NBFR variables.  Error recovery may also create active NBFR
  variables. By convention, NBFR variables always have a value of zero.

  Inactive SB variables should not occur. SB status occurs only as the result
  of error recovery and is only valid in primal simplex.

  The value of SB variables is lost when they are reported out as part of a
  solution. This will only happen if dylp could not find an optimal solution.

  The following qualifiers can be added to the status:

  vstatNOPIVOT  Prevents the variable from being considered as a candidate
                for pivoting; used by the pivot rejection machinery.
  vstatNOPER    Prevents the variable from being perturbed during the
                formation of a restricted subproblem.
  vstatNOLOAD   Prevents the variable from being considered for activation;
                used by startup and variable activation/deactivation routines.
*/

#define vstatINV     0
#define vstatBFX  1<<0
#define vstatBUB  1<<1
#define vstatB    1<<2
#define vstatBLB  1<<3
#define vstatBFR  1<<4
#define vstatNBFX 1<<5
#define vstatNBUB 1<<6
#define vstatNBLB 1<<7
#define vstatNBFR 1<<8
#define vstatSB   1<<9
#define vstatBUUB  1<<10
#define vstatBLLB  1<<11

/*
  TAKE NOTE: Do not use the msb as a qualifier! The status value, with or
  without qualifiers, must be a positive value when cast to a signed integer.
*/

#define vstatNOPIVOT ((flags) 1<<(sizeof(flags)*8-2))
#define vstatNOPER ((flags) 1<<(sizeof(flags)*8-3))
#define vstatNOLOAD ((flags) 1<<(sizeof(flags)*8-4))

#define vstatBASIC \
        (vstatBFX|vstatBUUB|vstatBUB|vstatB|vstatBLB|vstatBLLB|vstatBFR)
#define vstatNONBASIC (vstatNBFX|vstatNBUB|vstatNBLB)
#define vstatEXOTIC (vstatSB|vstatNBFR)

#define vstatSTATUS (vstatBASIC|vstatNONBASIC|vstatEXOTIC)
#define vstatQUALS (vstatNOPIVOT|vstatNOPER|vstatNOLOAD)

/*
  This macro checks (in a simplistic way) that its parameter encodes one and
  only one status.  It's intended for mild error checking.  See
  dylp_utils:dy_chkstatus if you're really feeling paranoid.
*/

#define VALID_STATUS(zz_status_zz) \
  (zz_status_zz == vstatBFX || zz_status_zz == vstatBUB || \
   zz_status_zz == vstatB   || zz_status_zz == vstatBLB || \
   zz_status_zz == vstatBFR || \
   zz_status_zz == vstatNBFX || zz_status_zz == vstatNBUB || \
   zz_status_zz == vstatNBLB || zz_status_zz == vstatNBFR || \
   zz_status_zz == vstatSB)



/*
  Interface structures: lpprob_struct, lptols_struct, lpopts_struct
*/

/*
  basis_struct

  This structure is used to describe a basis to dylp, and to return the
  final basis at termination. The size of the basis depends on the
  number of active constraints, which will be a subset of the constraints
  in the system.

  The constraint system as supplied to dylp should not have logical variables
  (dylp will create them automatically). This presents a problem if the final
  basis contains basic logical variables. In this case, vndx is set to the
  negative of the index of the constraint which spawned the logical. This
  same technique can be used on input to, for example, specify the traditional
  all-logical starting basis.

  Field         Definition
  -----         ----------
  len           The number of rows in the basis.
  el.cndx       Index of the constraint in this basis position.
  el.vndx       Index of the variable in this basis position.

*/

typedef struct { int cndx ; int vndx ; } basisel_struct ;

typedef struct
{ int len ;
  basisel_struct *el ; } basis_struct ;


/*
  LP problem control and status flags

  lpctlNOFREE           (i) Prevents dylp from freeing the problem structures,
                            in anticipation of a subsequent hot start. If dylp
                            exits with a state that is not suitable for hot
                            start, this flag is ignored and the problem data
                            structures are released.
  lpctlONLYFREE         (i) In conjunction with an initial phase of dyDONE,
                            causes dylp to do nothing except free the problem
                            data structure and return.
  lpctlUBNDCHG          (i) Indicates that the variable upper bounds (vub) have
                            been changed.
  lpctlLBNDCHG          (i) Indicates that the variable lower bounds (lub) have
                            been changed.
  lpctlRHSCHG           (i) Indicates that the right-hand side (rhs) has been
                            changed. Includes the rhslow vector (if it exists).
  lpctlOBJCHG           (i) Indicates that the objective (obj) has been changed.
  lpctlACTVARSIN        (i) Indicates that a valid active variable vector has
                            been supplied.
  lpctlINITACTVAR       (i) Forces dylp to perform variable activation before
                            beginning simplex iterations.
  lpctlINITACTCON       (i) Forces dylp to perform constraint activation before
                            beginning simplex iterations. (If variable
                            activation is also requested, constraint activation
                            occurs first.)

  lpctlACTVARSOUT       (i) Indicates that an active variable vector is to be
                            returned.
                        (o) Indicates that a valid active variable vector has
                            been returned.

  lpctlDYVALID          (o) Indicates that dylp exited in a state which can
                            be restarted with a hot start.

*/

#define lpctlNOFREE     1<<0
#define lpctlONLYFREE   1<<1
#define lpctlUBNDCHG    1<<2
#define lpctlLBNDCHG    1<<3
#define lpctlRHSCHG     1<<4
#define lpctlOBJCHG     1<<5
#define lpctlACTVARSIN  1<<6
#define lpctlINITACTVAR 1<<7
#define lpctlINITACTCON 1<<8

#define lpctlACTVARSOUT 1<<10

#define lpctlDYVALID    1<<11

/*
  lpprob_struct

  This structure is used to pass an LP problem into dylp and convey the
  results back to the client. The allocated size indicated in colsze and
  rowsze is assumed to be accurate.  If basis, status, x, or y are NULL, they
  will be allocated as needed. If they are non-NULL, dylp will reallocate
  them if necessary (i.e., when the actual size of the lp exceeds the
  allocated size of the vectors).

  The status vector has the following coding:
    * for nonbasic variables, the normal dylp status flags are used;
    * for basic variables, the negative of the basis index is used.
  
  There is one unavoidable problem with this scheme -- the status vector
  provides the only information about the value of nonbasic variables. This
  is adequate for all but superbasic variables and nonbasic free variables
  which are not at zero. Both of these cases are transient anomalies, created
  only when the basis package is forced to patch a singular basis, and they
  should not persist in the final solution when an optimal solution is found
  or when the problem is infeasible.  They may, however, occur in the
  solution reported for an unbounded problem if the unbounded condition is
  discovered before the nonbasic free or superbasic variable is chosen for
  pivoting.  On input, nonbasic free variables are assumed to take the value
  0, and specifying a superbasic variable is illegal.

  Field         Definition
  -----         ----------
  ctlopts       Control and status flags.               
  phase         (i) If set to dyDONE, dylp will free any retained data
                    structures and return. Any other value is ignored.
                (o) Termination phase of the dynamic simplex algorithm;
                    should be dyDONE unless something screws up, in which
                    case it'll be dyINV.
  lpret         Return code from the simplex routine.
  obj           For lpOPTIMAL, the value of the objective function.
                For lpINFEAS, the total infeasibility.
                For lpUNBOUNDED, the index of the unbounded variable, negated
                  if the variable can decrease without bound, positive if it
                  can increase without bound.
                Otherwise, undefined.
  iters         The number of simplex iterations.
  consys        The constraint system.
  basis         (i) Initial basis.
                (o) Final basis.
  status        (i) Initial status vector.
                (o) Final status vector.
  x             (i) No values used, but a vector can be supplied.
                (o) The values of the basic variables (indexed by basis
                    position).
  y             (i) No values used, but a vector can be supplied.
                (o) The values of the dual variables (indexed by basis
                    position).
  actvars       There is one entry for each variable, coded TRUE if the
                variable is active, FALSE otherwise. The vector supplied on
                input will be overwritten on output.
                (i) Variables to be activated at startup. Used only for a
                    warm start. Validity is indicated by the lpctlACTVARSIN
                    flag. A vector can be supplied strictly for output use.
                (o) The current active variables. Will be returned only if
                    requested by the lpctlACTVARSOUT flag. If the vector is
                    valid on return, lpctlACTVARSOUT will remain set,
                    otherwise it will be reset.

  colsze        Allocated column capacity (length of status vector).
  rowsze        Allocated row capacity (length of basis, x, and y vectors).

  
  Note that dylp will reallocate status, basis->el, actvars, x, and y, if the
  vectors supplied at startup are too small to report the solution. Don't set
  colsze or rowsze to nonzero values without actually allocating space.
*/

typedef struct
{ flags ctlopts ;
  dyphase_enum phase ;
  lpret_enum lpret ;
  double obj ;
  int iters ;
  consys_struct *consys ;
  basis_struct *basis ;
  flags *status ;
  double *x ;
  double *y ;
  bool *actvars ;
  int colsze ;
  int rowsze ; } lpprob_struct ;



/*
  lptols_struct

  This structure contains phase and tolerance information for the lp algorithm.

  The philosophy with respect to the separate zero and feasibility tolerances
  for primal and dual variables is that dylp uses the zero tolerance when
  calculating primal or dual variables, and the feasibility tolerance when
  checking for feasibility. This allows us to keep small values for accuracy
  in computation, but not be so fussy when it comes to feasibility.

  Field         Definition
  -----         ----------
  inf           Infinity. dylp uses IEEE FP infinity, but be careful not to
                pass it to the basis package.
  zero          Zero tolerance for primal variables, and also the generic
                zero tolerance for constraint coefficients, right-hand-side
                values, etc.
  pchk          Primal accuracy check tolerance.
  pfeas         Primal feasibility check tolerance; dynamically scaled from
                zero in proportion to the 1-norm of the primal basic variables.
  pfeas_scale   Primal feasibility check tolerance multiplier. This provides
                some user-controllable decoupling of zero and pfeas.
  cost          Base zero tolerance for checks involving objective function
                coefficients, reduced costs, and related values.
  dchk          Dual accuracy check tolerance. Also used by dy_duenna to
                test for improvement in the objective.
  dfeas         Dual feasbility check tolerance; dynamically scaled from cost
                in proportion to the 1-norm of the dual variables. Acts as the
                zero tolerance for reduced costs.
  dfeas_scale   Dual feasibility check tolerance multiplier. This provides
                some user-controllable decoupling of cost and dfeas.
  pivot         Simplex pivot selection tolerance, expressed as a multiplier
                for the pivot selection tolerance used by the basis package
                when factoring the basis. (I.e., the actual pivot selection
                criteria will be to accept a simplex pivot a<i,j> if
                |a<i,j>| > lptols.pivot*basis.pivot*MAX{i}|a<i,j>|.)
  bogus         Multiplier used to identify 'bogus' values, in the range
                tol < |val| < bogus*tol for the appropriate tolerance.
  swing         Ratio used to identify excessive growth in primal variables
                (pseudo-unboundedness).
  toobig        Absolute value of primal variables which will cause dual
                multipivoting to consider primal infeasibility when selecting
                a flip/pivot sequence.
  purge         Percentage change in objective function required before
                constraint or variable purging is attempted.
  purgevar      Percentage of maximum reduced cost used to determine the
                variable purge threshold; nonbasic architectural variables
                at their optimum bound whose reduced cost exceeds
                purgevar*MAX{j}cbar<j> are purged.

  reframe       Multiplier used to trigger a reference framework reset in
                PSE pricing; reset occurs if
                  |gamma<j> - ||abar<j>||^2| > reframe*||abar<j>||^2.
                The check is made in pseupdate.
                Also used to trigger recalculation of the basis inverse row
                norms used in DSE pricing; reset occurs if
                  |rho<i> - ||beta<i>||^2| > reframe*||beta<i>||^2.
                The check is made in dseupdate.
*/

typedef struct
{ double inf ;
  double zero ;
  double pchk ;
  double pfeas ;
  double pfeas_scale ;
  double cost ;
  double dchk ;
  double dfeas ;
  double dfeas_scale ;
  double pivot ;
  double bogus ;
  double swing ;
  double toobig ;
  double purge ;
  double purgevar ;
  double reframe ; } lptols_struct ;

#if defined(DYLP_INTERNAL) || defined(BONSAIG)
/*
  A few handy macros for testing values against tolerances.
*/
#ifdef DYLP_INTERNAL
#  ifdef BND_TOLER
#    undef BND_TOLER
#  endif
#  define BND_TOLER dy_tols->pfeas
#  ifdef INF_TOLER
#    undef INF_TOLER
#  endif
#  define INF_TOLER dy_tols->inf
#endif

#define withintol(zz_val_zz,zz_tgt_zz,zz_tol_zz) \
  (fabs((zz_val_zz)-(zz_tgt_zz)) <= zz_tol_zz)

#define setcleanzero(zz_val_zz,zz_tol_zz) \
  if (fabs(zz_val_zz) < zz_tol_zz) zz_val_zz = 0

#define atbnd(zz_val_zz,zz_bnd_zz) \
  ((fabs(zz_bnd_zz) < INF_TOLER) && \
   (fabs((zz_val_zz)-(zz_bnd_zz)) < BND_TOLER*(1.0+fabs(zz_bnd_zz))))

#define belowbnd(zz_val_zz,zz_bnd_zz) \
  ((fabs(zz_bnd_zz) < INF_TOLER) ? \
   (((zz_bnd_zz)-(zz_val_zz)) > BND_TOLER*(1.0+fabs(zz_bnd_zz))) : \
   (zz_val_zz < zz_bnd_zz))

#define abovebnd(zz_val_zz,zz_bnd_zz) \
  ((fabs(zz_bnd_zz) < INF_TOLER) ? \
   (((zz_val_zz)-(zz_bnd_zz)) > BND_TOLER*(1.0+fabs(zz_bnd_zz))) : \
   (zz_val_zz > zz_bnd_zz))

#define withinbnds(zz_lb_zz,zz_val_zz,zz_ub_zz) \
  (!abovebnd(zz_val_zz,zz_ub_zz) && !belowbnd(zz_val_zz,zz_lb_zz))

#endif /* DYLP_INTERNAL || BONSAIG */

#ifdef DYLP_INTERNAL
/*
  Finally, a macro to decide if we should snap to a value. The notion here is
  that the accuracy with which one can hit a target value depends on both the
  magnitude of the target and the distance travelled to get there. On a
  64-bit machine, IEEE FP has about 15 decimal digits of accuracy. For
  example, if we're travelling 1.0e7 and trying to hit zero, we only have 8
  decimal places of accuracy remaining. If we're within 1.0e-8, might as well
  snap to 0. In practice, there's already a bit of roundoff in any nontrivial
  calculation, so we start with the zero tolerance and scale from there.
  
  In some cases, we only know the target, so the best we can do is
  scale to it.

  The utility of this idea is highly questionable.
*/

#define snaptol1(zz_tgt_zz) (dy_tols->zero*(1.0+(zz_tgt_zz)))

#define snaptol2(zz_tgt_zz,zz_dst_zz) \
  (dy_tols->zero*(1.0+maxx((zz_tgt_zz),(zz_dst_zz))))

#define snaptol3(zz_tol_zz,zz_tgt_zz,zz_dst_zz) \
  ((zz_tol_zz)*(1.0+maxx((zz_tgt_zz),(zz_dst_zz))))

#endif /* DYLP_INTERNAL */



/*
  Enum for initial basis type.

  This determines the criteria used to select the initial set of basic
  variables during a cold start.

  ibINV         invalid
  ibLOGICAL     Use only logical (slack and artificial) variables
  ibSLACK       Use slack variables for inequalities. Prefer architectural
                over artificial variables for equalities.
  ibARCH        Prefer architectural variables over logical variables.
*/

typedef enum { ibINV = 0, ibLOGICAL, ibSLACK, ibARCH } ibtype_enum ;

/*
  Enum for calling context.

  As dylp evolves, it may well prove useful to know the context of the
  call. Consider this an experiment. The default context is INITIALLP.

  cxINV         invalid (context is unknown)
  cxSINGLELP    This is a one-off call to solve a single LP from scratch.
  cxINITIALLP   This is a call to solve a single LP from scratch, but will
                likely be followed by calls to reoptimise.
  cxBANDC       This call is made in the context of a branch-and-cut
                algorithm.
*/

typedef enum { cxINV = 0, cxSINGLELP, cxINITIALLP, cxBANDC } cxtype_enum ;

/*
  lpopts_struct

  This structure is used to pass option settings to dylp. Default values are
  declared at the beginning of dy_setup.c.

  Field         Definition
  -----         ----------
  context       The context in which dylp is being called. See comments
                above for cxtype_enum.
  forcecold     TRUE to force a cold start, FALSE otherwise. If set to TRUE,
                dominates warm and hot start.
  forcewarm     TRUE to force a warm start, FALSE otherwise. If set to TRUE,
                dominates hot start.
  fullsys       Forces the use of the full constraint system at all times. The
                full constraint system is loaded on startup, and all constraint
                and variable deactivation/activation is skipped. (But see the
                finpurge option below.) (Also, this will not prevent dylp
                from resorting to forced phase transitions, which typically
                involve deactivation of constraints or variables. Arguably
                this is a bad thing, and may change in the future.)
  active        Used to estimate the initial size of the dylp constraint
                system relative to the original system.
    vars          Fraction of original variables expected to be active at
                  any time.
    cons          Fraction of original inequalities expected to be active at
                  any time.
  initcons      Specifies how inequalities will be selected to initialize the
                active system. See extensive comments in dy_coldstart.c.
    frac          Fraction of inequalities to be used.
    i1l           Lower bound on angle to objective, first interval
    i1lopen       TRUE if the bound is open.
    i1u           Upper bound on angle to objective, first interval
    i1uopen       TRUE if the bound is open.
    i2valid       TRUE if the second interval is specified
    i2l           Lower bound on angle to objective, second interval
    i2lopen       TRUE if the bound is open.
    i2u           Upper bound on angle to objective, second interval
    i2uopen       TRUE if the bound is open.
  coldbasis     Code specifying the kind of basis built for a cold start. See
                comments for ibtype_enum and comments in dy_coldstart.c
  finpurge      Controls whether dylp does a final deactivation of constraints
                and/or variables. This will occur only an optimal solution is
                found, and is not suppressed by fullsys.
    cons          TRUE to purge constraints
    vars          TRUE to purge variables
  heroics       Controls behaviour during forced primal <-> dual transitions
    d2p           TRUE to allow deactivation of basic architecturals, FALSE
                  to disallow. FALSE is recommended, and the default.
    p2d           TRUE to allow deactivation of tight constraints, FALSE
                  to disallow. FALSE is recommended, and the default.
    flip          TRUE to allow flips to regain dual feasibility, FALSE to
                  disallow. Tends to cycle; default is false.
  coldvars      If the number of active variables exceeds this value after
                a cold start, dylp will attempt to purge variables prior to
                the initial primal simplex run.
  con           Options related to constraint activation/deactivation
    actlvl        The constraint activation strategy
                    0: (strict) activate violated constraints,
                       lhs < rhslow or lhs > rhs
                    1: (tight) activate tight or violated constraints,
                       lhs <= rhslow or lhs >= rhs
    actlim        If non-zero, limits the number of constraints that can be
                  activated in any one call to a constraint activation
                  routine.
    deactlvl    The constraint deactivation strategy:
                  0: (normal) deactivate only inequalities i which are
                     strictly loose (i.e., slk<i> basic, not at bound).
                  1: (aggressive) normal plus inequalities which are tight
                     with y<i> = 0.
                  2: (fanatic) aggressive plus equalities with y<i> = 0
  usedual       TRUE if dual phase II is to be used to regain feasibility after
                adding constraints, FALSE to force use of primal phase I.
  addvar        If non-zero, at most this many variables will be added in
                any one pass through phase dyADDVAR.
  dualadd       Controls the types of activation allowed when adding variables
                during dual simplex.
                  0:    variable activation is disallowed
                  1:    type 1 activation (variables that will be dual feasible
                        when activated into the nonbasic partition)
                  2:    type 2 activation (variables which can be activated
                        if immediately pivoted into the basis)
                  3:    type 3 activation (activate with bound-to-bound pivot)
                See dy_dualaddvars for more extensive comments.
  scan          Partial pricing parameter. Controls the number of columns to
                be scanned for a new candidate entering variable when the
                candidate selected during PSE update is rejected.
  iterlim       The per phase pivot limit for the code; if set to 0, no
                limit is enforced.
  idlelim       The number of iterations without change in the objective
                function before the code declares the problem is stalled or
                cycling.
  dpsel         Options to control dual pivoting. Selection of the leaving
                variable is always handled by DSE.
    strat:        The strategy used to select the entering variable:
                    0: standard ratio test; may use anti-degen lite
                    1: multipivoting, selecting for maximum dual objective
                       improvement.
                    2: multipivoting, select for minimum predicted
                       infeasibility.
                    3: multipivoting, select infeasibility reduction if
                       possible, otherwise maximum dual objective improvement.
    flex          If TRUE, dylp will switch between strategies 1 and 3, using
                  strategy 1 unless primal magnitudes become too large.
    allownopiv    If TRUE, sequences of flips with no finishing pivot will be
                  allowed. Defaults to false, very prone to cycling.
  ppsel         Options to control primal pivoting. Selection of the entering
                variable is always handled by PSE.
    strat:        The strategy used to select the leaving variable:
                    0: standard ratio test; may use anti-degen lite
                    1: multipivoting
  factor        The LP basis will be refactored every factor iterations, in
                the absence of some compelling reason (typically error
                recovery) that forces it to occur sooner.
  check         An accuracy check will be forced every check iterations, in
                the absence of some compelling reason to do it earlier.
  groom         Controls the action taken by the basis grooming routine
                when it makes a nontrivial status correction:
                  0:    catatonic
                  1:    issue a warning
                  2:    issue an error message and force an abort
                Numeric codes are related to keywords in dy_setup.c:dy_ctlopt.
  degen         TRUE to allow creation of restricted subproblems to deal with
                degeneracy, FALSE to disallow it.
  degenpivlim   The number of successive degenerate pivots required before
                creating a restricted subproblem.
  degenlite     Controls secondary antidegeneracy --- `antidegen lite'
                  0: (pivotabort) break ties using |abar<kj>| and abort when
                     delta<j> = 0
                  1: (pivot) break ties using |abar<kj>| but always scan the
                     full basis
                  2: (alignobj) break ties by examining the alignment of the
                     hyperplane which will become tight on the pivot; choose
                     so that movement in the direction of the objective most
                     nearly lies in the hyperplane
                  3: (alignedge) break ties by examining the alignment of the
                     hyperplane which will become tight on the pivot; choose
                     so that the direction of motion defined by the entering
                     variable most nearly lies in the hyperplane.
                  4: (perpobj) break ties by examining the alignment of the
                     hyperplane which will become tight on the pivot; choose
                     so that the normal of the hyperplane is most nearly
                     aligned with the normal of the objective
                  5: (perpedge) break ties by examining the alignment of the
                     hyperplane which will become tight on the pivot; choose
                     so that the normal of the hyperplane is most nearly
                     aligned with the direction of motion
                Numeric codes are related to keywords in dy_setup.c:dy_ctlopt.
  patch         TRUE to allow the code to patch a singular basis, FALSE to
                prevent patching.
  copyorigsys   Controls whether dylp makes a local copy of the original
                system. If set to TRUE, dylp will always make a local copy.
                If set to FALSE, a copy will be made only if necessary.
                Scaling will trigger a local copy.
  scaling       Controls whether dylp attempts to scale the original constraint
                system.
                  0: scaling is forbidden
                  1: scale the original constraint system using scaling vectors
                     attached to the system
                  2: evaluate the original constraint system and scale it if
                     necessary
  print         Substructure for picky printing control. For all print options,
                a value of 0 suppresses all information messages.
    major         Controls printing of major phase information.
                  1: a message at each phase transition.
    scaling       Controls print level during initial evaluation and scaling of
                  the original constraint system.
                  1: start and finish messages
                  2: stability measures for original and scaled matrices;
                     adjustments to tolerances.
    setup         Controls print level while creating the initial constraint
                  system for dylp.
                  1: start and finish messages.
                  2: summary information about activated constraints
                  3: messages about each constraint included in the initial
                     system.
                  4: messages about each constraint processed for the initial
                     system
                  5: messages about each variable included in the initial
                     system.
                  6: lists value and status of inactive variables with
                     nonzero values
    crash         Controls print level while crashing the basis.
                  1: start & finish messages
                  2: summary counts for logicals, architecturals, artificials
                  3: a dump of the completed basis
                  4: detailed info on the selection of each architectural
                     and artificial variable
    pricing       Controls print level for pricing of columns (rows) in primal
                  (dual) simplex.
                  1: summary messages
                  2: lists candidate list and primal variable selected for
                     entry (exit) at each pivot
                  3: lists each variable as it's added to the candidate list
                     and again when reconsidered for pivoting
    pivoting      Controls print level for selection of the leaving (entering)
                  primal variable in primal (dual) simplex and updating of
                  variables.
                  1: prints result of leaving (entering) variable selection
                  2: information about the selection of the leaving (entering)
                     variable.
                  3: more information about the selection of the leaving
                     (entering) variable.
                  4: prints the pivot column (row) before and after
                     multiplication by the basis inverse, and yet more
                     pivot selection information.
                  5: prints a line for every candidate evaluated
    pivreject     Controls print level for information related to the operation
                  of the pivot rejection mechanism.
                  1: Prints a message for each row/column added to the pivot
                     rejection list, plus other major events.
                  2: Prints a message for each row/column removed from the
                     pivot rejection list.
    degen         Controls print level for information related to the operation
                  of the antidegeneracy mechanism.
                  1: prints a message each time the antidegeneracy level
                     changes
                  2: prints a message when a true degenerate pivot is taken
                     under duress
                  3: prints a message when a degenerate pivot is taken
                  4: prints anomalies as each degenerate set is formed and
                     backed out
                  5: prints details of each degenerate set as it's formed and
                     backed out
    phase1        Controls general print level for phase 1 of primal simplex.
                  1: messages about extraordinary events -- problem pivots, etc.
                  2: messages about 'routine' but infrequent events --
                     termination conditions, refactoring, unboundedness, etc.
                  3: messages with additional details of problems encountered
                  4: a one line log message is printed for each pivot
                  5: summary information about infeasible variables and phase
                     I objective coefficients; information about primal
                     variables updated at each pivot.
                  6: prints the primal variables after each pivot; prints
                     infeasible variables during phase I objective construction
                  7: prints the dual variables after each pivot; prints
                     infeasible variables during phase I objective modification
    phase2        Controls general print level for phase 1 of primal simplex.
                  1: messages about extraordinary events -- problem pivots, etc.
                  2: messages about 'routine' but infrequent events --
                     termination conditions, refactoring, unboundedness, etc.
                  3: messages with additional details of problems encountered
                  4: a one line log message is printed for each pivot
                  5: prints the updated basic primal variables after each pivot
                  6: prints all basic primal variables after each pivot
                  7: prints the dual variables after each pivot.
    dual          Controls general print level for the dual simplex. As
                  phase2.
    basis         Controls print level in routines working with the basis.
                  1: summary warnings about problems: empty rows, singularity,
                     numerical instability, etc.
                  2: information about factoring failures and recovery actions
                  3: warnings about individual empty rows, details of column
                     replacement when patching a singular basis, pivot
                     tolerance adjustments; information about pivoting failures
                     and recovery actions
                  4: basis stability after factoring
                  5: basis stability after pivoting
    conmgmt       Controls print level while dylp is in the purge/generate/
                  activate constraint phases.
                  1: prints the number of constraints purged, generated,
                     & activated, and new size of constraint system.
                  2: prints a message for each constraint purged or activated.
                     (The cut generation routine is responsible for
                     handling this function when it generates cuts.)
                  3: additional details about refactoring and new values
                     of primal and dual variables.
                  4: prints a message about any variables affected as a side
                     effect of constraint changes, constraints processed
                     but not activated, and information about direction of
                     recession and relative angle of constraints when adding
                     constraints to an unbounded problem.
                  5: prints a running commentary on constraint and variable
                     shifts, inactive variables.
    varmgmt       Controls print level while dylp is in the purge/generate/
                  activate variable phases.
                  1: prints the number of variables purged, generated,
                     & activated, and new size of constraint system.
                  2: prints a message for each variable purged & activated.
                     (The column generation routine is responsible for
                     handling this function when it generates new variables).
                  3: prints a message about any constraints affected as a side
                     effect of variable changes, variables processed but not
                     activated, and information about direction of recession
                     and relative angle of dual constraints when adding
                     variables to an unbounded dual.
                  4: prints a running commentary on constraint and variable
                     shifts.
    force         Controls print level when dylp is attempting to force a
                  transition (primal -> dual, dual -> primal) or force the
                  use of the full constraint system.
                  1: prints a summary message giving the result of the
                     transition attempt
                  2: prints messages about actions taken for individual
                     constraints and variables.
                  3: additional information about variables and constraints
                     examined.
*/

typedef struct
{ cxtype_enum context ;
  int scan ;
  int iterlim ;
  int idlelim ;
  struct { int strat ;
           bool flex ;
           bool allownopiv ; } dpsel ;
  struct { int strat ; } ppsel ;
  int factor ;
  int check ;
  int groom ;
  struct { int actlvl ;
           int actlim ;
           int deactlvl ; } con ;