PATHSolver.jl

PATHSolver.jl is a wrapper for the PATH solver.

The wrapper has two components:

• a thin wrapper around the C API
• an interface to MathOptInterface

You can solve any complementarity problem using the wrapper around the C API, although you must manually provide the callback functions, including the Jacobian.

The MathOptInterface wrapper is more limited, supporting only linear complementarity problems, but it enables PATHSolver to be used with JuMP.

Affiliation

This wrapper is maintained by the JuMP community and is not an official wrapper of PATH. However, we are in close contact with the PATH developers, and they have given us permission to re-distribute the PATH binaries for automatic installation.

License

PATHSolver.jl is licensed under the MIT License.

The underlying solver, path is closed source and requires a license.

Without a license, the PATH Solver can solve problem instances up to with up to 300 variables and 2000 non-zeros. For larger problems, this web page provides a temporary license that is valid for a year.

You can either store the license in the PATH_LICENSE_STRING environment variable, or you can use the PATHSolver.c_api_License_SetString function immediately after importing the PATHSolver package:

import PATHSolverPATHSolver.c_api_License_SetString("<LICENSE STRING>")

where <LICENSE STRING> is replaced by the current license string.

Installation

Install PATHSolver.jl as follows:

import PkgPkg.add("PATHSolver")

By default, PATHSolver.jl will download a copy of the underlying PATH solver. To use a different version of PATH, see the Manual Installation section below.

Use with JuMP

julia> using JuMP, PATHSolverjulia> M = [           0  0 -1 -1           0  0  1 -2           1 -1  2 -2           1  2 -2  4       ]4×4 Array{Int64,2}: 0   0  -1  -1 0   0   1  -2 1  -1   2  -2 1   2  -2   4julia> q = [2, 2, -2, -6]4-element Array{Int64,1}:  2  2 -2 -6julia> model = Model(PATHSolver.Optimizer)A JuMP ModelFeasibility problem with:Variables: 0Model mode: AUTOMATICCachingOptimizer state: EMPTY_OPTIMIZERSolver name: Path 5.0.00julia> set_optimizer_attribute(model, "output", "no")julia> @variable(model, x[1:4] >= 0)4-element Array{VariableRef,1}: x[1] x[2] x[3] x[4]julia> @constraint(model, M * x .+ q ⟂ x)[-x[3] - x[4] + 2, x[3] - 2 x[4] + 2, x[1] - x[2] + 2 x[3] - 2 x[4] - 2, x[1] + 2 x[2] - 2 x[3] + 4 x[4] - 6, x[1], x[2], x[3], x[4]] ∈ MOI.Complements(4)julia> optimize!(model)Reading options file /var/folders/bg/dzq_hhvx1dxgy6gb5510pxj80000gn/T/tmpiSsCRORead of options file complete.Path 5.0.00 (Mon Aug 19 10:57:18 2019)Written by Todd Munson, Steven Dirkse, Youngdae Kim, and Michael Ferrisjulia> value.(x)4-element Array{Float64,1}: 2.8 0.0 0.7999999999999998 1.2julia> termination_status(model)LOCALLY_SOLVED::TerminationStatusCode = 4

Note that options are set using JuMP.set_optimizer_attribute.

The list of options supported by PATH can be found here: https://pages.cs.wisc.edu/~ferris/path/options.pdf

MathOptInterface API

The Path 5.0.03 optimizer supports the following constraints and attributes.

List of supported variable types:

• MOI.Reals

List of supported constraint types:

• MOI.VariableIndex in MOI.EqualTo{Float64}
• MOI.VariableIndex in MOI.GreaterThan{Float64}
• MOI.VariableIndex in MOI.Interval{Float64}
• MOI.VariableIndex in MOI.LessThan{Float64}
• MOI.VectorOfVariables in MOI.Complements
• MOI.VectorAffineFunction{Float64} in MOI.Complements
• MOI.VectorQuadraticFunction{Float64} in MOI.Complements
• MOI.VectorNonlinearFunction in MOI.Complements

List of supported model attributes:

• MOI.Name()

Use with the C API

PATHSolver.jl wraps the PATH C API using PATHSolver.c_api_XXX for the C method XXX. However, using the C API directly from Julia can be challenging, particularly with respect to avoiding issues with Julia's garbage collector.

Instead, we recommend that you use the PATHSolver.solve_mcp function, which wrappers the C API into a single call. See the docstring of PATHSolver.solve_mcp for a detailed description of the arguments.

Here is the same example using PATHSolver.solve_mcp. Note that you must manually construct the sparse Jacobian callback.

julia> import PATHSolverjulia> M = [           0  0 -1 -1           0  0  1 -2           1 -1  2 -2           1  2 -2  4       ]4×4 Matrix{Int64}: 0   0  -1  -1 0   0   1  -2 1  -1   2  -2 1   2  -2   4julia> q = [2, 2, -2, -6]4-element Vector{Int64}:  2  2 -2 -6julia> function F(n::Cint, x::Vector{Cdouble}, f::Vector{Cdouble})           @assert n == length(x) == length(f)           f .= M * x .+ q           return Cint(0)       endF (generic function with 1 method)julia> function J(           n::Cint,           nnz::Cint,           x::Vector{Cdouble},           col::Vector{Cint},           len::Vector{Cint},           row::Vector{Cint},           data::Vector{Cdouble},       )           @assert n == length(x) == length(col) == length(len) == 4           @assert nnz == length(row) == length(data)           i = 1           for c in 1:n               col[c], len[c] = i, 0               for r in 1:n                   if !iszero(M[r, c])                       row[i], data[i] = r, M[r, c]                       len[c] += 1                       i += 1                   end               end           end           return Cint(0)       endJ (generic function with 1 method)julia> status, z, info = PATHSolver.solve_mcp(           F,           J,           fill(0.0, 4),  # Lower bounds           fill(Inf, 4),  # Upper bounds           fill(0.0, 4);  # Starting point           nnz = 12,      # Number of nonzeros in the Jacobian           output = "yes",       )Reading options file /var/folders/bg/dzq_hhvx1dxgy6gb5510pxj80000gn/T/jl_iftYBS > output yesRead of options file complete.Path 5.0.03 (Fri Jun 26 09:58:07 2020)Written by Todd Munson, Steven Dirkse, Youngdae Kim, and Michael FerrisCrash Logmajor  func  diff  size  residual    step       prox   (label)    0     0             1.2649e+01             0.0e+00 (f[    4])    1     2     4     2 1.0535e+01  8.0e-01    0.0e+00 (f[    1])    2     3     2     4 8.4815e-01  1.0e+00    0.0e+00 (f[    4])    3     4     0     3 4.4409e-16  1.0e+00    0.0e+00 (f[    3])pn_search terminated: no basis change.Major Iteration Logmajor minor  func  grad  residual    step  type prox    inorm  (label)    0     0     5     4 4.4409e-16           I 0.0e+00 4.4e-16 (f[    3])Major Iterations. . . . 0Minor Iterations. . . . 0Restarts. . . . . . . . 0Crash Iterations. . . . 3Gradient Steps. . . . . 0Function Evaluations. . 5Gradient Evaluations. . 4Basis Time. . . . . . . 0.000016Total Time. . . . . . . 0.044383Residual. . . . . . . . 4.440892e-16(PATHSolver.MCP_Solved, [2.8, 0.0, 0.8, 1.2], PATHSolver.Information(4.4408920985006247e-16, 0.0, 0.0, 0.044383, 1.6e-5, 0.0, 0, 0, 3, 5, 4, 0, 0, 0, 0, false, false, false, true, false, false, false))julia> statusMCP_Solved::MCP_Termination = 1julia> z4-element Vector{Float64}: 2.8 0.0 0.8 1.2

Thread safety

PATH is not thread-safe and there are no known work-arounds. Do not run it in parallel using Threads.@threads. See issue #62 for more details.

Factorization methods

By default, PATHSolver.jl will download the LUSOL shared library. To use LUSOL, set the following options:

model = Model(PATHSolver.Optimizer)set_optimizer_attribute(model, "factorization_method", "blu_lusol")set_optimizer_attribute(model, "factorization_library_name", PATHSolver.LUSOL_LIBRARY_PATH)

To use factorization_method umfpack you will need the umfpack shared library that is available directly from the developers of that code for academic use.

Manual installation

By default PATHSolver.jl will download a copy of the libpath library. If you already have one installed and want to use that, set the PATH_JL_LOCATION environment variable to point to the libpath50.xx library.