lpkit.h

利用c语言编写

#define REALLOC(ptr, nr)\
  ((((nr) == 0) || ((ptr = realloc(ptr, (size_t)((nr) * sizeof(*ptr)))) == NULL)) ? \
   (void *) report(NULL, CRITICAL, "realloc of %d bytes failed on line %d of file %s",\
           (nr) * sizeof(*ptr), __LINE__, __FILE__), (ptr = (void *) 0) : \
   ptr\
  )

#define FREE(ptr) if (ptr != NULL) {free(ptr), ptr = NULL;} else

#define MALLOCCPY(nptr, optr, nr)\
  (MALLOC(nptr, nr),(nptr != NULL) ? memcpy(nptr, optr, (size_t)((nr) * sizeof(*optr))) : 0, nptr)

#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 */
{
  int           row;
  REAL          value;
  REAL          range_value;
  struct _rside *next;
  short         relat;
  short         range_relat;
} rside;

/* SOS storage structure */

#define LINEARSEARCH 0

typedef struct _SOSrec
{
  int   tagorder;
  char  *name;
  short type;
  int   size;
  int   priority;
  int   *members;
  REAL  *weights;
  int   *membersSorted;
  int   *membersMapped;
} SOSrec;

/* Prototypes for call-back functions*/
typedef int WINAPI abortfunc(void *lp, void *userhandle);
typedef void WINAPI logfunc(void *lp, void *userhandle, char *buf);
typedef void * WINAPI msgfunc(void *lp, void *userhandle, int message);

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

typedef struct _lprec
{
  char      *lp_name;   	/* the name of the lp */
  short     verbose;            /* ## Verbose flag */
  MYBOOL    print_duals;        /* ## Set TRUE to print duals in PrintSolution */
  MYBOOL    print_sol;          /* ## Set TRUE to print optimal solution */
  MYBOOL    debug;              /* ## Set TRUE to print extra debug information */
  short     print_at_invert;    /* ## Print information at every reinversion */
  MYBOOL    trace;              /* ## Print information on simplex progression */
  MYBOOL    anti_degen;	    	/* ## Set TRUE to do perturbations to avoid cycling */
  MYBOOL    do_presolve;        /* ## Set TRUE to 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;

  MYBOOL    names_used;         /* Flag to indicate if names for rows and columns are used */

  char      **row_name;		/* rows_alloc+1 */
  char      **col_name;		/* columns_alloc+1 */

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

  int       non_zeros;          /* The number of elements in the sparse 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 */
  MYBOOL    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 */
  RREAL     *rhs;	        /* rows_alloc+1 :The RHS of the current simplex tableau */
  MYBOOL    *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 */

  MYBOOL    basis_valid;        /* TRUE is the basis is still valid */
  int       *bas;               /* rows_alloc+1 :The basis column list */
  MYBOOL    *basis;             /* sum_alloc+1 : basis[i] is TRUE if the column is in the basis */
  MYBOOL    *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 */

  MYBOOL    eta_valid;          /* TRUE if current Eta structures are valid */
  int       eta_alloc;          /* The allocated memory for Eta non-zero values */
  int       eta_size;           /* The number of Eta columns */
  int       num_inv;            /* Number of pivots since last refactorization */
  int       max_num_inv;        /* ## Number of pivots between reinversions of the ETA matrix */
  REAL      *eta_value;         /* eta_alloc : Structure containing values of Eta */
  int       *eta_row_nr;        /*  "     "  : Structure containing row indexes of Eta */
  int       *eta_col_end;       /* rows_alloc + MaxNumInv : eta_col_end[i] is
                		   the start index of the next Eta column */

  MYBOOL    bb_rule;            /* ## Set rule for selecting B&B variables:
                                      FIRST_SELECT : Lowest indexed non-integer column
                                      RAND_SELECT  : Random non-integer column
                                      WORST_SELECT : Largest deviation from an integer value
                                      MEDIAN_SELECT: Median value deviation from an integer value */

  REAL      obj_bound;          /* ## Set initial "at least better than" guess for objective function
                                   (can in particular speed up B&B iterations) */
  int       iter;               /* Number of iterations in the simplex solver (LP) */
  int       total_iter;         /* Number of iterations (B&B) (Integer LP) */
  int       max_level;          /* The Deepest B&B level of the last solution */
  int	    total_nodes;        /* Total number of nodes processed in B&B */
  REAL      *solution;          /* sum_alloc+1 : Solution array of the next to optimal LP,
                                   Index   0           : Objective function value,
                                   Indeces 1..rows     : Slack variable values,
                		   Indeced rows+1..sum : Variable values */
  REAL      *best_solution;     /* sum_alloc+1 : Solution array of optimal 'Integer' LP,
                                   structured as the solution array above */
  REAL      *duals;             /* sum_alloc+1 :The dual variables/reduced costs of the last LP */

  MYBOOL    maximise;           /* TRUE if the goal is to maximise the objective function */
  MYBOOL    floor_first;        /* FALSE: B&B does ceiling bound first
                                   TRUE:  B&B does floor bound first
                                   AUTOMATIC: B&B desides which branch to take first */
  MYBOOL    *ch_sign;           /* rows_alloc+1 :TRUE if the Row in the matrix has changed sign
                                   (a`x > b, x>=0) is translated to
	          		    s + -a`x = -b with x>=0, s>=0) */

  MYBOOL    scaling_used;       /* TRUE if scaling is used */
  MYBOOL    columns_scaled;     /* TRUE if the columns are scaled too, Only use
                	 	   if all variables are non-integer */
  REAL      *scale;             /* sum_alloc+1:0..Rows the scaling of the Rows,
                		   Rows+1..Sum the scaling of the columns */

  int	    nr_lagrange;        /* Nr. of Langrangian relaxation constraints */
  REAL	    **lag_row;	        /* NumLagrange, columns+1:Pointer to pointer of rows */
  REAL      *lag_rhs;	        /* NumLagrange :Pointer to pointer of Rhs */
  REAL      *lambda;	        /* NumLagrange :Lambda Values */
  MYBOOL    *lag_con_type;      /* NumLagrange :TRUE if constraint type EQ */
  REAL      lag_bound;	        /* The Lagrangian lower bound */

  MYBOOL    valid;	        /* Has this lp pased the 'test' */
  REAL      infinite;           /* ## limit for dynamic range */
  REAL      epsilon;            /* ## to determine if a float value is integer */
  REAL      epsb;               /* ## for rounding RHS values to 0/infeasibility */
  REAL      epsd;               /* ## for rounding reduced costs to zero */
  REAL      epsel;              /* ## for rounding other values (vectors) to 0 */
  hashstruct *rowname_hashtab;  /* hash table to store row names */
  hashstruct *colname_hashtab;  /* hash table to store column names */

  REAL      *dualsfrom;         /* sum_alloc+1 :The sensitivity on dual variables/reduced costs of the
                		   last LP */
  REAL      *dualstill;         /* sum_alloc+1 :The sensitivity on dual variables/reduced costs of the
                		   last LP */
  REAL      *objfrom;           /* columns_alloc+1 :The sensitivity on object function of the
		                   last LP */
  REAL      *objtill;           /* columns_alloc+1 :The sensitivity on object function of the
                                   last LP */

  int       orig_rows;          /* Number of actual problem rows before deletions */
  int       orig_columns;       /* Number of actual problem columns before working columns */
  short     spx_status;         /* Simplex solver feasibility/mode code */
  short     lag_status;         /* Extra status variable for lag_solve */
  int       solutioncount;      /* number of equal-valued solutions found (up to solutionlimit) */
  int       solutionlimit;      /* upper number of equal-valued solutions kept track of */
  int       num_refact;         /* Number of times the basis was refactored */
  MYBOOL    scalemode;          /* ## Set 0 for max-min, 1 for geometric */
  MYBOOL    improve;            /* ## Set to non-zero for iterative improvement */
  MYBOOL    lag_trace;          /* ## Print information on Lagrange progression */
  MYBOOL    piv_rule;           /* ## Set rule for selecting row and column entering/leaving */
  MYBOOL    break_at_first;     /* ## Set TRUE to stop at first feasible solution */
  short     bb_floorfirst;      /* ## Set TRUE for B&B to set variables to floor bound first;
                                      conversely with FALSE, the ceiling value is set first */
  REAL      break_at_value;     /* ## Set value for the objective function deemed
                                      to be sufficiently good in an integer problem */
  int       int_count;          /* Number of integers required */
  int       *var_is_free;       /* columns+1: Index of twin variable if variable is free */

  REAL      Extrad;
  MYBOOL    doIterate;          /* Perform iteration at next opportunity */
  MYBOOL    doInvert;           /* Force basis reinversion immediateluy */
  MYBOOL    justInverted;       /* The basis was recently reinverted */
  MYBOOL    wasprocessed;       /* The solve preprocessing was performed */

  MYBOOL    Break_bb;           /* Solver working variable */
  int       Level;              /* Solver B&B working variable (recursion depth) */

  REAL      lag_accept;         /* The Lagrangial convergence acceptance criterion */

  REAL      negrange;           /* ## limit for negative variable range */

  REAL      epsperturb;         /* ## perturbation scalar */

  REAL	    epspivot;           /* ## Pivot reject tolerance (try others first) */

  /* Time/timer variables */
  long      sectimeout;
  double    timestart;
  double    timeend;
  double    time_refactstart;   /* Time since start of last refactorization-pivots cyle */

  /* Message processing callbacks */
  abortfunc *abort;
  void      *aborthandle;
  logfunc   *writelog;
  void      *loghandle;
  logfunc   *debuginfo;
  msgfunc   *usermessage;
  int       msgmask;
  void      *msghandle;
#if 0
  int       *var_to_orig;       /* sum_alloc+1 : Mapping of variables from solution to
				   best_solution to account for removed variables and
				   rows during presolve; a non-positive value indicates
                                   that the constraint or variable was removed */
  int       *orig_to_var;
#endif
  int       sc_count;           /* Number of semi-continuous variables */
  int       sos_alloc;          /* Size allocated to specially ordered sets (SOS1, SOS2...) */
  int       sos_count;          /* Number of specially ordered sets (SOS1, SOS2...) */
  int       sos_ints;           /* Number of integers in SOS'es above */
  REAL      *var_is_sc;         /* sum_columns+1 : TRUE if variable is semi-continuous;
                                   value replaced by conventional lower bound during solve */
  SOSrec    **sos_list;         /* Array of pointers to SOS lists */
  int       sos_vars;           /* Number of variables in the sos_nodes list */
  int       *sos_priority;      /* Priority-sorted list of variables (no duplicates) */
} lprec;



/* function interface for the user */

void lp_solve_version(int *majorversion,
                      int *minorversion,
                      int *release,
                      int *build);
void set_magic(int code, int param);

lprec *make_lp(int rows, int columns);
/* create and initialise a lprec structure
   defaults:
   Empty (Rows * Columns) matrix,
   Minimize the objective function
   constraints all type <=
   Upperbounds all Infinite
   no integer variables
   floor first in B&B
   no scaling
   default basis */

lprec *read_LP(char *input, short verbose, char *lp_name);
lprec *read_lp_file(FILE *input, short verbose, char *lp_name);
/* create and read an .lp file from input (input must be open) */

void delete_lp(lprec *lp);
/* Remove problem from memory */

lprec *copy_lp(lprec *lp);
/* copy a lp structure */

int set_mat(lprec *lp, int row, int column, REAL value);
/* fill in element (Row,Column) of the matrix
   Row in [0..Rows] and Column in [1..Columns] */

int set_obj_fn(lprec *lp, REAL *row);
/* set the objective function (Row 0) of the matrix */
int str_set_obj_fn(lprec *lp, char *row);
/* The same, but with string input */

int add_constraint(lprec *lp, REAL *row, short constr_type, REAL rh);
/* Add a constraint to the problem,
   row is the constraint row,
   rh is the right hand side,
   constr_type is the type of constraint (LE (<=), GE(>=), EQ(=)) */
int str_add_constraint(lprec *lp, char *row_string ,short constr_type, REAL rh);