coinor-libdylp-dev 1.6.0-1.1ubuntu2 / usr / include / coin / dy_consys.h

/*
  This file is a portion 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 _CONSYS_H
#define _CONSYS_H

/*
  @(#)dy_consys.h	4.4	11/11/04
  svn/cvs: $Id: dy_consys.h 240 2008-06-18 23:32:21Z lou $

  This header file contains declarations for a constraint system data
  structure, tailored for LP-based branch-and-cut MILP algorithms (more
  generally, for any situation where dynamic change in the number of rows
  and/or columns is expected). The constraint system allows for arbitrary
  additions and deletions. Additional space is allocated as needed; there are
  no a priori limits. Allocated space is never reduced, however, short of
  destroying the constraint system.

  The coefficient matrix is implemented as a sparse structure, linked by row
  and by column. Access to the rows and columns of the coefficient matrix is
  via utility routines.
  
  To provide O(1) cost for row and column addition and deletion, while
  maintaining a dense index set, the hole left by deleting a row or column
  is filled by moving the last row or column to occupy the vacant index slot.

  The client can 'attach' row and column vectors to the constraint system;
  more precisely, vectors and multiple pointers to those vectors.  The
  vectors will be dynamically resized and pointers updated whenever rows
  or columns are added to the constraint system. Entries in attached vectors
  are automatically reordered when a row or column is moved to fill the hole
  left by a deletion.

  The user is expected to work directly with any attached vectors; there are
  no special access routines.

  Because rows and columns can move, clients must be careful when they keep
  records of row or column indices, and update these records as necessary.

  A special set of attached vectors are referred to as associated vectors.
  These are distinguished only by having pointers allocated in the constraint
  system header structure.

  NOTE: The package assumes that variables and constraints are indexed from
	1; this makes error checking a lot more reliable, particularly for
	errors of omission (whoops, forgot to set that index ... ). Vectors
	intended for expanded rows or columns must be sized accordingly.
	(I.e., if vector is to hold k values, the actual allocated space
	is k+1 entries, with vector[0] unused.) consys will do this
	automatically when asked to allocate space. Clients must remember
	this when allocating space for vectors that they will attach to a
	constraint system.

  NOTE: The constraint system is prepared to deal with both finite (most
	often DBL_MAX) and infinite (IEEE) infinity in the upper and lower
	bounds vectors for variables (vlb, vub). Explicit checks are
	necessary to maintain the value of a finite infinity when scaling the
	constraint system. The value of infinity must be supplied as a
	parameter to create_consys(). It's not a good idea to have infinity
	popping up elsewhere, but IEEE infinity should work (because no
	explicit checks are required for mathematical correctness).

  NOTE: At the infinitesimal end, any coefficient with absolute value less
	than 1.0e-20 will be dropped. Currently this is hardwired (see
	consys_create). It may change if there's a need.
*/

#include "dy_vector.h"



/*
  Constraint coefficient matrix

  This is a sparse-matrix data structure, linked by row and column.

  Note that rows and columns are << not >> sorted in index order. Insertions
  and deletions are done adjacent to the headers, for efficiency.
*/
/*
  Coefficients

  Field		Description
  -----		-----------
  rowhdr	The row header for this coefficient.
  colhdr	The column header for this coefficient.
  val		The value of this coefficient.
  rownxt	The next coefficient in this row.
  colnxt	The next coefficient in this column.
*/

typedef struct coeff_struct_tag
{ struct rowhdr_struct_tag *rowhdr ;
  struct colhdr_struct_tag *colhdr ;
  double val ;
  struct coeff_struct_tag *rownxt ;
  struct coeff_struct_tag *colnxt ; } coeff_struct ;

/*
  Column headers

  Field		Description
  -----		-----------
  ndx		The index of this column.
  len		The number of coefficients in the column.
  nme		The name of the variable associated with the column.
  coeffs	The coefficients of the column.
*/

typedef struct colhdr_struct_tag
{ int ndx ;
  int len ;
  const char *nme ;
  coeff_struct *coeffs ; } colhdr_struct ;

/*
  Row headers

  Field		Description
  -----		-----------
  ndx		The index of this row.
  len		The number of coefficients in the row.
  nme		The name of the variable associated with the row.
  coeffs	The coefficients of the row.
*/

typedef struct rowhdr_struct_tag
{ int ndx ;
  int len ;
  const char *nme ;
  coeff_struct *coeffs ; } rowhdr_struct ;

/*
  Coefficient matrix header

  Field		Definition
  -----		---------
  coeffcnt	The number of coefficients in the matrix.
  cols		Array of pointers to column headers.
  rows		Array of pointers to row headers.
*/

typedef struct
{ int coeffcnt ;
  colhdr_struct **cols ;
  rowhdr_struct **rows ; } conmtx_struct ;



/*
  Attached Vectors:

  As mentioned at the top, attached vectors are automatically resized whenever
  the constraint system is resized, and reorderd to track the movement of rows
  and columns due to deletions.

  A particular subset of attached vectors are designated as associated
  vectors; a system has at most one of each type of associated vector.
  Their only distinguishing characteristic is that they occupy the dedicated
  pointers in the constraint system header:
   * objective function
   * variable type <3>
   * variable upper & lower bounds
   * right-hand-side (a.k.a. rhs or b) and rhsl (a.k.a. rhslow or blow) <1>
   * constraint type
   * upper & lower bounds for constraint left-hand-sides <2>
   * row and column scaling vectors (more accurately, the diagonal elements
     of row and column scaling matrices)
   
   <1> rhsl is created when range constraints (blow <= ax <= b) are present
       in the constraint system.
   <2> These are calculated using the upper and lower bounds on the variables
       in the constraint, and are used in arc consistency calculations. See
       further explanation below.
   <3> Arguably the variable type vector only needs to cover the architectural
       variables, but it'd be a pain to distinguish a resize involving the
       architectural columns from a resize involving the logical columns.
       Easier to waste a little space.

  The flags given below are used in attached vector headers to indicate
  how a vector should be handled, and in the consys_struct.parts field to
  indicate which components of the constraint system are present. Their
  most important function is to specify whether a vector is a row vector
  or a column vector. Beyond that, they serve as weak consistency and type
  checks.
  
  Notes:
  * MTX, ROWHDR, and COLHDR cannot be allocated/deallocated, but having
    codes for them makes the interface to some of the utility routines a
    bit more uniform.
  * COL and ROW should be used for generic column and row vectors,
    respectively.
  * VUB is initialised to +infinity.
  * RSCALE and CSCALE are initialised to 1.0
  * VTYP and CTYP are tied to the vartyp_enum and contyp_enum types.
*/

#define CONSYS_MTX	((flags) 1<<0)
#define CONSYS_ROW	((flags) 1<<1)
#define CONSYS_COL	((flags) 1<<2)
#define CONSYS_OBJ	((flags) 1<<3)
#define CONSYS_VUB	((flags) 1<<4)
#define CONSYS_VLB	((flags) 1<<5)
#define CONSYS_RHS	((flags) 1<<6)
#define CONSYS_CUB	((flags) 1<<7)
#define CONSYS_CLB	((flags) 1<<8)
#define CONSYS_RHSLOW	((flags) 1<<9)
#define CONSYS_VTYP	((flags) 1<<10)
#define CONSYS_CTYP	((flags) 1<<11)
#define CONSYS_COLHDR	((flags) 1<<12)
#define CONSYS_ROWHDR	((flags) 1<<13)
#define CONSYS_RSCALE	((flags) 1<<14)
#define CONSYS_CSCALE	((flags) 1<<15)

/*
  Macros to identify row and column vectors.
*/
#define CONSYS_ROWVEC \
  (CONSYS_OBJ|CONSYS_VUB|CONSYS_VLB|CONSYS_VTYP|CONSYS_CSCALE| \
   CONSYS_COLHDR|CONSYS_ROW)

#define CONSYS_COLVEC \
  (CONSYS_RHS|CONSYS_RHSLOW|CONSYS_CUB|CONSYS_CLB|CONSYS_CTYP|CONSYS_RSCALE| \
   CONSYS_ROWHDR|CONSYS_COL)

/*
  A macro to check for a valid vector type.
*/

#define VALID_ATTVTYPE(zz_vectype_zz) \
  (zz_vectype_zz == CONSYS_OBJ || \
   zz_vectype_zz == CONSYS_VUB || zz_vectype_zz == CONSYS_VLB || \
   zz_vectype_zz == CONSYS_RHS || zz_vectype_zz == CONSYS_RHSLOW || \
   zz_vectype_zz == CONSYS_CUB || zz_vectype_zz == CONSYS_CUB || \
   zz_vectype_zz == CONSYS_VTYP || zz_vectype_zz == CONSYS_CTYP || \
   zz_vectype_zz == CONSYS_RSCALE || zz_vectype_zz == CONSYS_CSCALE || \
   zz_vectype_zz == CONSYS_ROW || zz_vectype_zz == CONSYS_COL)


/*
  Attached vector header

  This structure is used in the list of attached vectors that should be
  checked and resized with the constraint system.

  Field		Definition
  -----		----------
  nxt		List link.
  what		The type of vector (coded with the flag values for
		attached and associated vectors)
  elsze		The size of an element in the vector.
  vec		The address of the vector.
  pveclst	A list of addresses which hold pointers to vec. If vec is
		moved as a result of a resize, these are rewritten.
*/

typedef struct attvhdr_struct_tag { struct attvhdr_struct_tag *nxt ;
			            flags what ;
				    int elsze ;
			            void *vec ;
				    lnk_struct *pveclst ; } attvhdr_struct ;

/*
  Constraint bounds

  Constraint bounds are upper and lower bounds on the value of the
  left-hand-side of a constraint, calculated using the upper and lower bounds
  on variables. In the case where all variables have finite bounds, the
  constraint bound will also be finite, and things are straightforward. But
  there's a complication --- we'll want to be able to efficiently handle the
  case where all variables have finite bounds except one, x<t>. In this case
  we can calculate a finite bound for the free variable, using the bounds on
  the other variables. Bottom line is we need a structure that keeps count of
  the number of infinities, as well as the finite portion of the bound. See
  consistency.c for more about the mechanics of particular cases.

  The interpretation of an entry is as follows:
    -varcnt <= inf < 0	inf is the negative of the index of the single
			remaining variable contributing an infinity; bnd is
			the finite lhs bound calculated from the other
			variables of the constraint
    inf >= 0		inf is the number of variables contributing infinity
			to the bound; bnd is the value of the finite portion
			of the lhs bound. If inf == 0, the lhs bound is finite.

    inf < -varcnt and inf = 1 are invalid. A value which exceeds the number of
    variables in the constraint is also bogus.

  This encoding means that it's impossible to distinguish +inf and -inf just
  by looking at the bound. But, in the case of constraint bounds, this hasn't
  been a problem in practice. Lower bounds go to -inf, and upper bounds go to
  +inf, and context has been sufficient.

  The revs field is used to keep track of the number of times the bound has
  been revised. See milp.h:mipopts_struct for the recalculation frequency.
*/

typedef struct { int revs ;
		 int inf ;
		 double bnd ; } conbnd_struct ;



/*
  Constraint type codes

  These codes have their origin in the MPS input standard.

  contypINV	invalid
  contypNB	non-binding constraint <1>
  contypGE	>= inequality
  contypEQ	equality
  contypLE	<= inequality
  contypRNG	'range' constraint, lb <= ax <= ub (a sort of shorthand for
		a >= and a <= inequality)

  <1> Non-binding constraints are a bit odd. They are used in two ways.
      The first non-binding constraint in the MPS file is, by convention,
      the objective function. The other use for non-binding constraints is
      in rows of type Dx (x one of N, E, G, or L), which specify linear
      combinations of constraints.
  <2> Following OSL (a good lead to follow when they're going where I want to
      go  :-), bonsai doesn't accept Dx rows, and throws away all but the
      first non-binding constraint, which it keeps only if it needs it for
      the objective function.
*/

typedef enum { contypINV = 0, contypNB,
	       contypGE, contypEQ, contypLE, contypRNG } contyp_enum ;

#define VALID_CONTYPE(zz_ctyp_zz) \
  (zz_ctyp_zz == contypGE || zz_ctyp_zz == contypEQ || \
   zz_ctyp_zz == contypLE || zz_ctyp_zz == contypRNG)

/*
  Variable type codes

  vartypINV	invalid
  vartypCON	continuous variable
  vartypINT	general integer variable
  vartypBIN	binary variable
*/

typedef enum { vartypINV = 0, vartypCON,
	       vartypINT, vartypBIN } vartyp_enum ;

#define VALID_VARTYPE(zz_vtyp_zz) \
  (zz_vtyp_zz == vartypCON || \
   zz_vtyp_zz == vartypINT || \
   zz_vtyp_zz == vartypBIN)

#define INT_VARTYPE(zz_vtyp_zz) \
  (zz_vtyp_zz == vartypINT || \
   zz_vtyp_zz == vartypBIN)

/*
  Behavioural options

  These codes are used as flags in the opts field of the constraint system
  header.

  CONSYS_LVARS	Set to indicate that logical variables are present and should
		be automatically maintained during constraint system
		manipulations.
  CONSYS_WRNZERO Set to indicate that a warning should be issued when the
		constraint system utility routines encounter a zero-length
		column or row. Also causes a warning during row/column
		creation and basis initialisation if an explicit zero
		coefficient is encountered.
  CONSYS_WRNATT Set to indicate that a warning should be issued when a
		duplicate attach request is encountered (i.e., both the
		vector and the pointer to the vector are already on the
		attvecs list).
  CONSYS_FININF	`Finite infinity' --- the client is indulging in the common
		trick of using a large finite value (most often, DBL_MAX) as
		infinity.
  CONSYS_CORRUPT The constraint system is corrupt --- an error has occurred
		during construction or modification that caused an operation
		to abort. Currently set only for errors that occur outside of
		debug and paranoia (you're supposed to look at the error
		messages for paranoia and debug).
*/

#define CONSYS_LVARS	((flags) 1<<0)
#define CONSYS_WRNZERO	((flags) 1<<1)
#define CONSYS_WRNATT	((flags) 1<<2)
#define CONSYS_FININF	((flags) 1<<3)
#define CONSYS_CORRUPT	((flags) 1<<4)

/*
  Constraint system header

  The top-level 'handle' for the structure.

  Field		Definition
  -----		---------
  nme		The name assigned to this constraint system.
  parts		Flags indicating which components of the constraint system are
		supposed to be present.
  opts		Flags indicating various behavioural options.
  inf		The value of infinity.
  tiny		The value of the infinitesimal.
  varcnt	The total number of variables (and the column dimension).
  archvcnt	The number of architectural variables. The number of continuous
		architectural variables is archvcnt-(intvcnt+binvcnt).
  logvcnt	The number of logical variables.
  intvcnt	The number of general integer variables.
  binvcnt	The number of binary variables.
  maxcollen	The number of coefficients in the largest column.
  maxcolndx	The index of the largest column.
  concnt	The total number of constraints (and the row dimension).
  archccnt	The number of architectural constraints.
  cutccnt	The number of cut constraints.
  maxrowlen	The number of coefficients in the largest row.
  maxrowndx	The index of the largest row.
  colsze	The allocated column capacity for the constraint system.
  rowsze	The allocated row capacity for the constraint system.
  mtx		The constraint matrix header.

    The vectors rowscale and colscale are valid only after execution of one
    of the scaling routines consys_geomscale, consys_equiscale, or
    consys_applyscale. The fields maxaij and minaij are valid only after
    execution of consys_evalsys or any of the scaling routines.

  maxaij	max{i,j} |a<ij>| (valid only after scaling)
  minaij	min{i,j, a<ij> != 0} |a<ij>| (valid only after scaling)
  rowscale	The row scaling vector.
  colscale	The column scaling vector.

  objnme	The name of the objective function.
  objndx	Index of the objective function, if it's installed as a
		constraint cx - x<z> = 0.
  xzndx		Index of the variable x<z>.
  obj		The objective function.
  vtyp		The type of variable.
  vub		The upper bounds for variables.
  vlb		The lower bounds for variables.
  rhs		The right-hand-side vector.
  rhslow	blow for range constraints of form blow <= ax <= b.
  ctyp		The type of constraint (contyp_enum).
  cub		The upper bounds for constraint left-hand-sides.
  clb		The lower bounds for constraint left-hand sides.
  attvecs	The list of attached vectors.

  NOTE the distinction between dimension and size -- the allocated capacity
       of the constraint system is [rowsze x colsze], while the actual size
       of the constraint system is [concnt x varcnt].
*/

typedef struct
{ const char *nme ;
  flags parts ;
  flags opts ;
  double inf ;
  double tiny ;
  int varcnt ;
  int archvcnt ;
  int logvcnt ;
  int intvcnt ;
  int binvcnt ;
  int maxcollen ;
  int maxcolndx ;
  int concnt ;
  int archccnt ;
  int cutccnt ;
  int maxrowlen ;
  int maxrowndx ;
  int colsze ;
  int rowsze ;
  conmtx_struct mtx ;
  double maxaij ;
  double minaij ;
  double *rowscale ;
  double *colscale ;
  const char *objnme ;
  int objndx ;
  int xzndx ;
  double *obj ;
  vartyp_enum *vtyp ;
  double *vub ;
  double *vlb ;
  double *rhs ;
  double *rhslow ;
  contyp_enum *ctyp ;
  conbnd_struct *cub ;
  conbnd_struct *clb ;
  attvhdr_struct *attvecs ; } consys_struct ;



/*
  consys_utils.c
*/

extern consys_struct *consys_create(const char *nme, flags parts, flags opts,
				    int concnt, int varcnt, double infinity) ;
extern bool consys_dupsys(consys_struct *src, consys_struct **dst,
			  flags dstvecs) ;
extern void consys_free (consys_struct *consys) ;
extern bool consys_realloc(consys_struct *consys, char rowcol, int incr),
	    consys_attach(consys_struct *consys, flags what, int elsze,
			  void **pvec),
	    consys_update(consys_struct *consys, void *oldvec, void *newvec),
	    consys_detach(consys_struct *consys, void **pvec, bool all) ;

extern bool consys_addcol_pk(consys_struct *consys,
			     vartyp_enum vartyp, pkvec_struct *pkcol,
			     double obj, double vlb, double vub),
	    consys_addcol_ex(consys_struct *consys, vartyp_enum vartyp,
			     const char **nme, double *excol,
			     double obj, double vlb, double vub),
	    consys_addrow_pk(consys_struct *consys, char rowclass,
			     contyp_enum contyp, pkvec_struct *pkrow,
			     double rhs, double rhslow,
			     conbnd_struct *cub, conbnd_struct *clb),
	    consys_getcol_pk(consys_struct *consys, int colndx,
			     pkvec_struct **pkvec),
	    consys_getcol_ex(consys_struct *consys, int colndx, double **vec),
	    consys_getrow_pk(consys_struct *consys, int rowndx,
			     pkvec_struct **pkvec),
	    consys_getrow_ex(consys_struct *consys, int rowndx, double **vec),
	    consys_delcol(consys_struct *consys, int colndx),
            consys_delrow(consys_struct *consys, int rowndx),
	    consys_delrow_stable(consys_struct *consys, int rowndx) ;

extern bool consys_setcoeff(consys_struct *consys,
			    int rowndx, int colndx, double val) ;
extern double consys_getcoeff(consys_struct *consys, int rowndx, int colndx) ;

extern bool consys_logicals(consys_struct *consys) ;

/*
  consys_mathutils.c
*/

extern int consys_gcdrow(consys_struct *consys, int rowndx) ;

extern double consys_dotcol(consys_struct *consys, int colndx, double *vec),
	      consys_dotrow(consys_struct *consys, int rowndx, double *vec) ;
extern double consys_1normrow(consys_struct *consys, int rowndx),
	      consys_ssqrow(consys_struct *consys, int rowndx),
	      consys_2normrow(consys_struct *consys, int rowndx),
	      consys_infnormrow(consys_struct *consys, int rowndx),
	      consys_1normcol(consys_struct *consys, int rowndx),
	      consys_ssqcol(consys_struct *consys, int rowndx),
	      consys_2normcol(consys_struct *consys, int rowndx),
	      consys_infnormcol(consys_struct *consys, int rowndx) ;

extern bool consys_mulrow(consys_struct *consys, int rowndx, double scalar) ;
extern bool consys_divrow(consys_struct *consys, int rowndx, double scalar) ;

extern bool consys_accumcol(consys_struct *consys, int colndx, double *vec) ;
extern bool consys_mulaccumcol(consys_struct *consys, int colndx,
			       double scalar, double *vec) ;

/*
  consys_scaling.c
*/

extern bool consys_evalsys(consys_struct *consys, double *scm, int *gecnt) ;
extern bool consys_geomscale(consys_struct *consys,
			     double **rowscale, double **colscale),
	    consys_equiscale(consys_struct *consys,
			     double **rowscale, double **colscale),
	    consys_applyscale(consys_struct *consys, bool convctyp,
			      double *rowscale, double *colscale) ;

/*
  consys_io.c
*/

extern const char *consys_prtvartyp(vartyp_enum vartyp),
		  *consys_prtcontyp(contyp_enum contyp) ;
extern char *consys_assocnme(consys_struct *consys, flags which),
	    *consys_conbndnme(char bndlett, int cndx, conbnd_struct *bnd),
	    *consys_conbndval(conbnd_struct *bnd) ;

#ifndef DYLP_NDEBUG

#include "dylib_io.h"
#include "dylib_std.h"

extern void consys_prtcon(ioid chn, bool echo,
			  consys_struct *consys, int i, const char *pfx) ;
#endif

/*
  A routine to set (change, really) the name of an existing constraint or
  variable.
*/

extern void consys_chgnme(consys_struct *consys, char cv,
			  int ndx, const char *newnme) ;

/*
  consys_nme returns a string containing the name of the specified constraint
  or variable. If the client supplies a buffer, that buffer is used to return
  the name. If a buffer isn't supplied, a little care is required.
    * If consys_nme can find a pointer to the name stored in the constraint
      matrix (i.e., in the row or column header) it will return the stored
      pointer. Successive calls will not interfere with one another.
    * If consys_nme has to build the name, it will use an internal buffer.
      Successive calls will reuse this buffer as required (overwriting the
      previous name).
  
  Names have to be built in two cases:
    * A fully prefixed name is requested (a prefix of 'consys->nme.' is
      added to the variable or constraint name).
    * The name of a logical variable is requested and logicals aren't enabled
      in the constraint system.
  
  A buffer of size CONSYS_MAXBUFLEN is guaranteed to be adequate.
*/

#define CONSYS_MAXBUFLEN 32
extern const char *consys_nme(consys_struct *consys,
			      char cv, int ndx, bool pfx, char *clientbuf) ;


#endif /* _CONSYS_H */