XA is a solver package from Sunset Software Technology. It is designed to solve linear programming problems as well mixed integer and quadratic programming problems. XA has been in the optimization arena for more than 20 years and is continually being updated to include new features and enhancements enabling it to be competitive amongst its peers. One can access this robust and reliable solver from the user-friendly Windows environment of MPL, The XA optimisation libraries is accessed from MPL as a Dynamic Link Library (DLL). Allowing MPL users to transparently access XA solution algorithmic methods from their MPL application.
XA has a complete set of methodologies to solve LP problems, its default setting is the dual simplex method, which works well for the majority of problems. It also encompasses the primal and network simplex algorithms that can be preferential on certain problem types. XA also has an interior-point implementation, its barrier algorithm is pretty robust and provides an alternative to the simplex method for solving LPs especially large sparse problems.
XA can solve models that have a quadratic objective function and linear constraints. If the objective function is positive semi-definite, XA can utilize the barrier algorithm to solve the quadratic programming problem. To solve QPs in MPL one has to set in MPL the "ModelType" to Quadratic.
XA uses the branch and bound approach to solve mixed integer programming problems, initially solving an LP relaxation version for the problem. Subsequent branching occurs whereby integer variables are bound to take an integer value. XA incorporate a total of 9 branching strategies allowing great scope for performance tuning.
XA default settings generally perform well, though there are problems on which these settings can give undesirable performance issues, one can suggest a few pointers depending on the type of problem:
XA is tuned to solve the vast majority of LP problems using the default options. There are occasions where one may need to change the option settings, these are usually a result of bad performance or numerical instability issues. On the whole the dual simplex method is best for most LP problems, there are some instances where the primal simplex may work best. The barrier method typically should be used for very large sparse models or models that are experiencing numerical difficulties. One can set the barrier method to solve LPs by changing the option "Algorithm" to 2. If the model has network type constraints the network simplex method often performs best to activate this algorithm set the option to 3.
MIP problems can be extremely difficult to solve, though there are no steadfast rules on enhancing MIP performance, certain things may be advantageous in improving the performance on some models and be a hinderous on other problems. Below are some of the considerations one should look into when try to solve difficult MIP problems:
Priority orders:Assign higher priority to the integer variables that should be decided earlier, these tend to represent decisions that are strategic or activate processes. The order, the variables are defined in MPL indicates the MIP priority, earlier the definition the higher the priority.
Variable selection:Selecting which variable to branch on can have considerable benefits. XA utilizes 9 methods, no one method works best for all models thus when experiencing performance issues we recommend that one experiments with all of these branching options. Typically the default method which is XA's own proprietary method works well on many models. Though often for large models setting the "Strategy" option to 4 or 9 can give substantial performance gains.
XA provides progress information during the optimisation run. MPL can display this information in the message window that also can be relayed to a log file. A typical log has the following appearance:
STATUS: Loading matrix into XA STATUS: Optimizing 'Sawmill' with XA solver XA: Iter: 1 Inf: 96.50000 70 XA: Iter: 2 Inf: 96.40000 69 XA: Iter: 3 Inf: 96.30000 68 XA: Iter: 4 Inf: 96.20000 67 XA: Iter: 5 Inf: 96.10000 66 XA: Iter: 6 Inf: 96.00000 65 XA: Iter: 7 Inf: 95.90000 64 XA: Iter: 8 Inf: 95.80000 63 XA: Iter: 9 Inf: 95.70000 62 XA: Iter: 10 Inf: 95.60000 61
XA shows the sum of infeasibilities at the iterations, once XA finds a feasible solution it states the progress of the objective value at the iterations until it solves to optimality.
XA: Iter: 71 Inf: 0.00000 0 XA: Iter: 72 Obj: -2516371.40 5 XA: Iter: 73 Obj: -2515818.62 3 XA: Iter: 74 Obj: -2509356.52 5 XA: Iter: 75 Obj: -2474037.13 2 XA: Iter: 76 Obj: -2457523.98 3 XA: Iter: 77 Obj: -2432701.33 6 .. XA: Iter: 440 Obj: -464075.937 1 XA: Iter: 441 Obj: -463336.737 1 XA: XA: L P O P T I M A L S O L U T I O N ---> OBJECTIVE -463336.737 XA: SOLVE 1 TIME 00:00:01 ITER 441 MEMORY USED 14.1% XA: Solver Statistics Solver name: XA Objective value: -463336.736591908 Iterations: 442 Solution time: 2.28 sec Result code: 1 STATUS: Retrieve solution back from XA
Upon completion of the optimization process XA displays a summary of the solve relaying total time, memory usage and total number of iterations.
For full description of all the XA Parameters that are supported in MPL please go to the XA Option Parameters page.