Next: user_get_upper_bounds Up: User-written functions of the Previous: user_free_lp

### user_create_lp

int user_create_lp(void *user, int varnum, var_desc **vars, int
numrows, int cutnum, cut_data **cuts, int *nz,
int **matbeg, int **matind, double **matval,
double **obj, double **rhs, char **sense,
double **rngval, int *maxn, int *maxm,
int *maxnz, int *allocn, int *allocm, int *allocnz)


Description:

Based on the instance data contained in the user data structure and the list of cuts and variables that are active in the current subproblem, the user has to create the initial LP relaxation for the search node. The matrix of the LP problem must contain the variables whose user indices are listed in vars (in the same order) and at least the base constraints.

An LP is defined by a matrix of constraints, an objective function, and bounds on both the right hand side values of the constraints and on the variables. If the problem has variables and constraints, the constraints are given by a constraint coefficient matrix of size (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 . The objective function coefficients and the lower and upper bounds on the variables are vectors of length . 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. An LP 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 , 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 in both *matval and *matind). By convention *matbeg is allocated to be of length , with (*matbeg)[n] containing the position after the very last entry in *matval and *matind (so it is very conveniently equal to ). This representation of a matrix is known as a column ordered or column major representation.

The arrays that are passed in can be overwritten and have already been previously allocated for the lengths indicated (see the description of arguments below). Therefore, if they are big enough, the user need not reallocate them. If the max lengths are not big enough then she has to free the corresponding arrays and allocate them again. In this case she must return the allocated size of the array to avoid further reallocation. If the user plans to utilize dynamic column and/or cut generation, arrays should be allocated large enough to allow for reasonable growth of the matrix or unnecessary reallocations will result. In order to accommodate *maxn variables, arrays must be allocated to size *allocn = *maxn + *maxm +1 and *allocnz = *maxnz + *maxm because of the extra space required by the LP solver for slack and artificial variables.

Arguments:

 void *user IN Pointer to the user-defined LP data structure. int varnum IN Number of variables in the relaxation (base and extra). var_desc **vars IN An array of length n containing the user indices of the active variables (base and extra). int rownum IN Number of constraints in the relaxation (base and extra). int cutnum IN Number of extra constraints. cut_data **cuts IN Packed description of extra constraints. int *nz OUT Pointer to the number of nonzeros in the LP. int **matbeg INOUT Pointers to the arrays that describe the LP problem (see description above. int **matind INOUT double **matval INOUT double **obj INOUT double **rhs INOUT char **sense INOUT double **rngval INOUT int *maxn INOUT The maximum number of variables. int *maxm INOUT The maximum number of constraints. int *maxnz INOUT The maximum number of nonzeros. int *allocn INOUT The length of the *matbeg and *obj arrays (should be *maxm + *maxn +1). int *allocm INOUT The length of the *rhs, *sense and *rngval arrays. int *allocnz INOUT The length of the *matval and *matind arrays (should be *maxnz + *maxm.

Return values:

 ERROR Error. The LP process is aborted. USER_AND_PP Post-processing will be skipped, the user added the constraints corresponding to the cuts. USER_NO_PP User created the matrix with only the base constraints.

Post-processing:

The extra constraints are added to the matrix by calling the user_unpack_cuts() subroutine and then adding the corresponding rows to the matrix. This is easier for the user to implement, but less efficient than adding the cuts at the time the original matrix was being constructed.

Wrapper invoked from:
process_chain() which is invoked when setting up a the initial search node in a chain.

Next: user_get_upper_bounds Up: User-written functions of the Previous: user_free_lp
Ted Ralphs
2003-05-29