	[ Home \| Support \| Sales \| Solvers \| Documentation \| Model Libraries \| Search \| Contact Us ]

PATH versus MILES

Introduction

This document describes some of the differences between the MCP solvers PATH and MILES. MILES is a free solver, that comes with the GAMS/BASE module, while PATH is an optional solver, that is charged for separately.

PATH vs. MILES

PATH and MILES are two GAMS solvers capable of solving mixed nonlinear complementarity problems (MCP). Both solvers are based on the sequential linear complementarity algorithm, i.e., they both solve a sequence of linear mixed complementarity problems whose solutions typically converge to the solution of the MCP. To solve each of the linear subproblems (major iterations), both codes use a generalization of an algorithm due to Lemke that is based on a sequence of pivots (minor iterations) similar to those generated by the simplex method for linear programming. To do these pivots efficiently, both codes use the same sparse linear algebra package.

As a result of the above similarities, the performance of the two codes is comparable for many "easy" models. Viewed over a broad range of problems, however, PATH is typically faster and more robust than MILES. While both codes solve all the MCP and MPSGE models in GAMSLIB, PATH signicantly outperforms MILES on the MCPLIB test collection found at CPNET.

Most sophisticated MCP and MPSGE modelers prefer to use PATH over MILES. PATH has a crashing scheme that allows it to quickly improve the user given starting point before starting to solve the linear subproblems. This frequently speeds up solution time. PATH automatically attempts to fix "singular" models using a technique based on proximal perturbations. In many cases, this enables the linear subproblems to be solved, leading to a model solution. This typically helps modelers at model development time.

PATH has many more solution options to enable it solve difficult models. The code automatically tries useful options on difficult problems using a restart procedure. PATH has a much more sophisticated "globalization" procedure that typically improves speed and robustness. PATH implements a nonmonotone watchdog technique. Stalling is frequently circumvented by allowing larger steps to be taken toward solutions.

PATH has many more diagnostic features that help uncover problems in a model. In particular, singularities in the model, zero rows and columns and several measures of optimality are returned to the user. Theoretically, PATH has better convergence properties than MILES. In particular, new merit functions are known to allow more reliable and faster convergence.