XA Solver Reference
From TomWiki
Jump to navigationJump to search
A detailed description of the TOMLAB /XA solver interface is given below. Also see the M-file help for xaTL.m. It is strongly recommended that the user use the TOMLAB format when using XA. Please go to Section for information about using XA with TOMLAB.
Purpose
The XA linear, mixed-integer linear and quadratic programming (LP, MILP, QP) interface solves problems of the form
| |||||||||||||||||||||||||||||||||||||||||||||||||||
where c, x, xL, xU ∈ ℜn, F ∈ ℜn×n, A ∈ ℜm×n and bL,bU ∈ ℜm. The variables x ∈ I, the index subset of 1,...,n, are restricted to be integers. All variables are considered continuous if F is given.
If F is empty, an LP or MILP problem is solved.
Calling Syntax
[x_k, f_k, Inform, modsts, solsts, act, dact, status] = ...
xa(c, A, x_L, x_U, b_L, b_U, xaControl, callback, PriLev, ...
LogFile, SaveFile, Prob, IntVars, VarWeight, SC, SC2, F)
Description of Inputs
| The following inputs are used: | |
| c | Linear objective function cost coefficients, vector n ×1. |
| A | Linear constraint matrix for linear constraints, dense or sparse matrix m ×n. |
| x_L | Lower bounds on design parameters x. If empty assumed to be 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 b_U=b_L is assumed, i.e. equality constraints. |
| xaControl | Structure, where the fields are set to the XA control parameters that the user wants to specify values for. The control parameters are listed in Section |
| callback | 0/1 vector of length 10. Defines the active callbacks during the solving process. |
| The callback routines and their corresponding indices in the callback vector are: | |
| 1 - xacb_begin.m - before solving | |
| 2 - xacb_infeas.m - infeasible iteration | |
| 3 - xacb_feas.m - feasible iteration | |
| 4 - xacb_node.m - integer node generated | |
| 5 - xacb_intsol.m - integer solution found | |
| 6 - xacb_branch.m - user selects b & b variable | |
| 7 - xacb_barrier.m - barrier iteration | |
| 8 - xacb_resolve.m - problem solve − > fast modify resolve | |
| 9 - currently not used | |
| 10 - xacb_end.m - after solving | |
| The user can either modify the existing xacb_*.m functions (use i.e. "which xacb_feas") to find them, OR copies can be made and placed before the original files in the MATLAB path. | |
| The calling syntax for all XA callbacks is: | |
| function xacb_(*)( xacbInfo, Prob ) | |
| and is described in more detail in xacb.m (help xacb.m) | |
| PriLev | Printing level in the xa m-file and the XA C-interface. |
| = 0 Silent | |
| = 1 Warnings and Errors | |
| = 2 Summary information | |
| = 3 More detailed information | |
| > 10 Pause statements, and maximal printing (debug mode) | |
| LogFile | Name of file to write XA log to. If empty, no log is written. |
| SaveFile | Name of file to write MPS representation of the problem to. The name should be given without extension - .mps is added automatically. If empty, the problem is not saved. |
| Prob | A structure. If TOMLAB calls XA, 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 (see description of callback) 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.QP.c, Prob.QP.F, Prob.x_L, Prob.x_U, Prob.A, Prob.b_L, Prob.b_U. (if input is [], then Prob.P=1 is set). | |
| IntVars | Defines which variables are integers, of general type I or binary B Variable indices should be in the range [1,...,n]. IntVars is a logical vector ==> x(find(IntVars > 0)) are integers. IntVars is a vector of indices ==> x(IntVars) are integers (if [], then no integers of type I or B are defined). XA checks which variables has x_L = 0 and x_U = 1, i.e. binary. |
| VarWeight | Vector of branching priorities for MILP problems. Should be a n-vector, ideally of integers > =1. A lower value means higher priority in the variable selection phase. |
| SC | A vector with indices for the Type 1 Semi-Continuous variables, i.e. that takes either the value 0 or a value in the range [ x_L(i) , x_U(i) ]. |
| SC2 | A vector with indices for the Type 2 Semi-Continuous variables, i.e. that takes either the value of the corresponding upper bound, or a value in the range [ x_L(i) , 0 ]. |
| F | Square dense or sparse matrix. Empty if non-quadratic problem. |
| iisRequest | A flag telling whether to obtain an IIS when a problem is determined infeasible. The flag can be set to one of the following values: |
| 0 - Do not search for an IIS (default). | |
| 1 - Implementation of irreducible inconsistent systems (IIS) of constraints. Algorithm: IIS. | |
| 2 - Method of locationing a minimal number of constraints such that if all are removed the model is feasible. Algorithm: Block. | |
| The IIS is returned through the output parameter: iis. Information about the IIS is automatically written to the LogFile if a LogFile is defined. | |
Description of Outputs
| The following fields are used: | |
| x_k | Solution vector with decision variable values (n x 1 vector). |
| f_k | Objective function value at optimum. |
| Inform | Result of XA run. |
| 2 = Init Successful. | |
| 4 = Load Successful. | |
| 6 = Solve Successful. | |
| 8 = Undo Successful. | |
| 10 = Done Successful. | |
| 101 = Allocation amount must be greater than or equal to 0. | |
| 102 = Allocation amount must be greater than or equal to 0. | |
| 103 = Memory allocation error, no memory available. | |
| 104 = Memory allocation error, requested memory not available. | |
| 110-118 = XA called out of sequence. | |
| 122 = BXA.DLL not in path. | |
| 124 = Wrong version of BXA.DLL or your version has been damaged. | |
| 126 = Wrong routine called after XADONE. | |
| 128 = Restart OS. | |
| 132, 134, 136 = Size is incorrect. | |
| 204 = Incorrect No or Yes variable. | |
| 205 = Incorrect command line parameter. | |
| 207 = Unreasonable command line parameter value. | |
| 208 = Incorrect value set. | |
| 209 = Incorrect value set. | |
| 210 = Incorrect value set. | |
| 211 = Unable to process output. | |
| 214 = Incorrect value set. | |
| 300 = Column number out of range. | |
| 301 = Too many or zero rows in problem. | |
| 302 = Too many or zero columns in problem. | |
| 303 = Free memory error, XA could not release it's memory. Probably XA data storage area has been clobbered. | |
| 304 = Column lower bound > upper bound. | |
| 305 = Row lower bound > upper bound. | |
| 306 = Problem too large for available memory. | |
| 307 = Too many nonzeros. | |
| 308 = Row number out of range. | |
| 309 = Duplicate column and/or row. | |
| 310 = Arrays overlap. | |
| 312 = Bad colptr values. | |
| 314 = Unreasonable rownos values. | |
| 316 = Duplicate rownos value for the same column. | |
| 318 = Unreasonable technology coefficient in a array. | |
| 320 = Unreasonable value in status array. | |
| 322 = Unreasonable value in priority array. | |
| 324 = Unreasonable value in increment array. | |
| 326 = Semi-continuous type 1 or type 2 column missing lower bound. | |
| 328 = Column can not have both semi-continuous type 1 and type 2 at the same time. | |
| 330 = Unrecognized line in MPS file. | |
| 400 = MPS formatted file is missing NAME line. The NAME must start in column 1 and be the first line in the file. | |
| 402 = Incomplete MPS file. File probably truncated. | |
| 404 = Row relationship error. | |
| 406 = Expecting a number. | |
| 408 = Bound relationship error. | |
| 410 = Split Column declaration. All rows a column intersects must be grouped together. | |
| 412 = In Column section, a column has duplicate row entries. | |
| 420 = Column has a Power sequence with a negative lower bound. | |
| 600 = Misspelled or missing DBF table filename. | |
| 602 = Error reading DBF table. | |
| 604 = Special row and column name appear together. | |
| 606 = Row increment setting; increment settings only apply to integer columns. | |
| 608 = Row priority setting, priority settings only apply to integer columns. | |
| 610 = Row field name not found in DBF table. | |
| 612 = Column field name not found in DBF table. | |
| 614 = Coefficient field name not found in DBF table. | |
| 616 = No data available in DBF table. | |
| 700 = No data previously loaded for solving. | |
| 702 = Row name size not equal to previously loaded name size. | |
| 704 = Column name size not equal to previously loaded size. | |
| 706 = Specified name size does not match row or column name size. | |
| 900 = Unknown error. | |
| 901 = Incorrect call. | |
| 930 = XA is solving an integer programming problem. A node is generated splitting the feasible region of each integer variables. The default maximum number of nodes is sqrt( number of Integers variables ) + number of 0/1 and semi-continuous columns + 4000 This default settings is too small. Set MAXNODES # to increase. | |
| 998 = Internal system administration error. | |
| 999 = Code has XA's internal memory. | |
| 20001 = Ranging a free/null row with MPS file. | |
| 20030 = Row name referenced in COLUMNS section is undefined. | |
| 20040 = Column has no technological coefficients, XA is fixing with zero primal activity. | |
| 20045 = Column name referenced in BOUNDS section is undefined. | |
| 20050 = Unable to save ädvance basis" solution. | |
| 20060 = A free column only appears in a FREE row. SET MPSXCOMPATIBLE YES to FIX this column to zero. | |
| 20080 = Duplicate row names in ROWS section. | |
| 20090 = Unrecognized line in MPS formatted file. | |
| 902-919 = Argument xx has a unreasonable value. This can also occur when you leave off an argument. | |
| modsts | Model status. See Table |
| solsts | Solver status. See Table |
| act | Primal activities for all columns+rows. |
| dact | Dual activities for all columns+rows. |
| status | Status of all rows+cols at optimum. |
| iis | Structure containing IIS information. Fields: |
| iisStatus | Status flag. Possible values: |
| 1 - IIS was obtained. | |
| 0 - IIS was not requested. | |
| -1 - Problem is infeasible but no IIS found. | |
| -2 - Problem is not infeasible. | |
| iisMessage | Status message. |
| rowind | The row indices of the IIS set. |
Description
The interface routine xa calls XA to solve LP, QP, and MILP problems. The matrices A and F are transformed in xa.m to the XA sparse matrix format.
Error checking is made on the lengths of the vectors and matrices.
xaTL
Purpose
The XA LP, MILP, and QP Interface solves linear programming (LP), quadratic programming (QP) and mixed integer linear programming (MILP). xaTL solves problems of the form
| |||||||||||||||||||||||||||||||||||||||||||||||||||
where c, x, xL, xU ∈ ℜn, F ∈ ℜn×n, A ∈ ℜm×n and bL,bU ∈ ℜm. The variables x ∈ I, the index subset of 1,...,n, are restricted to be integers. All variables are considered continuous if F is given.
Calling Syntax
Prob = lpAssign( ... ); or Prob = mipAssign( ... ); or Prob = qpAssign( ... );
Result = xaTL(Prob); or Result = tomRun('xa', Prob, 1);
Description of Inputs
| Problem description structure. The following fields are used: | |
| Problem description structure. The following fields are used:, continued | |
| Prob | Problem structure in TOMLAB format. Use lpAssign, mipAssign or qpAssign to define the Prob structure. |
| Fields used in input structure Prob: | |
| x_L, x_U | Lower and upper bounds on variables, size n x 1. |
| b_L, b_U | Lower and upper bounds on linear constraints, size m x 1. |
| A | Linear constraint matrix, dense or sparse m x n matrix. |
| NOTE - all bounds vectors - if [], +/- Inf is assumed. | |
| QP.c | Linear objective function coefficients, size n x 1. |
| QP.F | Quadratic matrix of size n x n. |
| PriLevOpt | Print level in XATL, the XA m-file and XAmex C-interface. |
| = 0 Silent | |
| = 1 Warnings and Errors | |
| = 2 Summary information | |
| = 3 More detailed information | |
| > 10 Pause statements, and maximal printing (debug mode) | |
| optParam | Structure with optimization parameters. The following fields are used: |
| MaxIter | Limit of iterations. If a value is given here, it is set as xaControl.ITERATION. Note that a value given directly in Prob.MIP.xaControl.ITERATION takes precedence. |
| Prob.XA | Structure with XA specific parameters. The following fields are used: |
| LogFile | Name of file to write XA log to. If empty, no log is written. |
| SaveFile | Name of file to write MPS representation of the problem to. The name should be given without extension - .mps is added automatically. If empty, the problem is not saved. |
| callback | 0/1 vector of length 10. Defines the active callbacks during the solving process. |
| The callback routines and their corresponding indices in the callback vector are: | |
| 1 - xacb_begin.m - before solving | |
| 2 - xacb_infeas.m - infeasible iteration | |
| 3 - xacb_feas.m - feasible iteration | |
| 4 - xacb_node.m - integer node generated | |
| 5 - xacb_intsol.m - integer solution found | |
| 6 - xacb_branch.m - user selects b & b variable | |
| 7 - xacb_barrier.m - barrier iteration | |
| 8 - xacb_resolve.m - problem solve − > fast modify resolve | |
| 9 - currently not used | |
| 10 - xacb_end.m - after solving | |
| The user can either modify the existing xacb_*.m functions (use i.e. "which xacb_feas") to find them, OR copies can be made and placed before the original files in the MATLAB path. | |
| The calling syntax for all XA callbacks is: | |
| function xacb_(*)( xacbInfo, Prob ) | |
| and is described in more detail in xacb.m (help xacb.m) | |
| iis | A flag telling whether to obtain an IIS when a problem is determined infeasible. The flag can be set to one of the following values: |
| 0 - Do not search for an IIS (default). | |
| 1 - Implementation of irreducible inconsistent systems (IIS) of constraints. Algorithm: IIS. | |
| 2 - Method of locationing a minimal number of constraints such that if all are removed the model is feasible. Algorithm: Block. | |
| The IIS is returned to the field: Result.XA.iis Information about the IIS is automatically written to the LogFile if a LogFile is defined. | |
| Prob.MIP | Structure holding information about mixed integer optimization. Also found here is the xaControl structure in which XA parameter settings can be made. The fields used are: |
| IntVars | Defines which variables are integers, of general type I or binary B Variable indices should be in the range [1,...,n]. IntVars is a logical vector ==> x(find(IntVars > 0)) are integers. IntVars is a vector of indices ==> x(IntVars) are integers (if [], then no integers of type I or B are defined). XA checks which variables has x_L=0 and x_U=1, i.e. binary. |
| VarWeight | Vector of branching priorities for MILP problems. Should be a n-vector, ideally of integers > =1. A lower value means higher priority in the variable selection phase. |
| SC | A vector with indices for the Type 1 Semi-Continuous variables, i.e. that takes either the value 0 or a value in the range [ x_L(i) , x_U(i) ]. |
| SC2 | A vector with indices for the Type 2 Semi-Continuous variables, i.e. that takes either the value of the corresponding upper bound, or a value in the range [ x_L(i) , 0 ]. |
| F | Square dense or sparse matrix. Empty if non-quadratic problem. |
| xaControl | Structure, where fields are set to the XA control parameters that the user wants to specify values for. Please refer to Section for more information on how to set the fields. |
Description of Outputs
| Result structure. The following fields are used: | |
| Result. The following fields are used:, continued | |
| f_k | Function value at optimum. |
| x_k | Solution vector. |
| x_0 | Initial solution vector not known, set as empty. |
| g_k | Exact gradient computed at optimum, computed as c or c + Fx. |
| xState | State of variables. Free==; On lower ==1; On upper ==2; Fixed ==3;. |
| bState | State of constraints. Free==; On lower ==1; On upper ==2; Equality ==3;. |
| v_k | Lagrangian multipliers (for bounds + dual solution vector). |
| v_k = [rc;v]. rc n-vector of reduced costs. v holds m dual variables. | |
| rc | Reduced costs. If ninf=0, last m ==-v_k. |
| ExitFlag | Exit status, TOMLAB standard. |
| Inform | Result of XA run. |
| 2 = Init Successful. | |
| 4 = Load Successful. | |
| 6 = Solve Successful. | |
| 8 = Undo Successful. | |
| 10 = Done Successful. | |
| 101 = Allocation amount must be greater than or equal to 0. | |
| 102 = Allocation amount must be greater than or equal to 0. | |
| 103 = Memory allocation error, no memory available. | |
| 104 = Memory allocation error, requested memory not available. | |
| 110-118 = XA called out of sequence. | |
| 122 = BXA.DLL not in path. | |
| 124 = Wrong version of BXA.DLL or your version has been damaged. | |
| 126 = Wrong routine called after XADONE. | |
| 128 = Restart OS. | |
| 132, 134, 136 = Size is incorrect. | |
| 204 = Incorrect No or Yes variable. | |
| 205 = Incorrect command line parameter. | |
| 207 = Unreasonable command line parameter value. | |
| 208 = Incorrect value set. | |
| 209 = Incorrect value set. | |
| 210 = Incorrect value set. | |
| 211 = Unable to process output. | |
| 214 = Incorrect value set. | |
| 300 = Column number out of range. | |
| 301 = Too many or zero rows in problem. | |
| 302 = Too many or zero columns in problem. | |
| 303 = Free memory error, XA could not release it's memory. Probably XA data storage area has been clobbered. | |
| 304 = Column lower bound > upper bound. | |
| 305 = Row lower bound > upper bound. | |
| 306 = Problem too large for available memory. | |
| 307 = Too many nonzeros. | |
| 308 = Row number out of range. | |
| 309 = Duplicate column and/or row. | |
| 310 = Arrays overlap. | |
| 312 = Bad colptr values. | |
| 314 = Unreasonable rownos values. | |
| 316 = Duplicate rownos value for the same column. | |
| 318 = Unreasonable technology coefficient in a array. | |
| 320 = Unreasonable value in status array. | |
| 322 = Unreasonable value in priority array. | |
| 324 = Unreasonable value in increment array. | |
| 326 = Semi-continuous type 1 or type 2 column missing lower bound. | |
| 328 = Column can not have both semi-continuous type 1 and type 2 at the same time. | |
| 330 = Unrecognized line in MPS file. | |
| 400 = MPS formatted file is missing NAME line. The NAME must start in column 1 and be the first line in the file. | |
| 402 = Incomplete MPS file. File probably truncated. | |
| 404 = Row relationship error. | |
| 406 = Expecting a number. | |
| 408 = Bound relationship error. | |
| 410 = Split Column declaration. All rows a column intersects must be grouped together. | |
| 412 = In Column section, a column has duplicate row entries. | |
| 420 = Column has a Power sequence with a negative lower bound. | |
| 600 = Misspelled or missing DBF table filename. | |
| 602 = Error reading DBF table. | |
| 604 = Special row and column name appear together. | |
| 606 = Row increment setting; increment settings only apply to integer columns. | |
| 608 = Row priority setting, priority settings only apply to integer columns. | |
| 610 = Row field name not found in DBF table. | |
| 612 = Column field name not found in DBF table. | |
| 614 = Coefficient field name not found in DBF table. | |
| 616 = No data available in DBF table. | |
| 700 = No data previously loaded for solving. | |
| 702 = Row name size not equal to previously loaded name size. | |
| 704 = Column name size not equal to previously loaded size. | |
| 706 = Specified name size does not match row or column name size. | |
| 900 = Unknown error. | |
| 901 = Incorrect call. | |
| 930 = XA is solving an integer programming problem. A node is generated splitting the feasible region of each integer variables. The default maximum number of nodes is sqrt( number of Integers variables ) + number of 0/1 and semi-continuous columns + 4000 This default settings is too small. Set MAXNODES # to increase. | |
| 998 = Internal system administration error. | |
| 999 = Code has XA's internal memory. | |
| 20001 = Ranging a free/null row with MPS file. | |
| 20030 = Row name referenced in COLUMNS section is undefined. | |
| 20040 = Column has no technological coefficients, XA is fixing with zero primal activity. | |
| 20045 = Column name referenced in BOUNDS section is undefined. | |
| 20050 = Unable to save ädvance basis" solution. | |
| 20060 = A free column only appears in a FREE row. SET MPSXCOMPATIBLE YES to FIX this column to zero. | |
| 20080 = Duplicate row names in ROWS section. | |
| 20090 = Unrecognized line in MPS formatted file. | |
| 902-919 = Argument xx has a unreasonable value. This can also occur when you leave off an argument. | |
| Iter | Number of iterations / nodes visited. |
| FuncEv | Number of function evaluations. Set to Iter. |
| GradEv | Number of gradient evaluations. Set to Iter if QP/MIQP, otherwise 0. FuncEv and ConstrEv set to Iter. GradEv=0. |
| ConstrEv | Number of constraint evaluations. Set to 0. |
| QP.B | Basis vector in TOMLAB QP standard. |
| Solver | Name of the solver (XA). |
| SolverAlgorithm | Description of the solver. |
| MIP.slack | Slack variables (m x 1 vector). |
| MIP.ninf | Number of infeasibilities. |
| MIP.sinf | Sum of infeasibilities. |
| MIP.lpiter | Number of LP iterations. |
| MIP.glnodes | Number of nodes visited. |
| MIP.basis | basis status of constraints + variables, (m + n x 1 vector) in the XA format, fields xState and bState has the same information in the Tomlab format. |
| XA.iis | Structure containing IIS information. Fields: |
| iisStatus | Status flag. Possible values: |
| 1 - IIS was obtained. | |
| 0 - IIS was not requested. | |
| -1 - Problem is infeasible but no IIS found. | |
| -2 - Problem is not infeasible. | |
| iisMessage | Status message. |
| rowind | The row indices of the IIS set. |
Description
The TOMLAB XA LP, MILP and QP interface calls the interface routine xa.m. Values > 1010 and Inf values are set to 1010, and the opposite for negative numbers. An empty objective coefficient c-vector is set to the zero-vector.
xaControl
The following table describes the XA parameters that the user can set using the xaControl structure.
|
Table 3: XA control parameters in xaControl, The following fields are used: | |
|
Table 4: XA control parameters in xaControl, The following fields are used:, continued | |
| LPMETHOD | LP optimizer algorithm that will be used. For QP problems Barrier will always be used. |
| 0 - Default. Dual Simplex. | |
| 1 - Primal Simplex. | |
| 2 - Dual Simplex. | |
| 3 - Barrier. | |
| 4 - Network Primal Simplex algorithm (not active). | |
| 5 - Network Dual Simplex algorithm (not active). | |
| 6 - Network Generalize Primal Simplex algorithm (not active). | |
| 7 - Network Generalize Dual Simplex algorithm(not active). | |
| BASIS | After XA has solved your problem, the solution is saved for the next time the problem is solved. This can greatly reduce the number of iterations and execution time required. Don't worry about new or deleted variables, constraints, etc. XA will take care of all these adjustments. The Dual Simplex algorithm is used when XA detects advance basis restarts. You can instruct XA to use the Primal Simplex algorithm for restarts as follows, Set DualSimplex No. |
| 'filename.ext' | The filename containing an 'advance basis' for restarting. Default file extension is SAV. |
| 'none' | No 'advance basis' is specified, but the 'final basis' is saved in the problem filename with an extension of SAV. |
| 'never' | No 'advance basis' is specified, and the final 'basis' is not saved. |
| Filename containing basis information (if present), after calling XA this file is updated with new basis information. | |
| Overrides status setting. | |
| '*' means to use the FILENAME setting value. | |
| Defaults to no basis file. | |
| FILENAME | File name to write information. Please specify drive and path information so you can find your file(s). |
| BASIS '*' write to this name . sav, .b01 and .ro1. | |
| ToRCC Yes writes to this name .rcc. | |
| Default value: RUNTIME in current directory. | |
| Example: 'path\filename' | |
| LIMITSEARCH | LimitSearch is used to limit the number of nodes to search by implicitly or explicitly stating a bound on the value of the integer solution. See Section for detailed explanation. |
| Default value is no limiting value, or, -1.0e23 for maximizing and 1.0e23 for minimizing. | |
| Possible values: # (1), #% (2), (#%) (3). | |
| MAXIMIZE | Sense of optimization. |
| No (0) - minimize the objective function (default value). | |
| Yes (1) - maximize the objective function. | |
| PRESOLVE | Prior to solving a model, the XA Optimizer attempts to simplify and reduce the size (number of rows, columns and non-zero coefficients). The amount and type of model reduction is represented be the following 'bit' pattern: |
| Type Reduction | Bit Pattern |
| 12345 67890 123 | |
| Singleton Column | 1xxxx xxxxx xxx |
| Singleton Row | x1xxx xxxxx xxx |
| Min/Max Row Adjust | xx1xx xxxxx xxx |
| Dual Checking | xxx1x xxxxx xxx |
| Min/Max Column Adjust | xxxx1 xxxxx xxx |
| Quick Dual Check | xxxxx 1xxxx xxx |
| Identical Column | xxxxx x1xxx xxx |
| Dependent Rows | xxxxx xx1xx xxx |
| Row Doubleton Reduction | xxxxx xxx1x xxx |
| Free Column Elimination | xxxxx xxxx1 xxx |
| Matrix Reduction | xxxxx xxxxx 1xx |
| Restore Original Bounds | xxxxx xxxxx x1x |
| Expensive Dual Test | xxxxx xxxxx xx1 |
| A one (1) activates and a zero (0) prohibits the a specific reduction feature. Default Pattern : '11111111111100' (string) | |
| Consideration: When you know your model does not have a lot of unnecessary rows or columns, or if you plan to solve variations of the same model 1,000s of times you should consider reducing the amount of presolve checking because these routines can be CPU intensive. | |
| Example, xaControl.PRESOLVE = '1110111111100'; | |
| CRASH | Method of generating initial basis. |
| 0 - Minimize primal infeasibility (default value). | |
| 1 - Minimize dual infeasibility. | |
| 2 - Both 0 and 1. | |
| 3 - All slack basis. | |
| DEGENITER | Degenerate anti-cycling aide. Number of consecutive degenerate pivots before anti-cycling code is activated. |
| Default value: square root of the number of rows. | |
| ELEMSIZE | The smallest element that can be stored in the LU factors arrays. If the absolute value is a number less than this it is considered zero (0.0). Extreme caution should be exercised when changing this value because of the overall effect on problem feasibility. |
| Default value: 1.0e-12 | |
| ELIMINATE | See Command Line Parameter PRESOLVE. |
| 'No' (0), 'Yes' (1), 'Off' (2). | |
| FREQLOG | Frequency in seconds to print the iteration log line. A negative number (e.g. -2) overwrites the same line. This command reduces the overhead of printing too many iteration lines. |
| Default value: 1 (one log line per second). | |
| IBOUNDS | Upper bound for integer column. Default value: 1.0 |
| INTGAP | Minimum objective function improvement between each new integer solutions. |
| Reported integer solution may not be the optimal integer solution because of premature termination. Default value 0.00. | |
| INTLIMIT | After finding this number of improving integer solution XA terminates with the best solution thus far. |
| Defaults - no limit the number of integer solutions. Reported integer solution may not be the optimal integer solution because of premature termination. | |
| INTPCT | Percent of available integer columns to consider fixing at each integer node. |
| Useful on very large binary problems. | |
| Default is zero (0.0) meaning no fixing. | |
| If 100 is entered then all integer columns that are integer at the end of solving the relaxed LP problem are fixed at the current integer bounds. | |
| IROUND | XA reports either rounded or unrounded integer column primal activity. 1 is YES (Default is 1), 0 is NO |
| YES causes XA to report rounded integer column activity. XA rounds integer activity values to the closest bound based upon the LTOLERANCE and UTOLERANCE values. | |
| NO causes XA to report unrounded integer variable activity, but these activities will always be within the requested integer tolerance. | |
| ITERATION | Maximum number of iteration. XA terminates if limit is exceeded, and if solving an integer problem the best integer solution found thus far is returned. |
| Default value: 2000000000 | |
| Reported integer solution may not be the optimal integer solution because of premature termination. | |
| LIMITNODES | Maximum number of branch and bound nodes to generate. XA terminates if limit is exceeded. |
| Default value: 2000000000 | |
| Reported integer solution may not be the optimal integer solution because of premature termination, or an integer solution may not have bee found. | |
| L-, UTOLERANCE | The tolerance (closeness) XA uses to solve integer column to it's numeric sequence. Values between LTOLERANCE and UTOLERANCE are candidates for branch and bound. |
| For instance, you might consider using an UTOLERANCE of 0.02 (a boat 98% full for all practical purposes to really 100% full). But beware, these integer activities within the specified tolerances are used in calculating constraint relationships and the objective function value. | |
| For example, if LTOLERANCE = 0.001, UTOLERANCE = 0.05, and Y has a reported (rounded) activity of 4.0, then 3 * Y ranges of 3 * 3.95 to 3 * 4.001. | |
| Default values: 5.0e-6. | |
| MARKOWITZ | Numeric Stability vs. sparsity in basis updating and inverse. Markowitz number is used during matrix inversion and updating the LU factors. During inversion, row and column factors are scanned for the largest and smallest numbers (in an absolute sense). The pivot element is chosen such that the ratio of the pivot element to these numbers is less than the MARKOWITZ number if possible. The larger the MARKOWITZ number is, the larger will this ratio be, which leads to sparsity but can cause numeric instability. The best number of numeric stability is 1.0 which tends to leads to build-up (density) in the LU factors, which effect speed. So simply put - 1) A value of 1.0 is the best for numerical stability and the worst for density. 2) A value of 1000.0 is (can be) bad for numerical stability but good to maintain sparsity of LU factors. |
| Sparsity favors a larger number at the expensive of numeric stability. | |
| Default 10 | |
| MAXNODES | Maximum number of branch and bound nodes. Default value: 4,000 plus the number of binary variables plus square root of the number of integer columns. |
| MPRICING | Number of variables to price per simplex iteration. Zero (0) defaults to 2 x square root of the number columns. Default 0. |
| PERTUBATE | After making 'degeniter' degenerate iterations (pivots), zero pivot values are adjusted by this amount in an attempt to move away from this region. After a non-degenerate pivot is made the 'degeniter' count is reset to zero. Extreme caution should be exercised when changing this value because of the overall effect on problem feasibility. |
| Default value: 0.0e0 | |
| PRICING | Variable pricing strategies. |
| 0 - Standard reduced cost pricing. | |
| 1 - Automatic DEVEX pricing switch over. | |
| 2 - Infeasible DEVEX pricing. | |
| 3 - Feasible DEVEX pricing(default value). | |
| 4 - Both infeasible and feasible DEVEX pricing. | |
| TOLERANCE_DUAL | Dual activity tolerance is considered to be zero. Extreme caution should be exercised when changing this value because of the overall effect on problem feasibility. |
| Default value: 1e-7 | |
| REINVERTFREQ | After making this number of iterations (pivots), the basis is refactor based upon the current columns in the basis and all LU pivoting factor are removed. Reducing the number of pivots before 're-inversion' usually reduces the number of iterations to solve a problem but at the expense of performing more basis inversion which use more CPU time. |
| Default value: 40 | |
| REJPIVOT | After a column is selected to enter the basis, a column is selected to leave the basis to maintain model feasibility. All candidate columns to leave the basis which have a 'marginal' value greater than the 'ypivot' value are initially consider as outgoing columns. If absolute value of the selected outgoing column's 'marginal' value is less than the 'rejpivot' value then this entering column is 'initially' rejected and the search for another column to enter the basis is performed and the outgoing column selection is performed again until the 'rejpivot' value is exceeded. If all enter columns are rejected then the entering column with the largest 'marginal' value is selected without regards to the 'rejpivot' value. |
| Increasing this value, for example to 1.0e-4, improves numerical stability on numerically unstable models but increases solve times. | |
| Extreme caution should be exercised when changing this value because of the overall effect on problem feasibility. | |
| Default value: 1.0e-6 | |
| RELAXED | Integer problem is solved as a standard LP and with no integer columns in the formulation. |
| 0 - integer problem are solved with branch and bound method (default value). | |
| 1 - solve problems as if all columns where continuous columns. | |
| SCALE | Problem Scaling technique. |
| 'No' (0) - Data not scaled. | |
| 'Yes' (1) - Column and row scaling (default value). | |
| '2' (2) - Row scaling only. | |
| SPROUTS, RUNNER | When solving mixed integer models the Optimizer must decide when to generate a 'marker' on the branch and bound node tree. This 'marker' is used to very quickly return to this location and begin exploring other branch directions. The 'marker' table is scanned at regular intervals to try to improve integer solutions. |
| Default value is 0 means no 'markers' are generated. | |
| A positive SPROUTS value indicates the frequency of 'marker' generation. | |
| A negative SPROUTS value indicates the amount of reduction in the number of non-integer columns before a 'marker' is generated. | |
| 'Marker' generate is memory intensify and the amount of memory requested in the call to XAINIT should increase to the maximum amount of memory on your machine. | |
| When solving mixed integer models the Optimizer must decide how to handle node generation, as either depth first or breadth first. The 'depth first' approach continues to generate nodes deeper into the branch tree and only backtracks nodes when an infeasibility or a integer solution is found. The 'breadth first' approach generates and solves both sides of a node tree before deciding which node to continue with to the next level. This process continues until an infeasibility or integer solution is found. | |
| One can control which approach is used with the RUNNER command line parameter. | |
| Default value is 'No' (0) meaning 'breadth first' node generation. | |
| A value of 'Yes' (1) meaning to use 'depth first' node generation. | |
| STICKWITHIT | Once an integer problem is solved, a bit in the 'status' array for each column is set to indicate the branching direction for the next XA iteration. This branching advice is following until this number of infeasible branches are made. |
| Default value 10. | |
| After this number of infeasible branches, the standard branching direction for the particular branch and bound strategy is used. | |
| TOLERANCE _TCOEFFICIENTS | The smallest technological coefficient allowed in your 'a' array. This tolerance is useful when extensive calculations are performed on these coefficients, where the results should be zero (but because of rounding errors) ends up being something like 1.0e-15. |
| Default value: 1.0e-7 | |
| TIMELIMIT | Maximum time in seconds allowed to solving the problem. |
| XA terminates if limit is exceeded, and if solving an integer problem the best integer solution found thus far is returned. | |
| Wall clock time. | |
| Default value: 2000000000 seconds. | |
| If set too low, reported integer solution may not be the optimal integer solution because of premature termination. | |
| TRANSENTRY | After the entering and outgoing basis columns are selected the LU factors are updated. The absolute value of the size of the updated LU factors updated is limited to the pivoting 'marginal' value times 'transentry' value. Extreme caution should be exercised when changing this value because of the overall effect on problem feasibility. |
| Default value: 1.0e-13 | |
| TOLERANCE_PRIMAL | Primal activity values are considered to be zero. Extreme caution should be exercised when changing this value because of the overall effect on problem feasibility. |
| Default value: 1e-8. | |
| YPIVOT | When selecting a column to leave the basis the column's marginal values that are less than 'ypivot' in a absolute sense are rejected. Making pivots with very small values can lead to numeric stability and should be avoid when possible while making pivots with to large a 'ypivot' value to can lead to infeasible pivoting. Extreme caution should be exercised when changing this value because of the overall effect on problem feasibility. |
| Default value: 1.0e-10. | |
| STOPAFTER | Amount of time in seconds to continue solving after finding the first integer solution. |
| Default value: 0, indicating no termination. | |
| Reported integer solution may not be the optimal integer solution because of premature termination. | |
| STOPUNCHANGED | Amount of time in seconds to continue solving without finding a better/improving integer solution. |
| Default value: 0, indicating no termination. | |
| Reported integer solution may not be the optimal integer solution because of premature termination. | |
| STRATEGY | MIP solving strategy. |
| See Table for possible values. | |
| Default value: 1 | |
| TORCC | Write an RCC file of problem. |
| The filename is determined by the FILENAME command line parameter. | |
| 'No' (0) - Do not write an RCC formatted file (default value). | |
| 'Yes' (1) - Write problem in RCC format. | |
xaControl.STRATEGY
Integer models are ones where one or more decision variable must not have fractional values. This is a very much harder problem than an ordinary LP. In the worst case, the amount of time to solve a family of related problems goes up exponentially as the size of the problem grows, for all algorithms that solve such problems to a proven an optimal integer answer.
We use the word integer to describe any binary, generalized integer, semi-continuous, prime, fibonacci, power and special sequence variables. For example, you can define a variable as semi-continuous, generalized integer with increments of 0.25. The only restriction is that you can not declare a variable to be both type I and type II semi-continuous.
Mixed integer linear programming problems are solved by first: optimizing all variables as being continuous variables; and secondly: the problem is searched for integer solutions. That is, feasible solutions are ones satisfying the constraints and which give integer values to the integer variables. The search is started from the optimal continuous solution. The integer decision variables are forced to take integer values using a 'brand and bound' technique with heuristic branching rules. You should be prepared to solve much smaller MIP models than the corresponding LP model. There exist models that are considered challenging, with a few dozen variables. Conversely, some models with tens of thousands of variables solve readily. But a MIP model with hundreds of variables should always be approached, initially at least, with a certain amount of caution.
There are numerous parameters and options available to control the solution strategy. XA has the capability of stopping before an optimum is proved, processing/printing the best integer answer obtained so far. For many MIP models, stopping early is a practical necessity. Fortunately, a solution that has been proved by the algorithm to be within, say, 1% of optimality often turns out to be the true optimum, and the bulk of the computation time is spent proving the optimality. For many modeling situations, a near-optimal solution is acceptable.
Whatever the solution method you choose, when trying to solve a difficult MIP model, it is usually crucial to understand the workings of the physical system you are modeling, and try to find some insight that will assist your chosen algorithm to work better.
The numeric bound on integer variable determines if the variable is binary (0 or 1) or a generalized (0,1,2,3, ...) integer variable. If you do not specify an upper bound for an integer variable then default value is 1.
Integer Command Line Parameters
XA is designed to solve a vast majority of LP problems using the default settings. When solving integer problems the default setting may not provide the best for speed and reliability. By experimenting with these parameters performance can be improved dramatically. The following table shows some of the options.
| MIP performance options | |
| Topic | Integer Specific Command Line Parameter |
|
Table 5: MIP performance options, continued | |
| Topic | Integer Specific Command Line Parameter |
| Branch and Bound Choice | Strategy a (0). |
| Stopping Criteria | |
| Limit the range to search for an integer solution. | LIMITSEARCH |
| Time limit of 1 hour and 25 minutes | Set TIMELIMIT 5100. |
| Iteration limit of 100,000. | Set ITERATION 100000. |
| Iteration limit of 100,000. | Set ITERATION 100000. |
| Stop after find 3 improving integer solutions. | Set INTLIMIT 3 |
| Stop after running for 10 minutes after finding the first integer solution. | Set STOPAFTER 600 |
| Priority branching | |
| Set integer variable branching order to the order the columns are defined in problem. | Priority o, or in reverse order of definition, Priority O. |
| Set branching order by ascending number of nonzeros per column. | Priority s, or descending number, Priority S. |
| Branching order determined by ascending objective coefficient values. | Priority c, or descending number, Priority C. |
| Set the default priority for binary variables to branch before generalized integers. | Set BVPriority 1000 |
| Set the default priority for binary variables to branch after all generalized integers. | Set BVPriority 20000 |
| Near Integer Optimal Solutions | |
| Solve for a solution with in 1000 units of the optimal integer solution. | Set INTGAP 1000. |
| Solve within 10 percent of the optimal integer solution. | LIMITSEARCH (10%). |
| Integer Variable Tolerances | |
| Tolerance to variable's upper bound sequence value. | Set UTOLERANCE number. |
| Tolerance to variable's lower bound sequence. | Set LTOLERANCE number. |
| Report the integer variables with unrounded results. | Set IROUND No (0). |
| Change the default upper bound on implicitly bounded integer variables from 1 to 1000. | Set IBOUND 1000. |
| Restarting Integer Models | |
| Use the previous integer solution stored in filename.r01 and re-start problem right were it was interrupted. | Set RESTART Yes (1). |
| Use the previous integer solution as a guide to solving this problem. | Basis filename. |
| Stop after solving the lp part of an integer problem. Do not attempt to solve the integer part of problem. | Set Relaxed Yes. |
| Performance Adjustments | |
| Perform integer variable elimination's at each node and presolve between each node generated. | Set INTPCT 30 |
| Tree Depth Strategy | |
| Limit the run time and tree depth for the branching node at each subdivided branching node. | TREETIME 10 (units are seconds). |
|
TREEDEPTH 8 (28 nodes). | |
| Primal/Dual Solver | |
| Use the dual simplex method to solve subproblems. | Set LPMETHOD 2. |
Branching Strategies
Nine 'branch and bound' strategies are provided to meet the demands of many different types of problems. Each strategy has four variations which effects the solve time, speed to first solution, and finding best integer solution. The order in which integer variables are processed during the search for an integer solutions is important. This order is called the 'branching order' of integer variables. Solution times can vary significantly with the method selected.
A command line parameter, STRATEGY, is available to select the strategy of your choice. The STRATEGY parameter may be specified with one of following values:
|
Table 6: Branch and Bound options | |
| B & B Strategy | Description of Selection Criteria |
|
Table 7: Branch and Bound options, continued | |
| B & B Strategy | Description of Selection Criteria |
| 1 | Proprietary method. Default value. |
| 2 | Minimum change in the objective function. |
| 3 | Priority based upon column order. |
| 4 | Column closest to it's integer bound. |
| 5 | Column always branches up (high). |
| 6 | Column always branches down (low). |
| 7 | Column farthest from it's integer bound. |
| 8 | Column randomly selected, useful when solving very large problems. |
| 9 | Apparent smoothest sides on the polytope. |
Each XA Branch and Bound strategy has 2 variations. Sometimes these variations reduce the solution time but may not yield the optimal integer solution. If you are interested in obtaining a fast and 'good' integer solution (which may not be the optimal integer solution), try these variations.
|
Table 8: Branch and Bound variations | |
| Variation | Effect |
|
Table 9: Branch and Bound variations, continued | |
| Variation | Effect |
| A (1) | This variation reduces the amount of time XA spends estimating the value of a would be integer solution. The values calculated are rough estimates. |
| STRATEGY 1A | |
| Variation A may not appear with variation B. | |
| B (2) | This variation spends very little time calculating estimated integer solutions at each node and is the most radical in performance and integer solution. |
| STRATEGY 8B | |
| Variation B may not appear with variation A. | |
| C (3) | Each time an improving integer solution is found XA splits the remaining node list in half based upon the length of the current list. This technique allows XA to search nodes that might not normally be explored. The reported integer solution value may not be the optimal integer solution because nodes may be eliminated that would lead to this solutions. |
| STRATEGY 6C | |
| Variation C may not appear with variation D. | |
| D (4) | Each time an improving integer solution is found XA splits the remaining node list based upon the difference in current projected objective and the best possible objective value divided by two. This technique allows XA to search nodes that might not normally be explored. The reported integer solution value may not be the optimal integer solution because nodes may be eliminated that would lead to this solutions. |
| STRATEGY 1D | |
| Variation D may not appear with variation C. | |
| P (5) | Each time a node is generated XA calculates the effects of each non-integer on future objective function values, which is calculation intensive. By assigning branching priorities to your integer variables XA will only perform this calculation on non-integer variable(s) with the lowest branching priority, which frequently reduces the number of calculations. |
| STRATEGY 1P or STRATEGY 6BP | |
| Variation P may appear any variation, but to be effective you must assign integer branching priorities. | |
Branching Priority
Branching priorities are completely independent of branching strategies.
1. XA develops a lists of integer/binary/semi- variables which are NOT integral (not sequence appropriate).
2. This list is trimmed to variables having the same lowest priority.
3. If strategy value is suffixed by P then 2)'s list is used to compute changes in the objective value, else 1)'s list is used. A large saving of compute time can be found depending upon the size of 1) compared to 2). Plus 2) list can also help the solver sequence the b and b candidates, e.g., period 1 then period 2, .... ordering. This have been found to help out a lot.
4. Now the branching strategy is used to select the variable and direction to branch, up or down.
The priority values used be XA in increasing order of preference. 1) Priority, 2) BVPRIORITY for BV variables with default priority value of 16000 are change to this value. This is XA internal default priority value which is used to initialize all variables.
LimitSearch Command Line Parameters
LIMITSEARCH is used to limit the number of nodes to search by implicitly or explicitly stating a bound on the value of an integer solution. The integer solution obtained, if any, will have a functional value no worse than LIMITSEARCH. The next integer solution will have a monotonically improving objective function value until an optimal integer solution is found and if verified.
If you can estimate the objective function value of a good integer solution, you can avoid nodes that lead to worse solutions and, consequently, speed up the search. However, too restrictive a value may lead to no integer solution at all, if an integer solution with a functional value better that the LIMITSEARCH value does exist. If the search terminates with 'NO INTEGER SOLUTION', you must begin the search again with a less restrictive LIMITSEARCH value.
The LIMITSEARCH command line parameter has three (3) methods of specifying a lower limit on the objective function.
|
Table 10: LIMITSEARCH Methods | |
| Value | Meaning |
|
Table 11: LIMITSEARCH Methods, continued | |
| Value | Meaning |
| ## (1) | Only search for integer solutions between this value and the 'optimal continuous' solution. |
| ##% (2) | Only search for integer solutions with #% of the 'optimal continuous' solution. |
| (#%) (3) | Solve for the integer solution that is within #% of the 'optimal integer solution'. This can reduce the search time significantly, but the reported integer solution may not be the optimal integer solution but will be within #% of it. |
You must experiment with different Strategies and LimitSearch values to determine which is best for your problems. We have found that one of the following settings generally works quite well:
- STRATEGY 1, LIMITSEARCH (5%), STOPAFTER 900
- STRATEGY 6, LIMITSEARCH (5%), STOPAFTER 900
Also try strategies 1A, 1B, 6A, 6B, and 9. The LimitSearch value should be as large as possible and still meets your business objectives (distance from the optimal integer solution). As you gain experience with these 'strategies', you will be able to make an 'informed' choice.
Model and Solver Status
|
Table 12: Model Status Codes | |
| Code | Model Status (modsts) |
|
Table 13: Model Status Codes, continued | |
| Code | Model Status (modsts) |
| 1 | Optimal (Integer) Solution. |
| 2 | Integer Solution (not proven the optimal integer solution). |
| 3 | Unbounded solution. |
| 4 | Infeasible solution. |
| 5 | Callback function indicates Infeasible solution. |
| 6 | Intermediate infeasible solution. |
| 7 | Intermediate nonoptimal solution. |
| 9 | Intermediate Non-integer solution. |
| 10 | Integer Infeasible. |
| 13 | More memory required to load/solve model. |
| 32 | Integer branch and bound process currently active, model has not completed solving. |
| 99 | Currently solving model, model has not completed solving. |
Note: Integer problems return a Model Status code of 1 if the optimal integer solution is found. If XA has not proven that its integer solution is optimal, then a Model Status code of 2 is returned.
|
Table 14: Solver Status Codes | |
| Code | Solver Status (solsts) |
|
Table 15: Solver Status Codes, continued | |
| Code | Solver Status (solsts) |
| 1 | Normal Completion. |
| 2 | Iteration Interrupt. |
| 3 | Resource Interrupt, like time limit exceeded. |
| 4 | Terminated by User, probably a Cntrl Z. |
| 8 | Node Table Overflow. |
| 10 | Solver Failure. |
