Xpress Appendix A: Difference between revisions

From TomWiki
Jump to navigationJump to search
No edit summary
No edit summary
 
Line 126: Line 126:
|}
|}


<figtable id="tab:callbackFunctions">
====Table: Callback functions.====
 
{|class="wikitable"
{|class="wikitable"
|+<caption>Callback functions.</caption>
|-valign="top"
!Index||m-file||Description
!Index||m-file||Description
|-valign="top"
|-valign="top"
Line 162: Line 161:
|(15)||vxpcb_TCM||User Defined Top Cut Manager Routine
|(15)||vxpcb_TCM||User Defined Top Cut Manager Routine
|}
|}
</figtable>


====Description of Outputs====
====Description of Outputs====

Latest revision as of 13:28, 22 January 2012

Notice.png

This page is part of the Xpress Manual. See Xpress Manual.

The Matlab Interface Routines - Main Routines

xpress

Purpose

XpressMP mixed-integer linear and quadratic programming (MILP, MIQP) and linear and quadratic programming (LP, QP) interface. Xpress MP solves problems of the form

where , , and . The variables , the index subset of , are restricted to be integers.

Calling Syntax

[x, slack, v, rc, f k, ninf, sinf,  Inform, basis, lpiter,  glnodes] = xpress(c, A, x L, x U, b L, b U, xpcontrol, callback, PriLev, Prob, IntVars, 
                                                                              PI, SC, SI, sos1, sos2, F, LogFile, SaveFile, SaveMode, iisRequest, iisFile, saRequest);

Description of Inputs

Problem description structure. The following fields are used:

c Linear objective function cost coefficients, vector n × 1.
F Square dense or sparse matrix. Empty if non-quadratic problem.
A Linear constraint matrix for linear constraints, dense or sparse matrix m × n.
x_L Lower bounds on design parameters x. If empty assumed as zero.
x_U Upper bounds on design parameters x.
b_L Lower bounds on the linear constraints.
The following parameters are optional:
b_U Upper bounds on the linear constraints. If empty, then bU = bL assumed.
xpcontrol Structure, where the fields are set to the Xpress M P control parameters that the user wants to specify values for. The control parameters are listed in Section 7 in the Xpress-Optimizer Reference Manual. The prefix XPRS is not used.
callback Logical vector defining which callbacks to use in Xpress M P. If the ith entry of the logical vector callback is set, the corresponding callback is defined. The callback calls the m-file specified in Table below. The user may edit this file, or make a new copy, which is put in a directory that is searched before the xpress directory in the Matlab path.
PriLev Printing level in the xpress m-file and the Xpress MP C-interface.

= 0 Silent

= 1 Summary information

= 2 More detailed information

Prob A structure. If TOMLAB calls xpress, then Prob is the standard TOMLAB problem structure, otherwise the user optionally may set: Prob.P = ProblemNumber; , where ProblemNumber is some integer. If any callback is defined then problem arrays are set as fields in Prob, and the Prob structure is always passed to the callback routines as the last parameter. The defined fields are Prob.c, Prob.x_L, Prob.x_U, Prob.A, Prob.b_L, Prob.b_U and Prob.QP.F. If the input structure is empty ([ ]), then Prob.P = 1 is set. If Prob.MIP.KNAPSACK = 1 and callback == 1, then the simple heuristic in xpcb_GL is used. If callback(9) is set, and Prob.MIP.KNAPSACK, or Prob.MIP is undefined, xpress is setting Prob.MIP.KNAPSACK = 0, to avoid the call to the heuristic.
IntVars Defines which variables are integers, of the general type I or binary B. Variable indices should be in the range [1,...,n]. If IntVars is a logical vector then all variables i where IntVars(i) > 0 are defined to be integers. If IntVars is determined to be a vector of indices then x(IntVars) are defined as integers. If the input is empty ([ ]), then no integers of type I or B are defined. The interface routine xpress checks which of the integer variables have lower bound xL = 0 and upper bound xU = 1, i.e. are binary 0/1 variables.
PI Integer variables of type Partially Integer (PI), i.e. takes an integer value up to a specified limit, and any real value above that limit. PI must be a structure array where:

PI.var is a vector of variable indices in the range [1, ..., n].

PI.lim is a vector of limit values for each of the variables specified in PI.var, i.e. for variable i, that is the PI variable with index j in P I .var, then x(i) takes integer values in [xL (i), P I .lim(j)] and continuous values in [PI.lim(j), xU (i)].

SC A vector with indices for the integer variables of type Semi-continuous (SC), i.e. that takes either the value 0 or a real value in the range [xL (i), xU (i)], assuming for some j, that i = SC (j), where i is an variable number in the range [1, ..., n].
SI A vector with indices for the integer variables of type Semi-integer (SI), i.e. that takes either the value 0 or an integer value in the range [xL (i), xU (i)], assuming for some j, that i = SI (j), where i is an variable number in the range [1, ..., n].
sos1 A structure defining the Special Ordered Sets of Type One (sos1). Assume there are k sets of type sos1, then sos1(k).var is a vector of indices for variables of type sos1 in set k. sos1(k).row is the row number for the reference row identifying the ordering information for the sos1 set, i.e. A(sos1(k).row,sos1(k).var) identifies this information. As ordering information, also the objective function coefficients c could be used. Then as row number, 0 is instead given in sos1(k).row.
sos2 A structure defining the Special Ordered Sets of Type Two (sos2). Specified exactly as sos1 sets, see sos1 input variable description.
LogFile File to write Xpress-MP log output to. Default is empty " in which case nothing is written.

Please note that Xpress-MP appends it's output to the log file.

SaveFile Filename for writing the problem prior to calling the Xpress-MP solver. If empty, no file is written. The type of output is determined by the SaveMode parameter. Xpress-MP will always add an extension to the filename given here. The extension depends on the SaveMode chosen, see below.
SaveMode Character string with any combination of the following character flags:

p - full precision of numerical values. o - one element per line.

n - scaled.

s - scrambled vector names. l - output in LP format.

The extension added to the SaveFile name is .mat, unless the 'l' flag is used in which case the extension is .lp.

iisRequest Flag indicating whether to compute an IIS and return it to MATLAB. This option can only be set for an LP problem. If an IIS is found, XPRESS automatically changes the problem to make it feasible and reoptimizes it.

= 0, Don't return IIS to MATLAB (default).

= 1, Compute IIS and return it to MATLAB if an LP problem has been proven infeasible. The IIS is returned through the output parameter 'iis'.

iisFile Flag indicating whether to write a file describing the IIS set or not. If is set to 1, a file: LPprob.iis will be written. Otherwise, no file is written..
saRequest Structure telling whether and how you want XPRESS to perform a sensitivity analysis (SA).

You can complete an SA on the objective function and right hand side vector. The saRequest structure contains two sub structures:

.obj and .rhs

They have one field each:

.index

In case of .obj.index, .index contains the indices of the columns whose objective function coefficients sensitivity ranges are required.

In case of .rhs.index, .index contains the indices of the rows whose RHS coefficients sensitivity ranges are required.

In both cases, the .index array has to be sorted, ascending.

To get an SA of objective function on the four variables 120 to 123 (included) and variable

6 the saRequest structure would look like this:

saRequest.obj.index = [6 120 121 122 123];

The result is returned through the output parameter 'sa'.

Table: Callback functions.

Index m-file Description
(1) xpcb_USN User Select Node Callback
(2) xpcb_UPN User Preprocess Node Callback
(3) xpcb_UON User Optimal Node Callback
(4) xpcb_UIN User Infeasible Node Callback
(5) xpcb_UIS User Integer Solution Callback
(6) xpcb_UCN User Node Cut-off Callback
(7) xpcb_UCB User Choose Branching Variable Callback
(8) xpcb_IL Simplex Log Callback
(9) xpcb_GL Global Log Callback
(10) xpcb_BL Barrier Log Callback
(11) xpcb_UOP User Output Callback
(12) xpcb_CMI User Defined Cut Manager Init Routine
(13) xpcb_CMS User Defined Cut Manager Termination Routine
(14) xpcb_CM User Defined Cut Manager Routine
(15) vxpcb_TCM User Defined Top Cut Manager Routine

Description of Outputs

The following fields are used:

Output Description
x Solution vector x with decision variable values (n × 1 vector).
slack Slack variables (m × 1 vector).
v Lagrangian multipliers (dual solution vector) (m × 1 vector).
rc Reduced costs. Lagrangian multipliers for simple bounds on x.
f_k Objective function value f (x) = cT * x at optimum.
ninf Number of infeasibilities.
sinf Sum of infeasibilities.
Inform Result of XpressM P run:
0 Optimal solution found.
2 Unbounded solution.
4 Infeasible problem.
5 Some error occurred.

See the XpressMP problem attributes XPRS LPSTATUS (for LP and QP) and XPRS MIPSTATUS (for MILP and MIQP) for more exact information. They are available in the global variable xpProblemAttrib.

basis Basis status of constraints and variables, (m + n × 1 vector).
lpiter Number of simplex iterations.
glnodes Number of nodes visited.
iis Structure containing IIS information (niis x 1). niis is the number of IISs found (see MAXIIS parameter). The fields:
iisStatus Status flag. (Only set in the first element of the iis array.) Possible values:

2 = IIS was written to file LPprob.iis.

1 = IIS was obtained.

-1 = Problem was infeasible but no IIS found.

-2 = Problem was not infeasible.

iisMessage Error message on error. (Only set in the first element of the iis array.)
colind The column indices of the IIS set.
rowind The row indices of the IIS set.
sa Structure with information about the requested SA, if requested. The fields:
obj Ranges for the variables in the objective function.
rhs Ranges for the right hand side values.
These fields are structures themselves. All four structures have identical field names:
status Status of the SA operation. Possible values:

1 = Successful.

0 = SA not requested.

-1 = Error: MIP problem was presolved.

lower The lower range.
upper The upper range.

Global Parameters Used

Parameter Description
xpControlVariables Structure with all XpressMP control variables listed in Section 7 in the Xpress-Optimizer Reference Manual. Available with fresh variables in each callback, and after the optimization.
xpProblemAttrib Structure with all XpressMP problem attributes listed in Section 8 in the Xpress-Optimizer Reference Manual. Available with fresh values in each callback, and after the optimization.

Description

The interface routine xpress calls Xpress MP to solve LP, QP, MILP and MIQP problems. The matrix A is transformed in xpress.m to the Xpress MP sparse matrix format. Error checking is made on the lengths of the vectors and matrices.

xpressTL

Purpose

The TOMLAB /Xpress MILP, MIQP, LP and QP Interface. It solves linear programming (LP), quadratic programming (QP), mixed integer linear programming (MILP) and mixed integer quadratic programming problems (MIQP). xpressTL solves problems of the form

where , and . The variables , the index subset of , are restricted to be integers.

Calling Syntax

Prob = ProbCheck(Prob, 'xpress'); 
Result = xpressTL(Prob);

Description of Inputs

Prob, the problem structure. The following fields are used:

Field Description
QP.c Linear objective function cost coefficients, vector n × 1.
QP.F Square n × n dense or sparse matrix. Empty if non-quadratic problem.
A Linear constraint matrix for linear constraints, dense or sparse m × n matrix.
x_L Lower bounds on design parameters x. If empty assumed to be -I nf .
x_U Upper bounds on design parameters x. If empty assumed to be I nf .
b_L Lower bounds on the linear constraints.
b_U Upper bounds on the linear constraints.
PriLev Printing level in the xpress m-file and the XpressM P C-interface.

= 0 Silent

= 1 Summary information

= 2 More detailed information

MIP.IntVars Defines which variables are integers, of the general type I or binary B. Variable indices should be in the range [1,...,n]. If IntVars is a logical vector then all variables i where I ntV ars(i) > 0 are defined to be integers. If IntV ars is determined to be a vector of indices then x(IntVars) are defined as integers. If the input is empty ([ ]), then no integers of type I or B are defined. The interface routine xpress checks which of the integer variables have lower bound xL = 0 and upper bound xU = 1, i.e. are binary 0/1 variables.
MIP.PI Integer variables of type Partially Integer (PI), i.e. takes an integer value up to a specified limit, and any real value above that limit. PI must be a structure array where:

PI.var is a vector of variable indices in the range [1, ..., n].

PI.lim is a vector of limit values for each of the variables specified in PI.var, i.e. for variable i, that is the PI variable with index jin P I .var, then x(i) takes integer values in [xL (i), P I .lim(j)] and continuous values in [P I .lim(j), xU (i)].
MIP.SC A vector with indices for the integer variables of type Semi-continuous (SC), i.e. that takes either the value 0 or a real value in the range [xL (i), xU (i)], assuming for some j, that i = SC (j), where i is an variable number in the range [1, ..., n].
MIP.SI A vector with indices for the integer variables of type Semi-integer (SI), i.e. that takes either the value 0 or an integer value in the range [xL (i), xU (i)], assuming for some j, that i = SI (j), where i is an variable number in the range [1, ..., n].
MIP.sos1 A structure defining the Special Ordered Sets of Type One (sos1). Assume there are k sets of type sos1, then sos1(k).var is a vector of indices for variables of type sos1 in set k. sos1(k).row is the row number for the reference row identifying the ordering information for the sos1 set, i.e. A(sos1(k).row,sos1(k).var) identifies this information. As ordering information, also the objective function coefficients c could be used. Then as row number, 0 is instead given in sos1(k).row.
MIP.sos2 A structure defining the Special Ordered Sets of Type Two (sos2). Specified exactly as sos1 sets, see M I P.sos1 input variable description.
MIP.KNAPSACK True if a knapsack problem is to be solved and a knapsack heuristic is to be used. Also MIP.callback(9) = 1 must be set if the heuristic is to be executed.
MIP.xpcontrol Structure, where the fields are set to the XpressM P control parameters that the user wants to specify values for. The control parameters are listed in Section 7 in the Xpress-Optimizer Reference Manual. The prefix XPRS is not used.
MIP.callback Logical vector defining which callbacks to use in XpressM P . If the ith entry of the logical vector callback is set, the corresponding callback is defined. The callback calls the m-file specified in the Table 12 below. The user may edit this file, or make a new copy, which is put in a directory that is searched before the xpress directory in the Matlab path.
optParam Structure with special fields for optimization parameters

Fields used are: MaxIter - Maximal number of iterations or node visits.

XPRESS.LogFile File to write Xpress-MP log output to. Default is empty " in which case nothing is written.

Please note that Xpress-MP appends it's output to the log file.

XPRESS.SaveFile Filename for writing the problem prior to calling the Xpress-MP solver. If empty, no file is written. The type of output is determined by the SaveMode parameter. Xpress-MP will always add an extension to the filename given here. The extension depends on the SaveMode chosen, see below.
XPRESS.SaveMode Character string with any combination of the following character flags:

p - full precision of numerical values. o - one element per line.

n - scaled.

s - scrambled vector names. l - output in LP format.

The extension added to the SaveFile name is .mat, unless the 'l' flag is used in which case the extension is .lp.

iis Flag indicating whether to compute an IIS and return it to MATLAB. This option can only be set for an LP problem. If an IIS is found, XPRESS automatically changes the problem to make it feasible and reoptimizes it.

= 0, Don't return IIS to MATLAB (default).

= 1, Compute IIS and return it to MATLAB if an LP problem has been proven infeasible. The IIS is returned through the output parameter 'iis'.

iisFile Flag indicating whether to write a file describing the IIS set or not. If is set to 1, a file: LPprob.iis will be written. Otherwise, no file is written.
sa Structure telling whether and how you want XPRESS to perform a sensitivity analysis (SA).

You can complete an SA on the objective function and right hand side vector. The saRequest structure contains two sub structures:

.obj and .rhs

They have one field each:

.index

In case of .obj.index, .index contains the indices of the columns whose objective function coefficients sensitivity ranges are required.

In case of .rhs.index, .index contains the indices of the rows whose RHS coefficients sensitivity ranges are required.

In both cases, the .index array has to be sorted, ascending.

To get an SA of objective function on the four variables 120 to 123 (included) and variable

6 the saRequest structure would look like this:

saRequest.obj.index = [6 120 121 122 123];

The result is returned through the output parameter 'sa'.

Callback functions.
Index m-file Description
(1) xpcb_USN User Select Node Callback
(2) xpcb_UPN User Preprocess Node Callback
(3) xpcb_UON User Optimal Node Callback
(4) xpcb_UIN User Infeasible Node Callback
(5) xpcb_UIS User Integer Solution Callback
(6) xpcb_UCN User Node Cut-off Callback
(7) xpcb_UCB User Choose Branching Variable Callback
(8) xpcb_IL Simplex Log Callback
(9) xpcb_GL Global Log Callback
(10) xpcb_BL Barrier Log Callback
(11) xpcb_UOP User Output Callback
(12) xpcb_CMI User Defined Cut Manager Init Routine
(13) xpcb_CMS User Defined Cut Manager Termination Routine
(14) xpcb_CM User Defined Cut Manager Routine
(15) xpcb_TCM User Defined Top Cut Manager Routine

Description of Outputs

Result structure. The following fields are used:

Output Description
Iter Number of iterations, or nodes visited.
ExitFlag 0: OK.

1: Maximal number of iterations reached.

2: Unbounded feasible region.

4: No feasible point found.

5: Error of some kind.

Inform If a MIP problem the control variable XPRS MIPSTATUS (xpControlVariables.MIPSTATUS) else XPRS LPSTATUS (xpControlVariables.LPSTATUS).
x_0 Initial starting point not known, set as empty.
QP.B Optimal active set, basis vector, in TOMLAB QP standard.

B(i) = 1: Include variable x(i) is in basic set.

B(i) = 0: Variable x(i) is set on its lower bound.

B(i) = -1: Variable x(i) is set on its upper bound.

f_k Function value at optimum, f (xk ).
g_k Gradient value at optimum, c or c + F * x.
x_k Optimal solution vector xk .
v_k Lagrangian multipliers (for bounds and dual solution vector). Set as vk = [rc; v], where rc is the n-vector of reduced costs and v holds the m dual variables.
xState State of each variable.

0 = nonbasic (on x_L), 1 = nonbasic (on x_U), 2 = superbasic (between bounds), 3 = basic

(between bounds)

bState State of each constraint.

0 = nonbasic (on b L), 1 = nonbasic (on b U), 2 = superbasic (between bounds), 3 = basic

(between bounds)

Solver Solver used - XpressM P.
SolverAlgorithm Solver algorithm used.
FuncEv Number of function evaluations. Set to Iter. GradEv Number of gradient evaluations. Set to Iter. ConstrEv Number of constraint evaluations. Set to Iter. Prob Problem structure used.
MIP.ninf Number of infeasibilities.
MIP.sinf Sum of infeasibilities.
MIP.slack Slack variables (m × 1 vector).
MIP.lpiter Number of LP iterations.
MIP.glnodes Number of nodes visited.
MIP.basis Basis status of constraints and variables (m + n × 1 vector) in the XpressMP format, fields xState and bState has the same information in the Tomlab format.
MIP.xpControlVariables Structure with all XpressM P control variables listed in Section 7 in the Xpress-Optimizer eference Manual [1].
MIP.xpProblemAttrib Structure with all XpressM P problem attributes listed in Section 8 in the Xpress-Optimizer Reference Manual [1].
XPRESS.iis Structure containing IIS information (niis x 1). niis is the number of IISs found (see MAXIIS parameter). The fields:
iisStatus Status flag. (Only set in the first element of the iis array.) Possible values:

2 = IIS was written to file LPprob.iis.

1 = IIS was obtained.

-1 = Problem was infeasible but no IIS found.

-2 = Problem was not infeasible.

iisMessage Error message on error. (Only set in the first element of the iis array.)
colind The column indices of the IIS set.
rowind The row indices of the IIS set.
XPRESS.sa Structure with information about the requested SA, if requested. The fields:
obj Ranges for the variables in the objective function.
rhs Ranges for the right hand side values.
These fields are structures themselves. All four structures have identical field names:
status Status of the SA operation. Possible values:

1 = Successful.

0 = SA not requested.

-1 = Error: MIP problem was presolved.

lower The lower range.
upper The upper range.

Global Parameters Used

xpControlVariables Structure with all XpressM P control variables listed in Section 7 in the Xpress- Optimizer Reference Manual [1]. Available with fresh variables in each callback, and after the optimization.
xpProblemAttrib Structure with all XpressM P problem attributes listed in Section 8 in the Xpress- Optimizer Reference Manual [1]. Available with fresh variables in each callback, and after the optimization.

Description

The TOMLAB XpressM P MILP, MIQP, QP and LP interface calls the interface routine xpress.m. Values > 1020 and I nf values are set to 1020 , and the opposite for negative numbers. An empty objective coefficient c-vector is set to the zero-vector.

Examples

See mip prob

M-files Used

xpress.m, mipRun.m

See Also

mipSolve