PATH
Description
PATH is a tool for solving (square) mixed complementarity problems. Mixed complementarity problems are systems of linear and nonlinear constraints where variables in the model are linked to constraints in the form of mixed complementarity conditions. In AIMMS, a mixed complementarity condition is defined as follows for a given variable \(x_i\) and an associated function \(f_i(x)\).
If \(l_{if} = -\infty\) and \(u_{if} = \infty\) then
either |
\(x_i = l_{ix}\) |
and |
\(f_i(x) \geq 0\) |
or |
\(x_i = u_{ix}\) |
and |
\(f_i(x) \leq 0\) |
or |
\(l_{ix} < x_i < u_{ix}\) |
and |
\(f_i(x) = 0\). |
If \(l_{ix} = -\infty\) and \(u_{ix} = \infty\) then
either |
\(x_i = 0\) |
and |
\(l_{if} < f_i(x) < u_{if}\) |
or |
\(x_i \geq 0\) |
and |
\(f_i(x) = l_{if}\) |
or |
\(x_i \leq 0\) |
and |
\(f_i(x) = u_{if}\) |
In any other situation, where exactly two of the constants \(l_{ix}\), \(u_{ix}\), \(l_{if}\) and \(u_{if}\) are finite, then
either |
\(x_i = l_{ix}\) |
and |
\(l_{if} \leq f_i(x) \leq u_{if}\) |
or |
\(x_i = u_{ix}\) |
and |
\(l_{if} \leq f_i(x) \leq u_{if}\) |
or |
\(l_{ix} < x_i < u_{ix}\) |
and |
\(f_i(x) = l_{if}\) |
or |
\(l_{ix} < x_i < u_{ix}\) |
and |
\(f_i(x) = u_{if}\) |
Transformation
PATH uses a different definition. In PATH, a mixed complementarity condition requires that:
either |
\(x_i = l_{ix}\) |
and |
\(f_i(x) \geq 0\) |
or |
\(x_i = u_{ix}\) |
and |
\(f_i(x) \leq 0\) |
or |
\(l_{ix} < x_i < u_{ix}\) |
and |
\(f_i(x) = 0\) |
A complementarity condition modeled in AIMMS is transformed into this formulation. Note that no transformation of the complementarity condition is needed if \(l_{if} = -\infty\) and \(u_{if} = \infty\).
PATH requires that the mixed complementarity problem is square (i.e., the number of variables and constraints must be equal) and PATH cannot handle normal inequalities (i.e., inequalities that have no complemented variable). On the other hand, AIMMS does not require that the mixed complementarity problem is square and AIMMS allows that normal inequalities are included. Therefore a mixed complementarity problem defined in AIMMS has to be transformed into the input format needed by PATH. AIMMS will match unassociated variables to ‘normal’ inequalities, and make the problem square by adding variables or constraints. However, users should avoid normal inequalities if possible and match unassociated variables and normal inequalities when the matching makes sense for their application! Structure and convexity can be destroyed if it is left to the AIMMS to perform the matching, which can have a negative influence on PATH’s performance.
PATH is equipped with parameters that influence its performance. AIMMS is equipped with options that set the parameters in PATH. Options in AIMMS can be set in the options dialog box.
Learn more about