# XA Solver Reference

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

 minx
 f(x) = 1 2 xT F x + cT x
 s/t
 xL
 ≤
 x
 ≤
 xU
 bL
 ≤
 Ax
 ≤
 bU
 xi integer
 i ∈ I

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

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

 minx
 f(x) = 1 2 xT F x + cT x
 s/t
 xL
 ≤
 x
 ≤
 xU
 bL
 ≤
 Ax
 ≤
 bU
 xi integer
 i ∈ I

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

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.

### 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.