bip_enum.h File Reference

BIP Enumerator Header. More...

Go to the source code of this file.

Typedefs
typedef struct binary_program	BIP

Functions
void	bip_init (void)
void	bip_free (BIP *bip)
	Deallocate BIP data structure. More...
BIP *	bip_read (const char *filename)
	Read a bip file. More...
void	bip_print (const BIP *bip, FILE *fp)
	Print Binary Program from BIP. More...
int	bip_enumerate (const BIP *bip, bool with_output)
	Enumerate all possible solution of a BIP. More...

Detailed Description

Author

Thorsten Koch

Date

20Nov2014

Definition in file bip_enum.h.

Typedef Documentation

typedef struct binary_program BIP

Definition at line 9 of file bip_enum.h.

Function Documentation

int bip_enumerate	(	const BIP *	bip,
		bool	with_output
	)

Prints all solutions.

Returns

number of feasible solutions found.

Definition at line 439 of file bip_enum.c.

{
   assert(bip_is_valid(bip));
   
   clock_t start = clock();
   int     solus = 0;
   int     count = 0;
   
   /* generate all permutation
    */
   for(unsigned long long bitvec = 0; bitvec < (1uL << bip->cols); bitvec++)
   {      
      unsigned long long mask = 1;  // long long because long is 32 bit on 32 bit computers
      double             x[BIP_MAX_COLS]; // having this always double is questionable

      assert(sizeof(bitvec) * 8 > BIP_MAX_COLS); //lint !e506
      
      /* construct solution vector
       */
      for(int j = 0; j < bip->cols; j++, mask <<= 1)
         x[j] = (bitvec & mask) ? 1.0 : 0.0; 

      if (bip_is_feasible(bip, &x[0])) //lint !e772 
      {
         if (with_output)
            print_solu(stdout, bip->cols, &x[0]);
         
         solus++;
      }
      count++;
   }
   assert((unsigned)count == (1u << bip->cols));
   
   double elapsed = GET_SEC(start, clock());
   
   printf("Checked %d vectors in %.3f s = %.3f kvecs/s\n",
      count, elapsed, count / elapsed / 1000.0);

   return solus;
}

void bip_free

(

BIP *

bip

)

Definition at line 133 of file bip_enum.c.

{
   assert(bip_is_valid(bip));

   mem_check(bip);
   
   free(bip);
}

void bip_init

(

void

)

Definition at line 91 of file bip_enum.c.

{
#if defined(USE_INT)

   max_coef_val = INT_MAX;
   min_coef_val = INT_MIN;
   int_coef     = true;
   
#elif defined(USE_LONGLONG) 

   max_coef_val = LLONG_MAX;
   min_coef_val = LLONG_MIN;
   int_coef     = true;

#elif defined(USE_FLOAT) 

   max_coef_val =  powf(10, (float)FLT_DIG);
   min_coef_val = -powf(10, (float)FLT_DIG);
   int_coef     =  false;

#elif defined(USE_DOUBLE)

   max_coef_val =  pow(10, (double)DBL_DIG);
   min_coef_val = -pow(10, (double)DBL_DIG);
   int_coef     =  false;

#elif defined(USE_LONGDOUBLE)

   max_coef_val =  powl(10, (long double)LDBL_DIG);
   min_coef_val = -powl(10, (long double)LDBL_DIG);
   int_coef     =  false;

#else
#error "No number type defined"
#endif   

   //   printf("Min/Max coefficient values [%.0Lf,%.0Lf]\n",
   //      (long double)min_coef_val, (long double)max_coef_val);
}

void bip_print	(	const BIP *	bip,
		FILE *	fp
	)

Definition at line 359 of file bip_enum.c.

{
   const char* sense[3] = { "<=", ">=", "==" };
      
   assert(NULL != fp);
   assert(bip_is_valid(bip));

   for(int r = 0; r < bip->rows; r++)
   {
      for(int c = 0; c < bip->cols; c++)
         fprintf(fp, "%Lf ", (long double)bip->a[r][c]);
      fprintf(fp, "%s %Lf\n", sense[bip->sense[r]], (long double)bip->b[r]);
   }
}

BIP* bip_read

(

const char *

filename

)

Format example:

4 # cols (variables) 3 # rows (constraints) 2 3 5 4 <= 8 3 6 0 8 <= 10 0 0 1 1 <= 1

comments (#) and empty lines are ignored.

Parameters

filename

name of file to read

Returns

ptr to BIP data structure

Definition at line 296 of file bip_enum.c.

{
   assert(NULL != filename);
   assert(0    <  strlen(filename));

   char      buf[MAX_LINE_LEN];
   char*     s;
   FILE*     fp;
   BIP*      bip   = calloc(1, sizeof(*bip));
   LFS*      lfs   = NULL;
   int       lines = 0;
   LINE_MODE mode  = READ_COLS;
   
   if (NULL == (fp = fopen(filename, "r")))
   {
      fprintf(stderr, "Can't open file %s\n", filename);
      free(bip);
      return NULL;
   }
   printf("Reading %s\n", filename);

   while(mode != READ_ERROR && NULL != (s = fgets(buf, sizeof(buf), fp)))
   {
      lines++;
      
      lfs  = lfs_split_line(lfs, s, "#");
      mode = process_line(mode, lfs, lines, bip);
   }
   fclose(fp);

   if (NULL != lfs)
      lfs_free(lfs);
   
   if (READ_ERROR == mode)
   {
      free(bip);

      return NULL;
   }
   if (bip->cols == 0 || bip->max_rows == 0 || bip->rows < bip->max_rows)
   {
      fprintf(stderr, "Error: unexpected EOF\n");
      free(bip);
      return NULL;
   }
   
   assert(bip->rows == bip->max_rows);

   assert(bip_is_valid(bip));
   
   printf("Read %d rows, %d cols\n", bip->rows, bip->cols);

   if (bip_can_overflow(bip))
   {
      bip_free(bip);

      return NULL;
   }   
   return bip;
}