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`
`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'
(
), 'E' (
), 'G' (
) 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
column come
first, then the entries for the
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.

2010-03-24