# GDPopt logic-based solver

The GDPopt solver in Pyomo allows users to solve nonlinear Generalized Disjunctive Programming (GDP) models using logic-based decomposition approaches, as opposed to the conventional approach via reformulation to a Mixed Integer Nonlinear Programming (MINLP) model.

The main advantage of these techniques is their ability to solve subproblems in a reduced space, including nonlinear constraints only for `True` logical blocks. As a result, GDPopt is most effective for nonlinear GDP models.

Three algorithms are available in GDPopt:

1. Logic-based outer approximation (LOA) [Turkay & Grossmann, 1996]
2. Global logic-based outer approximation (GLOA) [Lee & Grossmann, 2001]
3. Logic-based branch-and-bound (LBB) [Lee & Grossmann, 2001]

Usage and implementation details for GDPopt can be found in the PSE 2018 paper (Chen et al., 2018), or via its preprint.

Credit for prototyping and development can be found in the `GDPopt` class documentation, below.

Usage of GDPopt to solve a Pyomo.GDP concrete model involves:

```>>> SolverFactory('gdpopt').solve(model)
```

Note

By default, GDPopt uses the GDPopt-LOA strategy. Other strategies may be used by specifying the `strategy` argument during `solve()`. All GDPopt options are listed below.

## Logic-based Outer Approximation

Chen et al., 2018 contains the following flowchart, taken from the preprint version: An example which includes the modeling approach may be found below.

```Required imports
>>> from pyomo.environ import *
>>> from pyomo.gdp import *

Create a simple model
>>> model = ConcreteModel(name='LOA example')

>>> model.x = Var(bounds=(-1.2, 2))
>>> model.y = Var(bounds=(-10,10))
>>> model.c = Constraint(expr= model.x + model.y == 1)

>>> model.fix_x = Disjunct()
>>> model.fix_x.c = Constraint(expr=model.x == 0)

>>> model.fix_y = Disjunct()
>>> model.fix_y.c = Constraint(expr=model.y == 0)

>>> model.d = Disjunction(expr=[model.fix_x, model.fix_y])
>>> model.objective = Objective(expr=model.x + 0.1*model.y, sense=minimize)

Solve the model using GDPopt
>>> results = SolverFactory('gdpopt').solve(
...     model, strategy='LOA', mip_solver='glpk')

Display the final solution
>>> model.display()
Model LOA example

Variables:
x : Size=1, Index=None
Key  : Lower : Value : Upper : Fixed : Stale : Domain
None :  -1.2 :   0.0 :     2 : False : False :  Reals
y : Size=1, Index=None
Key  : Lower : Value : Upper : Fixed : Stale : Domain
None :   -10 :   1.0 :    10 : False : False :  Reals

Objectives:
objective : Size=1, Index=None, Active=True
Key  : Active : Value
None :   True :   0.1

Constraints:
c : Size=1
Key  : Lower : Body : Upper
None :   1.0 :  1.0 :   1.0
```

Note

When troubleshooting, it can often be helpful to turn on verbose output using the `tee` flag.

```>>> SolverFactory('gdpopt').solve(model, tee=True)
```

## Logic-based Branch-and-Bound

The GDPopt-LBB solver branches through relaxed subproblems with inactive disjunctions. It explores the possibilities based on best lower bound, eventually activating all disjunctions and presenting the globally optimal solution.

To use the GDPopt-LBB solver, define your Pyomo GDP model as usual:

```Required imports
>>> from pyomo.environ import *
>>> from pyomo.gdp import Disjunct, Disjunction

Create a simple model
>>> m = ConcreteModel()
>>> m.x1 = Var(bounds = (0,8))
>>> m.x2 = Var(bounds = (0,8))
>>> m.obj = Objective(expr=m.x1 + m.x2, sense=minimize)
>>> m.y1 = Disjunct()
>>> m.y2 = Disjunct()
>>> m.y1.c1 = Constraint(expr=m.x1 >= 2)
>>> m.y1.c2 = Constraint(expr=m.x2 >= 2)
>>> m.y2.c1 = Constraint(expr=m.x1 >= 3)
>>> m.y2.c2 = Constraint(expr=m.x2 >= 3)
>>> m.djn = Disjunction(expr=[m.y1, m.y2])

Invoke the GDPopt-LBB solver
>>> results = SolverFactory('gdpopt').solve(m, strategy='LBB')

>>> print(results)
>>> print(results.solver.status)
ok
>>> print(results.solver.termination_condition)
optimal

>>> print([value(m.y1.indicator_var), value(m.y2.indicator_var)])
[True, False]
```

## GDPopt implementation and optional arguments

Warning

GDPopt optional arguments should be considered beta code and are subject to change.

class `pyomo.contrib.gdpopt.GDPopt.``GDPoptSolver`[source]

Decomposition solver for Generalized Disjunctive Programming (GDP) problems.

The GDPopt (Generalized Disjunctive Programming optimizer) solver applies a variety of decomposition-based approaches to solve Generalized Disjunctive Programming (GDP) problems. GDP models can include nonlinear, continuous variables and constraints, as well as logical conditions.

These approaches include:

• Logic-based outer approximation (LOA)
• Logic-based branch-and-bound (LBB)
• Partial surrogate cuts [pending]
• Generalized Bender decomposition [pending]

This solver implementation was developed by Carnegie Mellon University in the research group of Ignacio Grossmann.

For nonconvex problems, LOA may not report rigorous lower/upper bounds.

Questions: Please make a post at StackOverflow and/or contact Qi Chen <https://github.com/qtothec>.

Several key GDPopt components were prototyped by BS and MS students:

• Logic-based branch and bound: Sunjeev Kale
• MC++ interface: Johnny Bates
• LOA set-covering initialization: Eloy Fernandez
`available`(exception_flag=True)[source]

Check if solver is available.

TODO: For now, it is always available. However, sub-solvers may not always be available, and so this should reflect that possibility.

`solve`(model, **kwds)[source]

Solve the model.

Warning: this solver is still in beta. Keyword arguments subject to change. Undocumented keyword arguments definitely subject to change.

This function performs all of the GDPopt solver setup and problem validation. It then calls upon helper functions to construct the initial master approximation and iteration loop.

Parameters: Keyword Arguments: model (Block) – a Pyomo model or block to be solved iterlim – Iteration limit. time_limit – Seconds allowed until terminated. Note that the time limit can currently only be enforced between subsolver invocations. You may need to set subsolver time limits as well. strategy – Decomposition strategy to use. tee – Stream output to terminal. logger – The logger object or name to use for reporting. init_strategy – Selects the initialization strategy to use when generating the initial cuts to construct the master problem. custom_init_disjuncts – List of disjunct sets to use for initialization. max_slack – Upper bound on slack variables for OA OA_penalty_factor – Penalty multiplication term for slack variables on the objective value. set_cover_iterlim – Limit on the number of set covering iterations. call_before_master_solve – callback hook before calling the master problem solver call_after_master_solve – callback hook after a solution of the master problem call_before_subproblem_solve – callback hook before calling the subproblem solver call_after_subproblem_solve – callback hook after a solution of the nonlinear subproblem call_after_subproblem_feasible – callback hook after feasible solution of the nonlinear subproblem algorithm_stall_after – number of non-improving master iterations after which the algorithm will stall and exit. round_discrete_vars – flag to round subproblem discrete variable values to the nearest integer. Rounding is done before fixing disjuncts. force_subproblem_nlp – Force subproblems to be NLP, even if discrete variables exist. mip_presolve – Flag to enable or diable GDPopt MIP presolve. Default=True. subproblem_presolve – Flag to enable or disable subproblem presolve. Default=True. calc_disjunctive_bounds – Calculate special disjunctive variable bounds for GLOA. False by default. obbt_disjunctive_bounds – Use optimality-based bounds tightening rather than feasibility-based bounds tightening to compute disjunctive variable bounds. False by default. check_sat – When True, GDPopt-LBB will check satisfiability at each node via the pyomo.contrib.satsolver interface solve_local_rnGDP – When True, GDPopt-LBB will solve a local MINLP at each node. mip_solver – Mixed integer linear solver to use. mip_solver_args – Keyword arguments to send to the MILP subsolver solve() invocation nlp_solver – Nonlinear solver to use nlp_solver_args – Keyword arguments to send to the NLP subsolver solve() invocation minlp_solver – MINLP solver to use minlp_solver_args – Keyword arguments to send to the MINLP subsolver solve() invocation local_minlp_solver – MINLP solver to use local_minlp_solver_args – Keyword arguments to send to the local MINLP subsolver solve() invocation bound_tolerance – Tolerance for bound convergence. small_dual_tolerance – When generating cuts, small duals multiplied by expressions can cause problems. Exclude all duals smaller in absolue value than the following. integer_tolerance – Tolerance on integral values. constraint_tolerance – Tolerance on constraint satisfaction. variable_tolerance – Tolerance on variable bounds. zero_tolerance – Tolerance on variable equal to zero.
`version`()[source]

Return a 3-tuple describing the solver version.