MIPdesc

One of the few internally defined data structures that the user has to deal with frequently is the MIPdesc data structure, which holds the data needed to describe a MILP. This data structure is used by SYMPHONY for two purposes. First, it is used to store the description of a generic MILP that is either read in from an MPS or AMPL file. More importantly, it is the data structure the user must use to pass the subproblem descriptions back to SYMPHONY at the time a new search tree node is created in the function user_create_subproblem(). The structure has 14 fields (listed below) that must be filled out to describe a subproblem (some fields are optional).

A subproblem is a mixed-integer program defined by a matrix of constraints, an objective function, bounds on both the right hand side values of the constraints and the variables, an array indicating which variables are integer, and (optionally) an array of column names that allows SYMPHONY to report the solution back in terms of column names instead of user indices. If the subproblem has n variables and m constraints, the constraints are given by a constraint coefficient matrix of size m $\times$ n (described in the next paragraph). The sense of each constraint, the right hand side values and bounds on the right hand side (called range) are vectors are of size m. The objective function coefficients and the lower and upper bounds on the variables are vectors of length n. The sense of each constraint can be either 'L' ( $\leq$), 'E' ( $=$), 'G' ( $\geq$) or 'R' (ranged). For non-ranged rows the range value is 0, for a ranged row the range value must be non-negative and the constraint means that the row activity level has to be between the right hand side value and the right hand side increased by the range value.

Since the coefficient matrix is very often sparse, only the nonzero entries are stored. Each entry of the matrix has a column index, a row index and a coefficient value associated with it. A matrix is specified in the form of the three arrays matval, matind, and matbeg. The array matval contains the values of the nonzero entries of the matrix in column order; that is, all the entries for the $0^{th}$ column come first, then the entries for the $1^{st}$ column, etc. The row index corresponding to each entry of matval is listed in matind (both of them are of length nz, the number of nonzero entries in the matrix). Finally, matbeg contains the starting positions of each of the columns in matval and matind. Thus, matbeg[i] is the position of the first entry of column i in both matval and matind). By convention matbeg is allocated to be of length n+1, with matbeg[n] containing the position after the very last entry in matval and matind (so it is very conveniently equal to nz). This representation of a matrix is known as a column ordered or column major representation. Below are listed the fields that must be filled out to describe a subproblem.

int n –

The number of columns.

int m –

The number of rows.

int nz –

The number of nonzeros.

double obj_offset –

Constant to be added to the objective function value when printed.

char obj_sense –

Objective sense (set to MAXIMIZE or MINIMIZE).

char *is_int –

Indicates which variables are required to be integer.

int *matbeg –

The array containing the starting positions for each column.

int *matind –

The array containing the indices for each column.

double *matval –

The array containing the matrix values for each column.

double *obj –

The objective function coefficients for the second objective (for multicriteria solve).

double *obj2 –

The objective function coefficients.

double *rhs –

The right hand side values for the constraints.

double *rngval –

The range values for the constraints (optional).

char *sense –

The senses of the constraints.

double *lb –

The lower bounds of the variables.

double *ub –

The upper bounds of the variables.

char **colname –

The column names.