lpkit.h

生成直角Steiner树的程序包

/*
  Main header file of the LP_SOLVE toolkit.
  
  Original by Jeroen Dirks, 21-2-95
  Maintained by Michel Berkelaar

  include this file in your program and link with liblps.a
*/

#include <stddef.h>
#include <stdlib.h>
#include <stdio.h>
#include <math.h>
#include "hash.h"

#ifndef EXIT_FAILURE
#define EXIT_FAILURE 1	/* older <stdlib.h> seem to lack this... */
#endif

#define FALSE   0
#define TRUE    1

#define DEFNUMINV 50
#define INITIAL_MAT_SIZE 10000

/* solve status values */
#define OPTIMAL     	0
#define MILP_FAIL   	1
#define INFEASIBLE  	2
#define UNBOUNDED   	3
#define FAILURE     	4
#define RUNNING     	5

/* test_branch extra status values */
#define STOP_AT_INVERT	6

/* lag_solve extra status values */
#define FEAS_FOUND   	6
#define NO_FEAS_FOUND 	7
#define BREAK_BB	8

#define FIRST_NI	0
#define RAND_NI		1

#define REL_LE      0
#define REL_EQ      1
#define REL_GE      2
#define REL_OF      3

#if 1
/* DMW - gcc does fabs inline without conditional jumps! */
#define my_abs(x)	(fabs (x))
#else
#define	my_abs(x)	((x) < 0 ? -(x) : (x))
#endif
#define my_min(x, y)    ((x) < (y) ? (x) : (y))
#define my_max(x, y)    ((x) > (y) ? (x) : (y))

#define MAX_WARN_COUNT 20

#ifdef CHECK
#define my_round(val, eps) { \
	REAL absv; \
        absv = ((val) < 0 ? -(val) : (val)); \
        if(absv < (eps)) \
          val = 0; \
	if(Warn_count < MAX_WARN_COUNT) \
	  { \
	    if(absv > 0.5 * (eps) && absv < 2 * (eps)) \
	      { \
		Warn_count++; \
		printf("%% Warning Value close to epsilon V: %e E: %e\n", \
		       (double)absv, (double)(eps)); \
		if(Warn_count == MAX_WARN_COUNT) \
		  { \
		    printf("%% *** Surpressing further rounding warnings\n"); \
		  } \
	      } \
	  } \
}

#else
#if 1
/* DMW - gcc does fabs inline without conditional jumps! */
#define my_round(val,eps) {if (fabs(val) < (eps)) val = 0;}
#else
#define my_round(val,eps) if (((val) < 0 ? -(val) : (val)) < (eps)) val = 0;
#endif
#endif


#define DEF_INFINITE  1e24 /* limit for dynamic range */
#define DEF_EPSB      5.01e-7 /* for rounding RHS values to 0 determine	
				 infeasibility basis */
#define DEF_EPSEL     1e-8 /* for rounding other values (vectors) to 0 */
#define DEF_EPSD      1e-6 /* for rounding reduced costs to zero */
#define DEF_EPSILON   1e-3 /* to determine if a float value is integer */
 
#define PREJ          1e-3  /* pivot reject (try others first) */

#ifndef REAL /* to allow -DREAL=<float type> while compiling */
#define REAL double
#endif

#define ETA_START_SIZE 10000 /* start size of array Eta. Realloced if needed */
#define FNAMLEN 64
#define NAMELEN 25
#define MAXSTRL (NAMELEN-1)
#define STD_ROW_NAME_PREFIX "r_"

#define CALLOC(ptr, nr)\
  if(!(ptr = calloc((size_t)(nr), sizeof(*ptr))) && nr) {\
    fprintf(stderr, "calloc of %d bytes failed on line %d of file %s\n",\
            nr * sizeof(*ptr), __LINE__, __FILE__);\
    exit(EXIT_FAILURE);\
  }

#define MALLOC(ptr, nr)\
  if(!(ptr = malloc((size_t)((nr) * sizeof(*ptr)))) && nr) {\
    fprintf(stderr, "malloc of %d bytes failed on line %d of file %s\n",\
            nr * sizeof(*ptr), __LINE__, __FILE__);\
    exit(EXIT_FAILURE);\
  }

#define REALLOC(ptr, nr)\
  if(!(ptr = realloc(ptr, (size_t)((nr) * sizeof(*ptr)))) && nr) {\
    fprintf(stderr, "realloc of %d bytes failed on line %d of file %s\n",\
            nr * sizeof(*ptr), __LINE__, __FILE__);\
    exit(EXIT_FAILURE);\
  }

#define MALLOCCPY(nptr, optr, nr)\
  {MALLOC(nptr, nr); memcpy(nptr, optr, (size_t)((nr) * sizeof(*optr)));}

#define MEMCPY(nptr, optr, nr)\
  memcpy(nptr, optr, (size_t)((nr) * sizeof(*optr)));

typedef char nstring[NAMELEN];

typedef struct _matrec
{
  int row_nr;
  REAL value;
} matrec;

typedef struct _column
{
  int            row;
  REAL           value;
  struct _column *next ;
} column;

typedef struct _constraint_name
{
  char                    name[NAMELEN];
  int                     row;
  struct _constraint_name *next;
} constraint_name;

typedef struct _bound
{
  REAL          upbo;
  REAL          lowbo;
} bound;

typedef struct _tmp_store_struct
{
  nstring name;
  int     row;
  REAL    value;
  REAL    rhs_value;
  short   relat;
} tmp_store_struct;

typedef struct _rside /* contains relational operator and rhs value */
{
  REAL          value;
  struct _rside *next;
  short         relat;
} rside;


/* fields indicated with ## may be modified directly */
/* pointers will have their array size in the comments */

typedef struct _lprec
{
  nstring   lp_name;		/* the name of the lp */

  short     verbose;            /* ## Verbose flag */
  short     print_duals;        /* ## PrintDuals flag for PrintSolution */
  short     print_sol;          /* ## used in lp_solve */
  short     debug;              /* ## Print B&B information */
  short     print_at_invert;    /* ## Print information at every reinversion */
  short     trace;              /* ## Print information on pivot selection */
  short     anti_degen;		/* ## Do perturbations */
  short     do_presolve;        /* perform matrix presolving */

  int	    rows;               /* Nr of constraint rows in the problem */
  int       rows_alloc;      	/* The allocated memory for Rows sized data */
  int       columns;            /* The number of columns (= variables) */
  int       columns_alloc;  
  int       sum;                /* The size of the variables + the slacks */
  int       sum_alloc;

  short     names_used;         /* Flag to indicate if names for rows and
				   columns are used */
  nstring   *row_name;		/* rows_alloc+1 */
  nstring   *col_name;		/* columns_alloc+1 */

 /* Row[0] of the sparce matrix is the objective function */

  int       non_zeros;          /* The number of elements in the sparce matrix*/
  int       mat_alloc;		/* The allocated size for matrix sized 
				   structures */
  matrec    *mat;               /* mat_alloc :The sparse matrix */
  int       *col_end;           /* columns_alloc+1 :Cend[i] is the index of the
		 		   first element after column i.
				   column[i] is stored in elements 
				   col_end[i-1] to col_end[i]-1 */
  int       *col_no;            /* mat_alloc :From Row 1 on, col_no contains the
				   column nr. of the
                                   nonzero elements, row by row */
  short     row_end_valid;	/* true if row_end & col_no are valid */
  int       *row_end;           /* rows_alloc+1 :row_end[i] is the index of the 
				   first element in Colno after row i */
  REAL      *orig_rh;           /* rows_alloc+1 :The RHS after scaling & sign
				  changing, but before `Bound transformation' */
  REAL      *rh;		/* rows_alloc+1 :As orig_rh, but after Bound 
				   transformation */
  REAL      *rhs;		/* rows_alloc+1 :The RHS of the current
				   simplex tableau */
  short     *must_be_int;       /* sum_alloc+1 :TRUE if variable must be 
				   Integer */
  REAL      *orig_upbo;         /* sum_alloc+1 :Bound before transformations */
  REAL      *orig_lowbo;	/*  "       "                   */
  REAL      *upbo;              /*  " " :Upper bound after transformation &
				   B&B work */
  REAL      *lowbo;             /*  "       "  :Lower bound after transformation
				   & B&B work */

  short     basis_valid;        /* TRUE is the basis is still valid */
  int       *bas;               /* rows_alloc+1 :The basis column list */
  short     *basis;             /* sum_alloc+1 : basis[i] is TRUE if the column
				   is in the basis */
  short     *lower;             /*  "       "  :TRUE if the variable is at its 
				   lower bound (or in the basis), it is FALSE
				   if the variable is at its upper bound */
  REAL	    *colsign;		/*  "       "  : colsign[i] = lower[i]?1:-1 */

  short     eta_valid;          /* TRUE if current Eta structures are valid */
  int       eta_alloc;          /* The allocated memory for Eta */
  int       eta_size;           /* The number of Eta columns */
  int       num_inv;            /* The number of real pivots */
  int       max_num_inv;        /* ## The number of real pivots between 
				   reinversions */
  REAL      *eta_value;         /* eta_alloc :The Structure containing the
				   values of Eta */
  int       *eta_row_nr;         /*  "     "  :The Structure containing the Row
				   indexes of Eta */
  int       *eta_col_end;       /* rows_alloc + MaxNumInv : eta_col_end[i] is
				   the start index of the next Eta column */

  short	    bb_rule;		/* what rule for selecting B&B variables */

  short     break_at_int;       /* TRUE if stop at first integer better than
                                   break_value */
  REAL      break_value;