2.3.4 Data structures

In this section we describe the data structures used in BiqCrunch heuristics, consisting of:

These structures can be modified in order to include additional information for a specific problem (or to increase the maximum problem size).


 
typedef struct Problem { 
   double *Q;  // Objective matrix in DENSE format 
   Sparse Qs; // Objective matrix in SPARSE format 
   int n; // size of Q 
   Sparse *As; // list of sparse matrices for the inequality constraints 
   double *a; // right-hand-side vector of inequality constraints 
   int mA; // number of inequality constraints 
   Sparse *Bs; // list of sparse matrices for the equality constraints 
   double *b; // right-hand-side vector of equality constraints 
   int mB; // number of equality constraints 
   int max_problem; // 1 if it is a max problem, and 0 if it is a min problem 
} Problem; 
 
typedef struct Inequality { 
   int i; 
   int j; 
   int k; 
   int type; 
   double value; 
   double y; 
} Inequality;  
Code 2.2: Problem data structure


 
typedef struct Sparse { 
   int *i; 
   int *j; 
   double *val; 
   int nnz; 
} Sparse;  
Code 2.3: Data structure of a sparse matrix


 
/* 
 * Maximum number of variables 
 */
 
#define NMAX 1024 
 
/* 
 * Solution of the problem. 
 * This structure defines the content of a solution of the problem. 
 */
 
typedef struct BobSolution { 
   /* 
    * Vector X. 
    * Binary vector that stores the solution of the branch-and-bound 
    * algorithm 
    */
 
   int X[NMAX]; 
} BobSolution;  
Code 2.4: Data structure of a solution


 
typedef struct BobNode { 
   /* 
    * Node information. 
    * 
    */
 
   BobTNdInfo BobNdInfo; // (int Size, int Off) 
   /* 
    * Number of fixed variables. 
    * Integer variable that stores the number of fixed variables in the 
    * current node. 
    */
 
   int level; 
   int xfixed[NMAX]; 
   BobSolution sol; 
   double fracsol[NMAX]; 
   BobTPri Pri; // (int Eval, int Depth) 
} BobNode;  
Code 2.5: Branch-and-bound tree node data structure