Solvers¶

After formulating a multilevel problem, PAO users will generally need to (1) transform the model to a standard form, and (2) apply an optimizer to solve the problem. The examples in the previous sections illustrate that step (1) is often optional; PAO automates the applications of several model transformations, particularly for problems formulated with Pyomo. The following section summarizes the solvers available in PAO, and describes how PAO manages solvers. Section Model Transformations describes model transformations in PAO.

Summary of PAO Solvers¶

The following summarizes the current solvers available in PAO:

pao.mpr.FA, pao.pyomo.FA

PAO solver for Multilevel Problem Representations that define linear bilevel problems. Solver uses big-M relaxations discussed by Fortuny- Amat and McCarl (1981).
pao.mpr.MIBS, pao.pyomo.MIBS

PAO solver for Multilevel Problem Representations using the COIN-OR MibS solver by Tahernejad, Ralphs, and DeNegre (2020).
pao.mpr.PCCG, pao.pyomo.PCCG

PAO solver for Multilevel Problem Representations that define linear bilevel problems. Solver uses projected column constraint generation algorithm described by Yue et al. (2017).
pao.mpr.REG, pao.pyomo.REG

PAO solver for Multilevel Problem Representations that define linear bilevel problems. Solver uses regularization discussed by Scheel and Scholtes (2000) and Ralph and Wright (2004).

The following table summarize key features of the problems these solvers can be applied to:

		Solver
Problem Feature		FA	REG	PCCG	MibS
Equation Structure	Linear	Y	Y	Y	Y
	Bilinear	Y	Y	Y	Y
	Nonlinear
Upper-Level Variables	Integer	Y		Y	Y
Upper-Level Variables	Real	Y	Y	Y	Y
Lower-Level Variables	Integer			Y	Y
Lower-Level Variables	Real	Y	Y	Y	Y
Multilevel Representation	Bilevel	Y	Y	Y	Y
	Trilevel
	k-Bilevel	Y	Y

Note

The iterface to MibS is a prototype that has not been well-tested. This interface will be documented and finalized in an upcoming release of PAO.

The Solver Interface¶

The Solver object provides a single interface for setting up an interface to optimizers in PAO. This includes both PAO solvers for multilevel optimization problems, but also interfaces to conventional numerical solvers that are used by PAO solvers. We illustrate this distinction with the following example, which optimizes the PAO1 (1) example:

>>> # Create an interface to the PAO FA solver
>>> opt = pao.Solver("pao.pyomo.FA")

>>> # Optimize the model
>>> # By default, FA uses the glpk MIP solver
>>> results = opt.solve(M)
>>> print(M.x.value, M.y.value, M.L.z.value)
6.0 4.0 2.0


>>> # Create an interface to the PAO FA solver, using cbc
>>> opt = pao.Solver("pao.pyomo.FA", mip_solver="cbc")

>>> # Optimize the model using cbc
>>> results = opt.solve(M)
>>> print(M.x.value, M.y.value, M.L.z.value)
6.0 4.0 2.0

The Solver object is initialized using the solver name followed by solver-specific options. In this case, the FA algorithm accepts the mip_solver option that specifies the mixed-integer programming (MIP) solver that is used to solve the MIP that is generated by FA after reformulating the bilevel problem. The value of mip_solver is itself an optimizer. As illustrated here, this option can simply be the string name of the MIP solver that will be used. However, the Solver object can be used to define a MIP solver interface as well:

>>> # Create an interface to the cbc MIP solver
>>> mip = pao.Solver("cbc")
>>> # Create an interface to the PAO FA solver, using cbc
>>> opt = pao.Solver("pao.pyomo.FA", mip_solver=mip)

>>> # Optimize the model using cbc
>>> results = opt.solve(M)
>>> print(M.x.value, M.y.value, M.L.z.value)
6.0 4.0 2.0

This enables the customization of the MIP solver used by FA. Note that the solve() method accepts the same options as Solve. This allows for more dynamic specification of solver options:

>>> # Create an interface to the cbc MIP solver
>>> cbc = pao.Solver("cbc")
>>> # Create an interface to the glpk MIP solver
>>> glpk = pao.Solver("glpk")

>>> # Create an interface to the PAO FA solver
>>> opt = pao.Solver("pao.pyomo.FA")

>>> # Optimize the model using cbc
>>> results = opt.solve(M, mip_solver=cbc)
>>> print(M.x.value, M.y.value, M.L.z.value)
6.0 4.0 2.0

>>> # Optimize the model using glpk
>>> results = opt.solve(M, mip_solver=glpk)
>>> print(M.x.value, M.y.value, M.L.z.value)
6.0 4.0 2.0

Warning

The solve() current passes unknown keyword arguments to the optimizer used by PAO solvers, but this feature will be disabled.

PAO Solvers¶

Solvers developed in PAO have names that begin with pao.. The current set of available PAO solvers can be queried using the Solver object:

>>> for name in pao.Solver:
...     print(name)
pao.mpr.FA
pao.mpr.MIBS
pao.mpr.PCCG
pao.mpr.REG
pao.pyomo.FA
pao.pyomo.MIBS
pao.pyomo.PCCG
pao.pyomo.REG

>>> pao.Solver.summary()
pao.mpr.FA
    PAO solver for Multilevel Problem Representations that define linear
    bilevel problems.  Solver uses big-M relaxations discussed by Fortuny-
    Amat and McCarl (1981).

pao.mpr.MIBS
    PAO solver for Multilevel Problem Representations using the COIN-OR
    MibS solver by Tahernejad, Ralphs, and DeNegre (2020).

pao.mpr.PCCG
    PAO solver for Multilevel Problem Representations that define linear
    bilevel problems. Solver uses projected column constraint generation
    algorithm described by Yue et al. (2017).

pao.mpr.REG
    PAO solver for Multilevel Problem Representations that define linear
    bilevel problems.  Solver uses regularization discussed by Scheel and
    Scholtes (2000) and Ralph and Wright (2004).

pao.pyomo.FA
    PAO solver for Pyomo models that define linear and bilinear bilevel
    problems.  Solver uses big-M relaxations discussed by Fortuny-Amat and
    McCarl (1981).

pao.pyomo.MIBS
    PAO solver for Multilevel Problem Representations using the COIN-OR
    MibS solver by Tahernejad, Ralphs, and DeNegre (2020).

pao.pyomo.PCCG
    PAO solver for Pyomo models that define linear and bilinear bilevel
    problems.  Solver uses projected column constraint generation
    algorithm described by Yue et al. (2017)

pao.pyomo.REG
    PAO solver for Pyomo models that define linear and bilinear bilevel
    problems.  Solver uses regularization discussed by Scheel and Scholtes
    (2000) and Ralph and Wright (2004).

The solve() method includes documentation describing the keyword arguments for a specific solver. For example:

>>> opt = pao.Solver("pao.pyomo.FA")
>>> help(opt.solve)
Help on method solve in module pao.pyomo.solvers.mpr_solvers:

solve(model, **options) method of pao.pyomo.solvers.mpr_solvers.PyomoSubmodelSolver_FA instance
    Executes the solver and loads the solution into the model.

    Parameters
    ----------
    model
        The model that is being optimized.
    options
        Keyword options that are used to configure the solver.

    Keyword Arguments
    -----------------
    tee
      If True, then solver output is streamed to stdout. (default is False)
    load_solutions
      If True, then the finale solution is loaded into the model. (default is True)
    linearize_bigm
      The name of the big-M value used to linearize bilinear terms.  If this is not specified, then the solver will throw an error if bilinear terms exist in the model.
    mip_solver
      The MIP solver used by FA.  (default is glpk)

    Returns
    -------
    Results
        A summary of the optimization results.

The solve() method returns a results object that contains data about the optimization process. In particular, this object contains information about the termination conditions for the solver. The check_optimal_termination() method can be used confirm that the termination condition indicates that an optimal solution was found. For example:

>>> nlp = pao.Solver('ipopt', print_level=3)
>>> opt = pao.Solver('pao.pyomo.REG', nlp_solver=nlp)
>>> results = opt.solve(M)
>>> print(results.solver.termination_condition)
TerminationCondition.optimal
>>> results.check_optimal_termination()
True

Pyomo Solvers¶

The Solver object also provides a convenient interface to conventional numerical solvers. Currently, solver objects constructed by Solver are simple wrappers around Pyomo optimization solver objects. This interface supports two types of solver interfaces: (1) solvers that execute locally, and (2) solvers that execute on remote servers.

When optimizating a Pyomo model, solver parameters can be setup both when the solver interface is created and when a model is optimized. For example:

>>> # This is a nonlinear toy problem modeled with Pyomo
>>> NLP = pe.ConcreteModel()
>>> A = list(range(10))
>>> NLP.x = pe.Var(A, bounds=(0,None), initialize=1)
>>> NLP.o = pe.Objective(expr=sum(pe.sin((i+1)*NLP.x[i]) for i in A))
>>> NLP.c = pe.Constraint(expr=sum(NLP.x[i] for i in A) >= 1)

>>> nlp = pao.Solver('ipopt', print_level=3)
>>> # Apply ipopt with print level 3
>>> results = nlp.solve(NLP)
>>> # Override the default print level to using 5
>>> results = nlp.solve(NLP, print_level=5)

However, PAO users will typically setup solver parameters when the Pyomo solver is initially created:

>>> nlp = pao.Solver('ipopt', print_level=3)
>>> opt = pao.Solver('pao.pyomo.REG', nlp_solver=nlp)
>>> results = opt.solve(M)

When executing locally, the executable option can be used to explicitly specify the path to the executable that is used by this solver. This is helpful in contexts where Pyomo is not automatically finding the correct optimizer executable in a user’s shell environment.

When executing on a remote server, the server is used to specify the server that is used. Currently, only the neos server is supported, which allows the user to perform optimization at NEOS [NEOS]. The NEOS server requires a user to specify a valid email address:

Warning

There is no common reference for solver-specific parameters for the solvers available in Pyomo. These are generally documented with solver documentation, and users should expect to contact solver developers to learn about these.