../../_images/Pyomo-GDP-150.png

Solving Logic-based Models with Pyomo.GDP

Flexible Solution Suite

Once a model is formulated as a GDP model, a range of solution strategies are available to manipulate and solve it.

The traditional approach is reformulation to a MI(N)LP, but various other techniques are possible, including direct solution via the GDPopt solver. Below, we describe some of these capabilities.

Reformulations

Logical constraints

Note

Historically it was required to convert logical propositions to algebraic form prior to use of the MI(N)LP reformulations and the GDPopt solver. However, this is mathematically incorrect since these reformulations convert logical formulations to algebraic formulations. It is therefore recommended to use both the MI(N)LP reformulations and GDPopt directly to transform or solve GDPs that include logical propositions.

The following transforms logical propositions on the model to algebraic form:

TransformationFactory('core.logical_to_linear').apply_to(model)

The transformation creates a constraint list with a unique name starting with logic_to_linear, within which the algebraic equivalents of the logical constraints are placed. If not already associated with a binary variable, each BooleanVar object will receive a generated binary counterpart. These associated binary variables may be accessed via the get_associated_binary() method.

m.Y[1].get_associated_binary()

Additional augmented variables and their corresponding constraints may also be created, as described in Advanced LogicalConstraint Examples.

Following solution of the GDP model, values of the Boolean variables may be updated from their algebraic binary counterparts using the update_boolean_vars_from_binary() function.

pyomo.core.plugins.transform.logical_to_linear.update_boolean_vars_from_binary(model, integer_tolerance=1e-05)[source]

Updates all Boolean variables based on the value of their linked binary variables.

Reformulation to MI(N)LP

To use standard commercial solvers, you must convert the disjunctive model to a standard MILP/MINLP model. The two classical strategies for doing so are the (included) Big-M and Hull reformulations.

Big-M (BM) Reformulation

The Big-M reformulation[5] results in a smaller transformed model, avoiding the need to add extra variables; however, it yields a looser continuous relaxation. By default, the BM transformation will estimate reasonably tight M values for you if variables are bounded. For nonlinear models where finite expression bounds may be inferred from variable bounds, the BM transformation may also be able to automatically compute M values for you. For all other models, you will need to provide the M values through a “BigM” Suffix, or through the bigM argument to the transformation. We will raise a GDP_Error for missing M values.

To apply the BM reformulation within a python script, use:

TransformationFactory('gdp.bigm').apply_to(model)

From the Pyomo command line, include the --transform pyomo.gdp.bigm option.

Multiple Big-M (MBM) Reformulation

We also implement the multiple-parameter Big-M (MBM) approach described in literature[4]. By default, the MBM transformation will solve continuous subproblems in order to calculate M values. This process can be time-consuming, so the transformation also provides a method to export the M values used as a dictionary and allows for M values to be provided through the bigM argument.

For example, to apply the transformation and store the M values, use:

mbigm = TransformationFactory('gdp.mbigm')
mbigm.apply_to(model)

# These can be stored...
M_values = mbigm.get_all_M_values(model)
# ...so that in future runs, you can write:
mbigm.apply_to(m, bigM=M_values)

From the Pyomo command line, include the --transform pyomo.gdp.mbigm option.

Hull Reformulation (HR)

The Hull Reformulation requires a lifting into a higher-dimensional space and consequently introduces disaggregated variables and their corresponding constraints.

Note

  • All variables that appear in disjuncts need upper and lower bounds.
  • The hull reformulation is an exact reformulation at the solution points even for nonconvex GDP models, but the resulting MINLP will also be nonconvex.

To apply the Hull reformulation within a python script, use:

TransformationFactory('gdp.hull').apply_to(model)

From the Pyomo command line, include the --transform pyomo.gdp.hull option.

Hybrid BM/HR Reformulation

An experimental (for now) implementation of the cutting plane approach described in literature[6] is provided for linear GDP models. The transformation augments the BM reformulation by a set of cutting planes generated from the HR model by solving separation problems. This gives a model that is not as large as the HR, but with a stronger continuous relaxation than the BM.

This transformation is accessible via:

TransformationFactory('gdp.cuttingplane').apply_to(model)

Direct GDP solvers

Pyomo includes the contributed GDPopt solver, which can directly solve GDP models. Its usage is described within the contributed packages documentation.

References

[1]Chen, Q., Johnson, E. S., Siirola, J. D., & Grossmann, I. E. (2018). Pyomo.GDP: Disjunctive Models in Python. In M. R. Eden, M. G. Ierapetritou, & G. P. Towler (Eds.), Proceedings of the 13th International Symposium on Process Systems Engineering (pp. 889–894). San Diego: Elsevier B.V. https://doi.org/10.1016/B978-0-444-64241-7.50143-9
[2]Chen, Q., Johnson, E. S., Bernal, D. E., Valentin, R., Kale, S., Bates, J., Siirola, J. D. and Grossmann, I. E. (2021). Pyomo.GDP: an ecosystem for logic based modeling and optimization development, Optimization and Engineering (pp. 1-36).https://doi.org/10.1007/s11081-021-09601-7
[3]Grossmann, I. E., & Trespalacios, F. (2013). Systematic modeling of discrete-continuous optimization models through generalized disjunctive programming. AIChE Journal, 59(9), 3276–3295. https://doi.org/10.1002/aic.14088
[4]Trespalacios, F., & Grossmann, I. E. (2015). Improved Big-M reformulation for generalized disjunctive programs. Computers and Chemical Engineering, 76, 98–103. https://doi.org/10.1016/j.compchemeng.2015.02.013
[5]Nemhauser, G. L., & Wolsey, L. A. (1988). Integer and combinatorial optimization. New York: Wiley.
[6]Sawaya, N. W., & Grossmann, I. E. (2003). A cutting plane method for solving linear generalized disjunctive programming problems. Computer Aided Chemical Engineering, 15(C), 1032–1037. https://doi.org/10.1016/S1570-7946(03)80444-3