Back to SYMPHONY Home Page

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 n variables and mconstraints, the constraints are given by a constraint coefficient matrix of size m x 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. 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 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.

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.